堆 (heap)

什么是堆

例 : 计算机CPU调动的排队原则 , 不考虑时序而考虑优先级

  • 优先队列 (Priority Queue) : 特殊的”队列” , 取出元素的顺序是按照元素的优先权 (关键字) 大小 , 而不是元素进入队列的先后顺序

操作

主要操作是 : 插入和删除 (最大值或最小值)

用什么数据结构实现优先队列 ?

采用数组实现优先队列

插入 : 元素总是插入尾部 三 : 树(下) - (1)堆 - 图1
删除 :
①查找最大或最小关键字 三 : 树(下) - (1)堆 - 图2
②从数组中删去需要移动元素 三 : 树(下) - (1)堆 - 图3

采用链表实现优先队列

插入 : 元素总时插入链表头部 三 : 树(下) - (1)堆 - 图4
删除 :
①查找最大或最小关键字 三 : 树(下) - (1)堆 - 图5
②删去结点 三 : 树(下) - (1)堆 - 图6

采用有序数组实现优先队列

插入 :
①找到合适的位置 三 : 树(下) - (1)堆 - 图7三 : 树(下) - (1)堆 - 图8
②移动元素并插入 三 : 树(下) - (1)堆 - 图9
删除 : 删去最后一个元素 三 : 树(下) - (1)堆 - 图10

采用有序链表实现优先队列

插入 :
①找到合适的位置 三 : 树(下) - (1)堆 - 图11
②插入元素 三 : 树(下) - (1)堆 - 图12
删除 : 删去首元素或最后元素 三 : 树(下) - (1)堆 - 图13

是否可以用二叉树?

用二叉查找树 : (不能)

优点 (需求) :

  • 查找 : 要查找的结点位置与树的高度有关
  • 删除 : 要删除最大或最小值 , 一定在二叉查找树的最左或最右

缺点 :
因为删除的一定是最大或最小值 , 一定在最左或最右 , 删除几次之后树会变歪

如果采用二叉树 , 应更关注插入还是删除 ?

  • 树结点顺序怎么安排 ?
  • 树结构 ?

显然 , 应该更关注 删除最大值
让最大值在根结点的位置 - 最大堆
完全二叉树

优先队列的完全二叉树表示

image.png

最大堆和最小堆

image.png

堆的抽象数据类型描述

名称 : 最大堆 (MaxHeap)
对象 : 完全二叉树 , 每个结点的元素值不小于其子结点的元素值
操作集 : (最大堆H , 元素 item ∈ ElementType) , 主要操作为

  • MaxHeap Create( int MaxSize ) : 创建一个空的最大堆
  • Boolean IsFull( MaxHeap H ) : 判断最大堆H是否已满
  • Insert( MaxHeap H, ElementType item) : 将元素item插入最大堆H 主要操作
  • Boolean IsEmpty( MaxHeap H) : 判断最大堆H是否为空
  • ElementType DeleteMax( MaxHeap H) : 返回H中最大元素 (高优先级) 主要操作

最大堆的操作

最大堆的创建

创建结构 :

  1. typedef struct HeapStruct *MaxHeap;
  2. struct HeapStruct{
  3. ElementType *Elements; /*存储堆元素的数组*/
  4. int Size; /*堆的当前元素个数*/
  5. int Capacity; /*堆的最大容量*/
  6. }

创建堆 :

  1. MaxHeap Create(int MaxSize){
  2. /*创建容量为MaxSize的空的最大堆*/
  3. MaxHeap H = malloc(sizeof(struct HeapStruct));
  4. /*接下来对结构里的三个分量分别赋值*/
  5. H->Elements = malloc( (MaxSize+1)* sizeof(ElementType));
  6. H->Size = 0;
  7. H->Capacity = MaxSize;
  8. H->Elements[0] = MaxData;
  9. /*定义“哨兵”为大于堆中所有可能元素的值,以便以后更快操作*/
  10. return H;
  11. }

最大堆的插入 O(logN)

