【数据结构与算法】堆排序(向下和向上调整)、TOP-K问题（超详细解读）（上）

前言：

💥🎈个人主页:Dream_Chaser～ 🎈💥

✨✨专栏:http://t.csdn.cn/oXkBa

⛳⛳本篇内容:c语言数据结构--堆排序，TOP-K问题

堆排序

1.二叉树的顺序结构

顺序存储

       顺序结构存储就是使用数组来存储，一般使用 数组只适合表示完全二叉树 ，因为不是完全二叉树会有空间的浪费。而现实中使用中只有 堆 才会使用数组来存储，关于堆我们后面的章节会专门讲解。 二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

普通的二叉树 是不适合用数组 来存储的，因为 可能会存在大量的空间浪费 。而 完全二叉树更适合使用顺序结构存储 。现实中我们通常把 堆(一种二叉树) 使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段

1.1父节点和子节点的关系

经过观察，可得知父子间下标关系::

父亲下标找孩子:

leftchild   =  parent*2+1

rightchild =  parent*2+2

孩子下标找父亲:

parent = (child-1) / 2

2 堆的概念及结构

堆: 如果有一个关键码的集合K = {k0,k1,k2,…,kn-1}, 把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足ki<=k2i+1且ki<=k2i+2（或满足ki>=k2i+1且ki>=k2i+2），其中i=0,1,2,…，则称该集合为堆。

大堆：将根节点最大的堆叫做最大堆或大根堆，

小堆：将根节点最小的堆叫做最小堆或小根堆。

堆的性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树。

堆的结构:

选择题

1.下列关键字序列为堆的是：（）

A 100 , 60 , 70 , 50 , 32 , 65

B 60 , 70 , 65 , 50 , 32 , 100

C 65 , 100 , 70 , 32 , 50 , 60

D 70 , 65 , 100 , 32 , 50 , 60

E 32 , 50 , 100 , 70 , 65 , 60

F 50 , 100 , 70 , 65 , 60 , 32

答案：A

解析：只有A满足大堆的条件

                100

        60                        70

50           32        65

而其它选项均不满足大堆或小堆的情况。

3. 堆的实现

3.1堆的自定义类型

头文件的引用

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

结构体类型的定义

typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;//数组
  int size;//有效数据个数
  int capacity;//容量
}HP;

3.2堆的向上调整算法

     假设一个数组，前提条件是它已经是一个堆了，这时候需要在数组后插入一个元素，要保证此数组仍是一个堆的结构，那么这时候就需要用到向上调整的算法。

       关于此题，向上调整算法的思想是:

       ①已经建好一个小根堆的前提下，插入一个元素8,要保证此刻的堆仍是一个小堆，那就需要求出节点8的父亲节点的下标，比较此时节点8与其父节点的大小，判断是否需要交换位置。

       ②若目标节点值的大小比其父节点小，那么需要交换目标节点的下标与其父节点的下标。并且将此刻的父节点作为新的目标节点，与其父节点比较，若值依旧比其要小，那就继续交换下标，一直到child下标的值为0结束交换过程。若一开始，目标节点大于其父节点的值，那么证明此刻的堆已经为小堆了，立刻跳出循环停止交换。

