堆（优先队列）priority queue
特殊的队列，取出元素的顺序是依照元素的优先权（关键字）大小，而出元素进入队列的先后顺序
操作：查找最大值（最小值），删除（最大值）
数组：
链表：
有序数组：
有序链表：
采用二叉搜索树？ NO
采用完全二叉树 YES
堆的连个特性
结构性：用数组表示的完全二叉树：
有序性：任一结点的关键字是其字树所有结点的最大值（或最小值）
最大堆（MaxHeap）也称大顶堆：最大值
最小堆（MinHeap）也称“小顶堆”：最小值
从根节点到任意结点路径上结点序列的有序性
操作：插入任意一个元素，删除最 大值元素
最大堆的删除：取出根节点（最大值）元素，同时删除堆的一个结点
最大堆的建立：将已存在的N个元素按最大堆的要求存放在一个以为数组中
1 #include <stdio.h> 2 #include <stdlib.h> 3 //最大堆 4 5 #define MaxData 1000 //哨兵，该值应该根据具体情况定义为大于堆中所有可能元素的值 6 7 typedef int ElementType; 8 9 typedef struct HeapNode * MaxHeap; 10 struct HeapNode { 11 int Capacity; //堆的最大容量 12 int Size; //堆中当前元素个数 13 ElementType *Data; //用于存储元素的数组 14 };
建一个空的最大堆：
1 //建立一个空的最大堆 2 MaxHeap InitHeap(int maxsize) 3 { 4 MaxHeap H = (MaxHeap)malloc(sizeof(struct HeapNode)); 5 H->Data = (ElementType*)malloc(sizeof(struct HeapNode) * (maxsize + 1)); //堆中的元素是从下标为1开始存储的，但是为了保证这个堆能存下maxsize个元素，所以要分配maxsize + 1个内存单元 6 H->Capacity = maxsize; 7 H->Size = 0; 8 H->Data[0] = MaxData; //将0下标的单元存储哨兵 9 for (int i = 1; i < maxsize + 1; i++) 10 H->Data[i] = 0; 11 return H; 12 }
判断堆是否已满或是否为空：
1 int IsEmpty(MaxHeap H) 2 { 3 return H->Size == 0; 4 } 5 6 //判断堆是否已满 7 int IsFull(MaxHeap H) 8 { 9 return H->Size == H->Capacity; 10 }
插入一个元素：
1 //最大堆中插入一个元素 2 void Insert(MaxHeap H, ElementType item) 3 { 4 int i; 5 if (IsFull(H)) 6 { 7 printf("The heap is full\n"); 8 return; 9 } 10 i = ++H->Size; //i为插入后堆中最后一个元素的位置 11 for (; H->Data[i / 2] < item; i /= 2) 12 H->Data[i] = H->Data[i / 2]; //循环退出时，父节点的数据已经大于item， item已经找到了正确的位置 13 H->Data[i] = item; //将item赋给正确的下标单元 14 }
删除一个元素：
1 ElementType Delete(MaxHeap H) 2 { 3 ElementType temp, Max; 4 int parent = 1, child; 5 if (IsEmpty(H)) 6 { 7 printf("The heap is empty!\n"); 8 return 0; 9 } 10 Max = H->Data[1]; //现将最大值即根节点的值记录下来 11 temp = H->Data[H->Size--]; //用最后的结点元素暂时代替根节点的数据，然后将堆的数据大小减1 12 13 //如果2 * parent > 0，那么说明parent已经是根节点了 14 for (; 2 * parent <= H->Size; parent = child) 15 { 16 child = 2 * parent; 17 18 //如果Child != H->Size说明child不是最后一个结点，该parent结点还有右节点， 19 //并且如果右节点的值大于左结点，那么child++; 20 if (child != H->Size && (H->Data[child + 1] < H->Data[child])) 21 child++; //child指向左右子节点的较大者 22 if (temp > H->Data[child]) break; //如果孩子结点已经小于temp了， 说明找到了合适的位置 23 else 24 H->Data[parent] = H->Data[child]; 25 } 26 H->Data[parent] = temp; 27 return Max; 28 }
最大堆的建立：
1.第一步，将N个元素按输入顺序存入二叉树中，这一步需要求满足完全二叉树的结构特性，而不管其有序性
2.从最后一个右孩子的结点开始调整，做类似删除元素时的下滤操作，逐个结点调整，直至根节点
1 //创建一个最大堆 2 MaxHeap CreateMaxHeap() 3 { 4 int dt, i = 0, j; 5 int parent, child; 6 ElementType X; 7 MaxHeap H = InitHeap(20); //先创建一个空的最大堆，然后往里面填充元素 8 while (scanf_s("%d", &dt) != EOF) 9 { 10 H->Data[i + 1] = dt; 11 i++; 12 H->Size++; 13 } 14 for (j = i / 2; j >= 1; j--) //从i / 2开始逐一向下过滤 15 { 16 //下面的操作和删除元素是一模一样的，只是不用将的元素个数减一 17 X = H->Data[j]; 18 for (parent = j; 2 * parent <= H->Size; parent = child) 19 { 20 child = 2 * parent; 21 if (child != H->Size && H->Data[child] < H->Data[child + 1]) 22 child++; 23 if (H->Data[child] < X) 24 break; 25 else 26 H->Data[parent] = H->Data[child]; 27 } 28 H->Data[parent] = X; 29 } 30 return H; 31 }
打印堆中的元素：
1 //打印堆中元素 2 void printHeap(MaxHeap H) 3 { 4 for (int i = 1; i <= H->Size; i++) 5 printf("%d ", H->Data[i]); 6 printf("\n"); 7 }
先序建立树：
1 void PreOrderCreateHeap(MaxHeap H, int index) 2 { 3 int dt; 4 scanf_s("%d", &dt); 5 if (dt == 0) 6 { 7 return; 8 } 9 H->Size++; 10 H->Data[index] = dt; 11 printf("please enter the left child of %d :", dt); 12 PreOrderCreateHeap(H, 2 * index); 13 printf("please enter the right child of %d: ", dt); 14 PreOrderCreateHeap(H, 2 * index + 1); 15 }
主函数：
1 int main() 2 { 3 MaxHeap H = CreateMaxHeap(); 4 PreOrderCreateHeap(H, 1); 5 printHeap(H); 6 7 return 0; 8 }