image.pngimage.png

  1. void Insert(MaxHeap H, ElementType item){
  2. /*将元素item插入最大堆H,其中H->Elements[0]已经定义为哨兵*/
  3. int i;
  4. if(IsFull(H)){
  5. printf("最大堆已满");
  6. return;
  7. }
  8. i = ++H->Size; /*i指向插入后堆中的最后一个元素的位置,size+1就是最后一个位置*/
  9. for(;H->Elements[i/2]<item; i/=2) /*为了保证有序性与父结点比较*/
  10. H->Elements[i] = H->Elements[i/2]; /*向下过滤结点*/
  11. H->Elements[i] = item; /*将item插入*/
  12. }

for循环中 , H->Elements[0] 是哨兵元素 , 它不小于堆中的最大元素 , 控制顺环结束
image.png []中代表数组下标
当插入的数是所有数中最大的 , 会一直重复 比较 -> 交换 这个过程 , 直到 0号位置的哨兵位置

最大堆的删除

  • 取出根结点 (最大值元素) , 同时删除堆的一个结点

(删除的过程相当于是找到根结点替补的过程)
image.pngimage.pngimage.png
上图中的任务 : 删除元素58
①把 31 移至根
②找出 31 的较大的孩子44 , 交换
③找出 31 的较大的孩子35 , 交换
…(重复这个过程 , 直到31比31的孩子都大)

  1. ElementType DeleteMax(MaxHeap H){
  2. /*从最大堆H中取出键值最大的元素,并删除一个结点*/
  3. int Parent, Child;
  4. ElementType MaxItem, temp;
  5. if(IsEmpty(H)){
  6. printf("最大堆已空");
  7. return;
  8. }
  9. MaxItem = H->Elements[1]; /*取出根结点最大值*/
  10. /*用最大堆中最后一个元素从根结点开始向上过滤下层结点*/
  11. temp = H->Elements[H->Size--];
  12. for(Parent=1 ; Parent*2 <= H->Size ; Parent = Child){
  13. /*Parent*2 <= H->Size : 判别是否有左儿子*/
  14. Child = Parent*2; /*指向左儿子,有儿子为Parent*2+1*/
  15. if( (Child != H->Size) && ( H->Elements[Child] < H->Elements[Child+1]) )
  16. Child++; /*Child指向左右子结点的较大者*/
  17. if( temp >= H->Elements[Child]) break;
  18. else /*移动temp元素到下一层*/
  19. H->Elements[Parent] = H->Elements[Child];
  20. }
  21. H->Elements[Parent] = temp;
  22. return MaxItem;
  23. }

最大堆的建立

堆的一个应用 : 堆排序
——需要先建堆
需要考虑的问题 : 已知N个元素 , 怎么构建最大堆
(将已经存在的N个元素按最大堆的要求存放在一个一维数组中)

方法1 : 插入

通过插入操作 , 将N个元素一个个相继插入到一个初始为空的堆中去 , 时间花费最多为 O(NlogN)

缺点 : 效率不高

方法2 : 线性建立最大堆

在线性时间复杂度下建立最大堆 O(N)

步骤 :
(1) 将N个元素按输入顺序存入 , 先满足完全二叉树的结构特性
(2) 调整各结点位置 , 以满足最大堆的有序特性
(3) 从倒数第一个有儿子的结点开始调整 (把每一个子堆调整好)
(4) 下图的调整顺序 : 87 , 30->72 , 91->83 , 87->43 , 91->66 , 83->66 , 79->91 , 83->79

image.png

建堆时 , 最坏情况下需要挪动次数是等于树中各结点的高度和


讨论 : 减堆中某个元素值的操作

将被删除的节点称为A,由堆的性质可知以A为根的子树也是堆,可以仿造堆中删除和添加的算法。为了方便描述我们假定这个堆是最大堆,具体操作如下:

  1. 将堆中最后一个节点覆盖到A处。
  2. 比较A与A的根P的大小。如果A>P,则A需要上移,进入步骤3;如果A<P,则A需要下移,进入步骤4。
  3. 将P和A交换位置,A的根记为P,如果A>P,则执行步骤3,否则结束算法。
  4. 将当A没有子节点时,结束算法,否则,进入步骤5。
  5. 将A与最大的子节点M比较,如果A<M,将A与M交换位置,进入步骤4,否则结束算法。