void Swap1(HPDataType* n1, HPDataType* n2)//交换函数
{
  HPDataType tmp = *n1;
  *n1 = *n2;
  *n2 = tmp;
}
堆的向上调整(未插入元素8前已是小堆)
void AdjustUp(int* a, int child)
{
  int parent = (child - 1) / 2;
  while (child > 0)
  {
    if (a[child] < a[parent])//小堆
    {
      Swap1(&a[child], &a[parent]);
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}

3.3堆的向下调整算法

       假设我们要删除一组数据里面的元素，未删除之前这组数据满足小堆/大堆的情况，那么该如何删除呢？

方法一:挪动覆盖删除堆顶元素，重新建堆

   可以看到，挪动覆盖，不能保证数组还是堆，父子关系全变了,只能重新建堆，代价极大。那么试下另辟蹊径。

方法二：首尾数据交换，再删除，再调堆

       此题前提条件为,给出一个小堆,要求删除一个元素之后，保证它还是一个小堆。

先说明一下向下调整的基本思想:

       ①先交换此时根节点的值与尾节点的值，接着删除尾节点的值，然后从交换后的根节点开始，选出左右子树中较小的孩子。

       ②让较小的孩子与根节点比较。

若此时的根节点(第一个父节点)的值大于较小的孩子节点，就让较小孩子的位置与根节点的位置互换，就像下图的70。并将较小孩子节点(第二个父节点)的位置作为新的父节点的下标，接着根据此父节点的值比较左右较小孩子的值，满足条件继续向下调整。

若此此时的根节点(第一个父节点)的值小于较小孩子节点的值，则证明此数组已为小堆，不需要调整，此刻跳出while循环。

代码实现:

void Swap2(HPDataType* x1, HPDataType* x2)
{
  HPDataType tmp = *x1;
  *x1 = *x2;
  *x2 = tmp;
}
void AdjustDown(int* a, int n, int parent)
{
  int child = parent * 2 + 1;
  while (child < n)
  {   //先判断是否越界的情况下，再判断两个孩子的大小；
    if (child + 1 < n && a[child] > a[child + 1])//假设左孩子小
    {
      child++;
    }
    if (a[child] < a[parent])
    {
      Swap2(&a[parent], &a[child]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}

3.4堆的初始化

       初始化一个数组，用于存放堆中的元素；capacity表示堆的容量，size表示堆的有效个数。

void HeapInit(HP* php)
{
  assert(php);
  php->a = NULL;
  php->capacity = php->size = 0;
}

3.5堆的插入

 将元素插入到数组中，并使有效个数size++，用于记录堆中元素的有效个数。并且，当插入第一个数的时候,就可以看作是堆。插入第二个元素的时候，假设要建的是小堆，那么就需要与跟节点比较大小，假设根节点大于子节点，那么就需要交换子节点与根节点的位置;若根节点小于子节点，那么就已是小堆不需要变位置。

  这个插入函数需要运用到向上调整算法来帮助建堆，传入的是满二叉树的最后一层的最后一个结点，使其插入数据的时候仍然保持堆的性质。

void HeapPush(HP* php, HPDataType x)
{
  assert(php);
  if (php->size == php->capacity)
  { //如果空间不够则扩容
    int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
    HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));
    if (tmp == NULL)
    {
      perror("malloc fail\n");
      return;
    }
    php->a = tmp;
    php->capacity = newCapacity;
  }
  php->a[php->size] = x;
  php->size++;
    //向上调整
  AdjustUp(php->a, php->size - 1);
}

3.6堆的删除

堆的删除的是堆顶的数据，但如果用覆盖的方式来删掉，那么就会使得父子关系全乱了，还有可能原来的堆直接不是堆了，需要全部元素重新调整顺序建堆，时间复杂度是O(N)。

      那么如果先将堆顶的数据与堆的最后一个节点的数据交换，之后再删除最后一个节点的数据，再通过一次在根节点处的向下调整，那么这时候就可以保持是堆的性质，并且时间复杂度变为O(log(N))

void Swap(HPDataType* a1, HPDataType* a2)
{
  HPDataType tmp = *a1;
  *a1 = *a2;
  *a2 = tmp;
}
void HeapPop(HP* php)
{
  assert(php);
  assert(!HeapEmpty(php));
  Swap(&php->a[0], &php->a[php->size - 1]);
  php->size--;
  AdjustDown(php->a, php->size, 0);
}

3.7获取堆顶元素

       获取堆顶元素，下标对应着数组第一个元素。

HPDataType HeapTop(HP* php)
{
  assert(php);
  assert(!HeapEmpty(php));
  return php->a[0];
}

3.8堆的判空

       判断堆是否为空，空返回true，非空返回false

bool HeapEmpty(HP* php)
{
  assert(php);
  return php->size == 0;
}

3.9返回堆中有效个数

       获取堆的数据个数，即返回堆结构体中的size变量

int HeapSize(HP* php)
{
  assert(php);
  return php->size;
}

3.10堆的销毁

       由于数组的空间是malloc出来的，那么需要free掉数组a的空间。再将a指针置空，并把堆的容量和有效个数的变量赋值成0

void HeapDestroy(HP* php)
{
  assert(php);
  free(php->a);
  php->a = NULL;
  php->capacity = php->size = 0;
}