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