数据结构——堆的实现与应用

前言

我们知道二叉树有两种存储结构：一种是链式结构，一种是数组结构。由于数组结构的特殊性，它通常被用来存储完全二叉树。而数组结构的完全二叉树中又有一个特殊的数据结构，那就是堆。这一节将介绍堆的实现和堆的应用。

文章目录

堆的概念和结构

堆是一颗特殊的完全二叉树。
在这颗二叉树中，根节点被称为堆顶。

堆又分为了大堆和小堆：
大堆的特点是：树中的所有父节点的值都大于等于它的子节点，堆顶的数据是整棵树中最大的。
小堆的特点是：树中的所有父节点的值都小于等于它的子节点，堆顶的数据是整棵树中最大的。

注意：两种的结构都只是限制了父节点和子节点的大小关系，不会被左右孩子节点的大小所影响。

堆的结构

堆的逻辑结构是一颗二叉树，而物理结构却是一个数组——堆是一个数组结构的完全二叉树。

这里我们可以回顾一下数组结构的二叉树中，父节点和子节点的关系：

通过父节点下标找到左右子节点的下标：

      c
     
     
      h
     
     
      i
     
     
      l
     
     
      
       d
      
      
       左
      
     
     
      =
     
     
      p
     
     
      a
     
     
      r
     
     
      e
     
     
      n
     
     
      t
     
     
      ∗
     
     
      2
     
     
      +
     
     
      1
     
     
      ;
     
     
      c
     
     
      h
     
     
      i
     
     
      l
     
     
      
       d
      
      
       右
      
     
     
      =
     
     
      p
     
     
      a
     
     
      r
     
     
      e
     
     
      n
     
     
      t
     
     
      ∗
     
     
      2
     
     
      +
     
     
      1
     
    
    
      child_左 = parent *2 +1; child_右 = parent*2+1 
    
   
  child左​=parent∗2+1;child右​=parent∗2+1

通过一个节点的下标找到对应的父节点下标：

      p
     
     
      a
     
     
      r
     
     
      e
     
     
      n
     
     
      t
     
     
      =
     
     
      (
     
     
      c
     
     
      h
     
     
      i
     
     
      l
     
     
      d
     
     
      −
     
     
      1
     
     
      )
     
     
      /
     
     
      2
     
     
      ;
     
    
    
      parent = (child-1)/2; 
    
   
  parent=(child−1)/2;

我们可以把任何一个数组当作完全二叉树，但是只有符合堆性质的数组才能被看作堆：

注意：堆不一定是有序数组，但是有序数组一定可以看作堆。

堆的实现

对于堆，我们需要学习的操作有：堆的插入，删除和创建。
而这些操作都是基于堆的自我调整。所谓堆的自我调整，就是把一个不符合堆性质的完全二叉树，调整成一个堆。

下面我们来操作这样一个小堆，分析堆需要怎样自我调整。

堆的插入

向堆中添加数据的唯一要求是：添加数据前后数组都满足同一种堆的性质。

所以在向堆中添加数据的时候，我们不能破坏掉原有的结构，如果将数据添加到数组的中间或者数组第一个位置，那么不仅可能破坏掉原有的堆结构，还会提高时间复杂度。
最好的方法就是将新的数据添加再数据的最后，然后利用堆的自我向上调整。
代码实现：

voidHeapPush(Heap* php,HPDataType x){assert(php);//检查空指针if(php->capacity == php->size)//向数组添加数据的时候检查容量{size_t newCapacity = php->capacity ==0?4: php->capacity *2;
        HPDataType* tmp =(HPDataType*)realloc(php->data,sizeof(HPDataType)* newCapacity);
        
        php->data = tmp;    
        php->capacity = newCapacity;}

    php->data[php->size++]= x;//将新的数据放在数组最后一个元素的下一个位置AdjustUp(php->data, php->size -1);//对现在数组的最后一个元素进行向上调整。}

向上调整：
如果数组的前N个数组都满足堆的结构，那么堆的向上调整可以将数组的前N+1 个元素调整为一个堆。
向上调整的逻辑：首先找到需要被调整节点的父节点，用这个节点和它的父节点作比较：如果满足堆的结构要求，就说明此时整个数组已经满足堆的结构了，不需要再改动；如果不满足堆的结构要求，就需要交换两个节点，然后找到新的父节点，再次比较…多次循环后就会满足堆的结构要求。

代码实现：
注意：在实现小堆时，父节点大于子节点就交换两个节点。实现大堆时，父节点小于子节点就交换两个节点。

