什么是堆：
堆的定义：n个元素的序列k={k0,k1,……,kn-1},当且仅满足条件
(1)ki >= k2i+1 和 ki >= k2i+2 (2)ki <= k2i+1 和 ki <= k2i+2
(1)称为大根堆 (2)称为小根堆
可以把堆看成完全二叉树。
什么是优先队列：
优先队列是一种常见的抽象数据类型，它与"队列"不同，不遵循"先进先出"原则，而遵循"最小元素先出"原则。
优先队列的基本操作有三个：
(1) 向优先队列里插入一个元素
(2) 在优先队列找出最小元素
(3) 删除优先队列中最小元素
可以用堆来实现有限队列
优先队列的实现：
1 #include "stdio.h" 2 #include "stdlib.h" 3 4 typedef int DATATYPE; 5 6 /********************优先队列存储结构********************************/ 7 struct priorityQueue 8 { 9 int MAXNUM; //存储结构长度 10 int n; //实际元素个数 11 DATATYPE * element; 12 }; 13 typedef struct priorityQueue *PQ; 14 15 /********************创建优先队列***********************************/ 16 PQ createPQ(int maxnum) 17 { 18 PQ pq = NULL; 19 pq = (PQ) malloc(sizeof(struct priorityQueue)); 20 if(NULL != pq) 21 { 22 pq->element = malloc(sizeof(DATATYPE) * maxnum); 23 if(pq->element != NULL) 24 { 25 pq->MAXNUM = maxnum; 26 pq->n = 0; 27 } 28 } 29 return pq; 30 } 31 32 /****************************判断优先队列是否为空****************************/ 33 int isEmpty_heap(PQ pq) 34 { 35 return pq->n == 0; 36 } 37 38 /**************************往优先队列中插入元素*******************************/ 39 void add_heap(PQ pq, DATATYPE x) 40 { 41 int i = -1; //标志元素最后要插入位置的下标 42 if(pq->n >= pq->MAXNUM) //如果队列已满，无法插入 43 { 44 printf("PriorityQueue is full"); 45 return; 46 } 47 //寻找插入的位置,pq->n是未有元素的空位 48 for(i = pq->n; i > 0 && x < pq->element[(i-1)/2]; i = (i - 1)/2) 49 { 50 pq->element[i] = pq->element[(i-1)/2]; 51 } 52 //插入元素 53 pq->element[i] = x; 54 pq->n++; 55 } 56 57 /*************************在三个元素中，找出最小元素的下标********************/ 58 int findMinIndex(PQ pq,int index1, int index2, int index3) 59 { 60 int min = 0; 61 min = (pq->element[index1] < pq->element[index2])?index1:index2; 62 min = (pq->element[min] < pq->element[index3])?min:index3; 63 return min; 64 } 65 66 /*************************删除优先队列最小元素************************************/ 67 void removeMin_heap(PQ pq) 68 { 69 int endIndex,leftchild,rightchild,index,minIndex; 70 if(isEmpty_heap(pq)) //如果为空队列，返回 71 return; 72 endIndex = --pq->n; //找到队列尾元素下标,并将首元素删除 73 74 index = 0; //空位的下标，开始时在根节点处 75 for(;index < endIndex;) 76 { 77 leftchild = index*2 + 1; 78 rightchild = index*2 + 2; 79 if(leftchild > endIndex || rightchild > endIndex) 80 { 81 pq->element[index] = pq->element[endIndex]; 82 break; 83 } 84 85 minIndex = findMinIndex(pq,endIndex,leftchild,rightchild); 86 pq->element[index] = pq->element[minIndex]; 87 if(minIndex == endIndex) 88 break; 89 else if(minIndex == leftchild) 90 index = leftchild; 91 else if(minIndex == rightchild) 92 index = rightchild; 93 } 94 } 95 96 97 98 /***********************显示优先队列中元素的排列****************************/ 99 void show(PQ pq) 100 { 101 int i = 0; 102 103 for(i = 0; i < pq->n; i++) 104 { 105 printf("%d, ",pq->element[i]); 106 } 107 108 } 109 110 int main() 111 { 112 PQ pq = createPQ(6); 113 add_heap(pq, 3); 114 add_heap(pq, 2); 115 add_heap(pq, 8); 116 add_heap(pq, 4); 117 add_heap(pq, 6); 118 add_heap(pq, 10); 119 120 show(pq); 121 printf("\n"); 122 123 removeMin_heap(pq); 124 show(pq); 125 return 0; 126 }
删除优先队列的原理为：在最小节点被删除后，根节点形成一个空位，这时考虑能否把处在队中最后位置的节点填入这里。由于这样做可能破坏堆序性，所以选择这个元素与根的两个子节点中最小的节点填入，选择的结果可能使得原来的空位向叶节点方向传递。如此反复交换，最终到堆中最后节点小于等于空位的两个子节点时，将最后节点填入这个空位。
利用堆，可以进行排序：
1 /********************对元素进行排序*********************************/ 2 void sort(DATATYPE * data,int size) 3 { 4 int i; 5 PQ pq = createPQ(size); 6 7 for(i = 0; i < size; i++) 8 { 9 add_heap(pq,data[i]); 10 } 11 12 for(i = 0; i < size; i++) 13 printf("%d, ",removeMin_heap(pq)); 14 }
测试：
1 int main() 2 { 3 int i = 0; 4 int a[100]; 5 for(i = 99; i >= 0; i--) 6 a[i] = i * 2 + 1; 7 8 9 sort(a,100); 10 return 0; 11 }
输出结果：
数组长度的限制：
栈里能声明的最大是１Ｍ
也就是char a［n］的大小不能大于１Ｍ
堆里的可以很大
也就是char ＊ a； a＝new char [n]的话a的大小可以达２Ｇ