- // 二叉堆实现优先队列
- // Bery 2013-03-26
- #include <stdio.h>
- #define MINDATA -32767
- // 二叉堆
- typedef struct HeapStruct
- {
- int capacity; // 最大堆容量
- int size; // 当前堆大小
- int * element; // 节点指针
- } * PriorityQueue;
- // 初始化
- PriorityQueue Initialize(int capacity)
- {
- PriorityQueue h = (PriorityQueue)malloc(sizeof (struct HeapStruct));
- h->element = (int *)malloc((capacity + 1) * sizeof (int));
- h->capacity = capacity;
- h->size = 0;
- // 将堆的顶端存入最小值, 作为标志位
- h->element[0] = MINDATA;
- return h;
- }
- // 入队
- void Insert(int e, PriorityQueue h)
- {
- int i; // 索引
- if (h->size == h->capacity)
- {
- printf("队满, 入队失败. \\n");
- return;
- }
- h->size++;
- // 从队尾元素开始, 找到元素要入队的位置
- for (i = h->size; h->element[i / 2] > e; i = i / 2)
- h->element[i] = h->element[i / 2];
- h->element[i] = e;
- }
- // 出队
- int DeleteMin(PriorityQueue h)
- {
- int i; // 索引
- int child; // 子元素
- int min; // 最小值
- int last; // 队尾元素
- if (h->size == 0)
- {
- printf("队空, 出队失败 \\n");
- return 0;
- }
- min = h->element[1]; // 要出队的元素
- last = h->element[h->size]; // 队尾元素未必是最大值
- h->size--;
- for (i = 1; i * 2 <= h->size; i = child)
- {
- // 计算i的左子树
- child = i * 2;
- // 如果i的右子树小于左子树, 则使child指向右子树
- if (child != h->size && h->element[child + 1] < h->element[child])
- child++;
- // 如果队尾元素大于当前节点的最小子树, 则把子树赋给当前节点
- // 否则退出循环
- if (last > h->element[child])
- h->element[i] = h->element[child];
- else
- break;
- }
- // 当前节点的位置应存入last
- h->element[i] = last;
- return min;
- }
- int main(void)
- {
- int i;
- int size;
- PriorityQueue h = Initialize(20);
- Insert(13, h);
- Insert(14, h);
- Insert(16, h);
- Insert(19, h);
- Insert(21, h);
- Insert(29, h);
- Insert(68, h);
- Insert(65, h);
- Insert(26, h);
- Insert(32, h);
- Insert(31, h);
- size = h->size;
- // 遍历所有元素
- for (i = 0; i < size; i++)
- printf("%d\\t", DeleteMin(h));
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/161220138060.html
来源: http://www.codesnippet.cn/detail/161220138060.html