voidAdjustUp(HPDataType* data,size_t child){assert(data);//判断空指针size_t parent =(child -1)/2;//通过下标间的关系找到对应父节点的下标while(child >0)//循环的原因：有可能持续性的向上调整。{if(data[parent]> data[child])//和父节点比较:小堆（父节点大于子节点就交换）、大堆（父节点小于子节点就交换）{Swap(&data[parent],&data[child]);
            child = parent;//交换后，需要找到新子节点下标和父节点下标
            parent =(child -1)/2;}else{break;//如果和父节点比较时已经满足堆的要求，就直接退出循环}}}

在这段代码中：我们传入了两个参数，分别代表一个数组和数组中需要向上调整的节点的下标。
循环有两个结束条件：

1. 需要调整的节点就在堆顶（根节点）。

举个例子：向堆中插入一个数据

5

：

会得到这样一个堆：

2. 需要调整的节点和父节点的关系已经满足对应堆的要求。

举个例子：向堆中再插入一个数据

25

会得到这样一个堆：

堆的删除

在堆这个数据结构中，删除操作被指定为删除堆顶的数据。
同样，需要保持删除堆顶的数据后，这个数组仍然是一个堆结构。
我们不能一下子改变多个数据的下标，这样会打乱堆的结构。
最好的方法就是：将堆中的第一个数据和最后一个数据交换，然后让新的堆顶数据向下调整：

//删除堆顶的数据voidHeapPop(Heap* php){assert(php);if(php->size >0){Swap(&(php->data[0]),&(php->data[php->size -1]));//交换第一个元素和最后一个元素
        php->size--;//删除掉最后一个元素AdjustDown(php->data,0,php->size );//对第一个元素向下调整}}

向下调整：

如果一个数组中后N个元素满足堆的性质，那么堆的向下调整可以让数组中的后N+1个元素满足堆的性质。

向下调整的逻辑：首先要通过下标找到对应节点的左右孩子节点，如果是实现小堆，就需要找到两个孩子节点中较小的一个，如果是实现大堆，就需要找到两个孩子节点中较大的一个。然后拿父节点和我们找到的指定子节点左比较，如果不满足堆的结构，就需要交换父节点和子节点，然后利用新的父节点下标去寻找满足条件的子节点。

代码的实现：

voidAdjustDown(HPDataType* data,size_t root,size_t size){assert(data);size_t parent = root;//确定父节点的下标size_t child = parent *2+1;//确定子节点的下标while(child < size){if(child +1< size && data[child]> data[child +1])//实现为小堆:左孩子更大的时候child加1;        {//实现为大堆:左孩子更小的时候child加1;
            child++;}//利用这一个选择语句选择出两个子节点中满足条件的节点下标。if(data[parent]> data[child]){Swap(&data[parent],&data[child]);
            parent = child;
            child = parent *2+1;}else{break;}}}

这段代码有三个参数：第一个参数是数组，第二个参数是开始向下调整的元素的下标，第三个参数是数组的大小。

循环的退出条件有两种：

1. 我们计算出来的子节点的下标已经超出数组中有效数据的大小了。

最终的结果是：

2. 在超出数组大小前的某一次调整就已经将数组调整为对应的堆结构。
如果将上面的节点值25 改为50，那么就会出现这样的情况：

最终得到这样一个堆：

堆的创建

堆的创建方式有两种：