课件

5.1堆.pdf

C语言实现 : 堆的定义与操作

  1. typedef struct HNode *Heap; /* 堆的类型定义 */
  2. struct HNode {
  3. ElementType *Data; /* 存储元素的数组 */
  4. int Size; /* 堆中当前元素个数 */
  5. int Capacity; /* 堆的最大容量 */
  6. };
  7. typedef Heap MaxHeap; /* 最大堆 */
  8. typedef Heap MinHeap; /* 最小堆 */
  9. #define MAXDATA 1000 /* 该值应根据具体情况定义为大于堆中所有可能元素的值 */
  10. MaxHeap CreateHeap( int MaxSize )
  11. { /* 创建容量为MaxSize的空的最大堆 */
  12. MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));
  13. H->Data = (ElementType *)malloc((MaxSize+1)*sizeof(ElementType));
  14. H->Size = 0;
  15. H->Capacity = MaxSize;
  16. H->Data[0] = MAXDATA; /* 定义"哨兵"为大于堆中所有可能元素的值*/
  17. return H;
  18. }
  19. bool IsFull( MaxHeap H )
  20. {
  21. return (H->Size == H->Capacity);
  22. }
  23. bool Insert( MaxHeap H, ElementType X )
  24. { /* 将元素X插入最大堆H,其中H->Data[0]已经定义为哨兵 */
  25. int i;
  26. if ( IsFull(H) ) {
  27. printf("最大堆已满");
  28. return false;
  29. }
  30. i = ++H->Size; /* i指向插入后堆中的最后一个元素的位置 */
  31. for ( ; H->Data[i/2] < X; i/=2 )
  32. H->Data[i] = H->Data[i/2]; /* 上滤X */
  33. H->Data[i] = X; /* 将X插入 */
  34. return true;
  35. }
  36. #define ERROR -1 /* 错误标识应根据具体情况定义为堆中不可能出现的元素值 */
  37. bool IsEmpty( MaxHeap H )
  38. {
  39. return (H->Size == 0);
  40. }
  41. ElementType DeleteMax( MaxHeap H )
  42. { /* 从最大堆H中取出键值为最大的元素,并删除一个结点 */
  43. int Parent, Child;
  44. ElementType MaxItem, X;
  45. if ( IsEmpty(H) ) {
  46. printf("最大堆已为空");
  47. return ERROR;
  48. }
  49. MaxItem = H->Data[1]; /* 取出根结点存放的最大值 */
  50. /* 用最大堆中最后一个元素从根结点开始向上过滤下层结点 */
  51. X = H->Data[H->Size--]; /* 注意当前堆的规模要减小 */
  52. for( Parent=1; Parent*2<=H->Size; Parent=Child ) {
  53. Child = Parent * 2;
  54. if( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) )
  55. Child++; /* Child指向左右子结点的较大者 */
  56. if( X >= H->Data[Child] ) break; /* 找到了合适位置 */
  57. else /* 下滤X */
  58. H->Data[Parent] = H->Data[Child];
  59. }
  60. H->Data[Parent] = X;
  61. return MaxItem;
  62. }
  63. /*----------- 建造最大堆 -----------*/
  64. void PercDown( MaxHeap H, int p )
  65. { /* 下滤:将H中以H->Data[p]为根的子堆调整为最大堆 */
  66. int Parent, Child;
  67. ElementType X;
  68. X = H->Data[p]; /* 取出根结点存放的值 */
  69. for( Parent=p; Parent*2<=H->Size; Parent=Child ) {
  70. Child = Parent * 2;
  71. if( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) )
  72. Child++; /* Child指向左右子结点的较大者 */
  73. if( X >= H->Data[Child] ) break; /* 找到了合适位置 */
  74. else /* 下滤X */
  75. H->Data[Parent] = H->Data[Child];
  76. }
  77. H->Data[Parent] = X;
  78. }
  79. void BuildHeap( MaxHeap H )
  80. { /* 调整H->Data[]中的元素,使满足最大堆的有序性 */
  81. /* 这里假设所有H->Size个元素已经存在H->Data[]中 */