1. 利用结构体去创建一个结构功能充足的堆。 其中包括了：堆结构的定义、堆的销毁、堆的插入、堆的删除、判断空堆、得到堆顶元素和依次遍历堆节点等操作。typedefint HPDataType;//存储数据类型重定义typedefstructHeap{ HPDataType* data;size_t size;size_t capacity;}Heap;//堆结构的定义以及类型重定义//初始化堆voidHeapInit(Heap* php);//删除堆voidHeapDestroy(Heap* php);//向堆中添加数据voidHeapPush(Heap* php,HPDataType x);//向上调整voidAdjustUp(HPDataType* data,size_t child);//删除堆顶的数据voidHeapPop(Heap* php);//向下调整voidAdjustDown(HPDataType* data,size_t parent,size_t size);//打印整个堆的内容voidHeapPrint(Heap* php);//得到堆顶的数据HPDataType HeapTop(Heap* php);//判断空堆bool HeapEmpty(Heap* php);
2. 利用一个数组去创建堆 我们知道可以把任何一个数组当作完全二叉树来操作。我们可以通过对这个数组执行堆的调整功能，将这个数组调整为堆结构。 下面举一个例子，将这样一个数组调整为大堆：前面学习过了两种调整方法：1. 向上调整；2.向下调整。两种方法都可以将任何一个数组调整为堆。 下面是两种方法的具体实现：1. 向上调整法向上调整法的前提是被调整的元素前面的所有数据已经是一个堆结构了。 利用向上调整法去调整数组的时候，我们从第二个元素开始调整： 代码实现：voidtestAdjustUp(){int arr[]={3,5,2,9,1,8,7};int capacity =sizeof(arr)/sizeof(arr[0]);//计算数组大小for(int i =1; i < capacity; i++){AdjustUp(arr, i);//多次调用向上调整法;}for(int i =0; i < capacity; i++)//可以将调整后的结果打印出来。{printf("%d ", arr[i]);}}具体实现过程：2.向下调整法 向下调整法的前提是调整的元素后面所有元素已经满足堆的性质。所以我们可以从后向前调整。需要注意的是：我们不是从最后一个元素开始调整，我们是从堆中的最后一棵树开始调整的，所以我们需要先找到最后一个根节点。 最后一个根节点下标的计算依据：数组中最后一个元素一定是最后一个根节点的子节点。 r o o t 尾 = ( s i z e − 1 − 1 ) / 2 root_尾 = (size -1-1)/2 root尾​=(size−1−1)/2 注意：size代表数组的大小；size - 1 代表最后一个节点的下标。voidtestAdjustDown(){int arr[]={3,5,2,9,1,8,7};int size =sizeof(arr)/sizeof(arr[0]);//计算数组大小int root =(size -1-1)/2;//找到最后一个根节点的下标最为向下调整根节点参数for(; root >=0; root--){AdjustDown(arr, root, size);//多次调用向下调账法。}int i =0;for(i =0; i < size; i++)//打印调整后的结果{printf("%d ", arr[i]);}}具体实现过程：3.两种方法的比较 经计算，利用向上调整法去创建堆的效率没有利用向下调整法的效率高。向上调整法创建堆的时间复杂度是O(NlogN),向下调整法创建堆的时间复杂度是O(N)。所以通常都是利用向下调整法去将一个数组调整为堆结构

堆的应用

堆排序算法

堆排序算法利用了堆的特点：大堆的堆顶永远是最大的数据，小堆的堆顶永远是最小的数据。
我们利用向下调整的方法，每一次都是将堆顶的元素放在堆的后面，在不断的调整后，原来的数组就会成为一个有序的数组。

voidtestupsort(){int arr[]={3,2,5,4,6,9,7,1,0,8};int capacity =sizeof(arr)/sizeof(arr[0]);int child =(capacity -1-1)/2;for(; child >=0; child--){AdjustDown(arr, child, capacity);}//已经建立好大堆了。int i =0;for(i =0; i < capacity; i++){printf("%d ", arr[i]);}printf("\n");for(int end = capacity-1; end >0; end--){Swap(&arr[0],&arr[end]);AdjustDown(arr,0, end);}for(i =0; i < capacity; i++){printf("%d ", arr[i]);}}

我们利用堆排序来将这样一个数组排成升序：

首先我们先将这个数组调整为一个大堆：

然后利用“得到堆顶的数据”和“向下调整法”来价格呢这个数组排序：

这样可以每一次循环都将堆顶的数组放在适合的位置：

TopK问题

topk

问题即在一个数据集合中找到前K个最大或者最小的元素，一般情况下数据量都很大，所以需要利用堆。

解决问题的方法：

voidPrintTopK(int* a,int n,int k){int* arr =(int*)malloc(sizeof(int)* k);//申请一个K大小的空间作为堆。int i =0;for(i =0; i < k; i++){
        arr[i]= a[i];}//将前面K个元素放入堆中int child =(k -1-1)/2;for(; child >=0; child--){AdjustDown(arr, child, k);//将堆调整为大堆或者小堆}for(i = k; i < n; i++){if(a[i]> arr[0])//依次访问剩下的数据，将他们与堆顶的元素比较。{
            arr[0]= a[i];//如果存在满足要求的值，就将这个值放在堆顶，然后向下调整。AdjustDown(arr,0, k);}}for(i =0; i < k; i++)//打印出要求得到的K个数据。{printf("%d ", arr[i]);}}

该函数有三个参数，第一个参数是一个数组，第二个参数是数组的大小，第三个参数指定了满足要求的数据的个数。

1. 如果寻找的是前K个最大的元素：那么就需要利用前K个数据去建立一个小堆。然后用剩下的元素依次和堆顶的数据比较，如果大于堆顶的元素，就将这个数据置于堆顶，然后向下调整。
2. 如果寻找的是前K个最小的元素：那么就需要利用前K个数据去建立一个大堆。然后用剩下的元素依次和堆顶的数据比较，如果小于堆顶的元素，就将这个数据至于堆顶，然后向下调整。