【数据结构】二叉树之堆的实现-阿里云开发者社区

一、堆的概念及结构

1.1 堆的概念

从以上概念中，我们可以提炼出以下三个信息：

堆总是一种完全二叉树，其采用顺序存储方式
堆中某个节点的值总是不大于(大堆)或不小于(小堆)其父节点的值；
当序列只有一个元素时，既可以是大堆也可以是小堆

1.2 堆的结构

为什么要采用顺序存储方式？

由于堆总是一颗完全二叉树，因此数组便成为了用来存储堆的最好方式。数组最大的优点就是支持随机访问，在数组中，只要我们知道其中一个结点的下标，便可以通过完全二叉树父结点和孩子结点的编号关系，快速定位到其父结点或孩子结点。下面列出了小/大根堆的结构及表示：

由于采用顺序存储，堆结构的代码表示就与顺序表基本一致，如下：

typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}HP;

二、堆的操作

2.1 堆的插入与向上调整（以小堆为例）

堆的插入就是将一个元素插入到堆的尾部，如下图所示。

但是我们可以发现，如果直接这样插入显然是不行的，插入后小堆的结构就被破坏了，所以我们需要对插入后的完全二叉树调整为新的小堆，这里需要用到的就是向上调整算法。

向上调整算法

所谓向上调整算法，就是将当前结点从下往上一步步调整直到形成小堆，大致过程如下：

可以看到，结点[5]通过两次向上交换移动到了堆顶，此时的树又变为了小根堆。
首先我们先比较末尾插入的新结点[5]与其父结点[30]的大小，根据小堆小的在堆顶，大的在堆底的特性可知：当父结点比插入结点大时，我们需要进行一次交换以调整堆的结构；而如果父结点比插入结点小时，说明插入结点并没有破坏小堆的结构，依然符合小堆的特性，无需进行调整。
那么，是不是一次调整后就结束了呢？当然不是。进行一次调整后我们只能保证调整过的那一部分符合小堆的特性，毕竟只根据新结点<=父亲结点以及父结点<=爷爷结点两个条件，我们并不能保证新结点>=爷爷结点。如果新结点<=爷爷结点，则我们进行一次调整后依旧不是小堆，新结点还需向上调整。由此可以看出，向上调整算法是个不断向上交换调整的算法。
算法实现思路：由以上分析，我们需要通过循环控制堆的向上调整。用两个变量parent和child分别代表父结点和孩子结点的下标，在循环过程中比较父结点和孩子结点的大小，当父>结点孩子结点时，我们就交换父子结点，然后将parent作为新的child，parent改为爷爷结点的下标，形成迭代用于下次循环比较。
循环结束条件：当父结点<=孩子结点时或者child<=0时说明小堆调整完毕，结束循环。
注意事项：使用向上调整算法时必须确保原来的树已经是小/大堆，否则无法保证调整后的树是小/大堆。

void Swap(HPDataType* p1, HPDataType* p2)
{
  HPDataType tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
void AdjustUp(HPDataType* a, int child)
{
  int parent = (child - 1) / 2;
  while (child > 0)
  {
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      child = parent;
      parent = (parent - 1) / 2;
    }
    else
      break;
  }
}
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*)malloc(sizeof(HPDataType) * newcapacity);
    if (tmp == NULL)
    {
      perror("malloc fail");
      exit(-1);
    }
    php->a = tmp;
    php->capacity = newcapacity;
  }
  php->a[php->size] = x;
  php->size++;
  AdjustUp(php->a, php->size - 1);
}

2.2 堆的删除与向下调整（以大堆为例）

有插入就自然有删除。堆的删除是删除堆顶的数据，如下：

那么问题就来了，堆顶数据删除后，新的堆顶是什么呢？是模仿顺序表一样后续元素全部往前移动吗？如下：

我们发现，如果将后续元素全部前移，原本的孩子可能变为父亲，父亲可能会变成孩子，整个堆的关系就紊乱了，堆的结构就会被完全破坏，需要重新建堆，成本过高。因此我们需要另辟蹊径。

我们的做法是将堆顶的数据跟最后一个数据交换，然后删除数组最后一个数据，这样就实现了堆顶数据的删除，并且不会影响堆的结构。如下：

通过这种方法，我们发现堆顶的左右子树均保持着原先大堆的结构不变，只有交换上来的堆顶元素不满足堆的条件。换句话说，我们只需对堆顶元素的位置进行调整即可，调整的方式就是接下来要介绍的向下调整算法

向下调整算法

向上调整是从下往上进行调整，那么向下调整就是从上往下进行调整。大致过程如下：

经过两次向下调整，堆顶元素[35]来到了合适的位置，此时的树即为大堆
我们知道在调整之前除了根结点之外，左右两颗子树均为大堆。根据大堆大的在堆顶，小的在堆底的特性可知：当堆顶元素比其中一个孩子小时，我们就需要进行交换以调整大堆的结构；而如果堆顶元素比所有孩子结点小时，说明堆顶元素的位置符合大堆的结构，无需进行调整。
还有最后一个问题：当我们需要进行调整时，堆顶元素要和哪个孩子结点进行交换呢？左孩子？亦或者是右孩子？很简单，既然是大堆，那我们只要选出进行交换即可（小堆相反），这样就能保证交换后新的堆顶元素一定大于两个孩子结点。
与向上调整算法同理，向下调整算法也是要不断向下进行调整，直到不再需要交换。
算法实现思路：因此我们依然通过循环控制堆的向下调整。用两个变量parent和child分别代表父结点和孩子结点的下标，parent初值为0表示堆顶元素。进入while循环后我们首先需要比较左右孩子的大小，然后找出较大值与parent进行比较，如果parent大于这个较大值，则说明此时树已经符合大堆的结构，无需进行调整；如果parent小于这个较大值则向下进行交换，然后更新parent和child，进行迭代。
循环结束条件：当父结点孩子结点较大值或者(元素个数)时说明大堆调整完毕，结束循环。
注意事项：使用向下调整算法时必须确保其左右子树已经是小/大堆，否则无法保证调整后的树是小/大堆。

void Swap(HPDataType* p1, HPDataType* p2)
{
  HPDataType tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
void AdjustDown(HPDataType* a, int n, int parent)
{
  int child = parent * 2 + 1;
  while (child < n)
  {
    if (child + 1 < n && a[child + 1] < a[child])
      child++;
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
      break;
  }
}
void HeapPop(HP* php)
{
  assert(php);
  assert(php->size > 0);
  Swap(&php->a[0], &php->a[php->size - 1]);
  php->size--;
  AdjustDown(php->a, php->size, 0);
}

2.3 向上调整建堆

Q：给你一个数组如下，要求设计算法将这个数组构建为一个堆。我们该怎么做呢？

int array[] = {27,15,19,18,28,34,14};
• 1

way1：首先我们知道，当数组只有一个元素时，其不仅可以看作大堆也可以看作小堆。那么就有一个很简单的思路，先初始化一个空堆，然后将数组第一个元素放入作为一个堆，然后遍历其他元素往堆的末端插入进行向上调整算法即可。下面是构建小堆过程以及代码：

void HeapInit(HP* php)
{
  assert(php);
  php->a = NULL;
  php->size = php->capacity = 0;
}
void HeapInitArray(HP* php, int* a, int n)
{
  assert(php);
  assert(a);
  php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
  if (php->a == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  php->size = n;
  php->capacity = n;
  memcpy(php->a, a, sizeof(HPDataType) * n);
  for (int i = 1; i < n; i++)
    AdjustUp(php->a, i);
}
void HeapPrint(HP* php)
{
  assert(php);
  for (int i = 0; i < php->size; i++)
  {
    printf("%d ", php->a[i]);
  }
  printf("\n");
}
void HeapDestory(HP* php)
{
  assert(php);
  free(php->a);
  php->a = NULL;
  php->size = php->capacity = 0;
}
int main()
{
  HP php;
  HeapInit(&php);
  HPDataType array[] = { 27,15,19,18,28,34,14 };
  HeapInitArray(&php, array, sizeof(array) / sizeof(HPDataType)); 
    //根据array数组创建堆
  HeapPrint(&php);
  HeapDestory(&php); //不再使用销毁堆
  return 0;
}

2.4 向下调整建堆

除了使用向上调整建堆，我们也可以使用向下调整算法将下面的数组构建为一个堆。实际上，我们会更倾向于使用向下调整算法来建堆，下面我们会通过对比两种算法的时间复杂度进行分析。

int array[] = {27,15,19,18,28,34,14};

不同于向上调整的是，向下调整不再是边插入边调整，而是直接将整个数组作为一个完全二叉树，然后逐元素进行调整，如下：

在之前，我们说过使用向下调整算法有一个前提：左右子树必须是个堆。那么我们显然不能从前往后进行调整，因为堆顶的左右子树不是一个堆。为了保证调整某个元素时它的左右子树已经是堆了，我们应该从后往前逐元素进行向下调整。

那么，**第一个需要调整的元素是谁呢？**叶子节点没有左右子树，故不需要进行调整，我们应该从第一个非叶子结点开始向下调整调整，即下标为(n-1-1)/2的元素(n为元素个数)。就这样不断调整到根结点即可完成堆的构建。下面是向下调整构建大堆的过程和代码：

void HeapInit(HP* php)
{
  assert(php);
  php->a = NULL;
  php->size = php->capacity = 0;
}
void HeapInitArray(HP* php, int* a, int n)
{
  assert(php);
  assert(a);
  php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
  if (php->a == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  php->size = n;
  php->capacity = n;
  memcpy(php->a, a, sizeof(HPDataType) * n);
  for(int i = (n - 1 - 1) / 2; i >= 0; i--)
    AdjustDown(a, n, i);
}
void HeapPrint(HP* php)
{
  assert(php);
  for (int i = 0; i < php->size; i++)
  {
    printf("%d ", php->a[i]);
  }
  printf("\n");
}
void HeapDestory(HP* php)
{
  assert(php);
  free(php->a);
  php->a = NULL;
  php->size = php->capacity = 0;
}
int main()
{
  HP php;
  HeapInit(&php);
  HPDataType array[] = { 27,15,19,18,28,34,14 };
  HeapInitArray(&php, array, sizeof(array) / sizeof(HPDataType)); 
    //根据array数组创建堆
  HeapPrint(&php);
  HeapDestory(&php); //不再使用销毁堆
  return 0;
}

2.5 向上调整VS向下调整

上面我们介绍了两种建堆方法，那么肯定会有许多小伙伴有所疑问：这两种建堆算法在效率上是相差无几还是有所优劣呢？下面我们就来分析分析它们的时间复杂度

特别说明：因为堆是完全二叉树，而满二叉树也是完全二叉树，因此上面为了简化使用满二叉树来分析复杂度(时间复杂度本来看的就是近似值，多几个结点并不影响最终结果)

通过上面的计算，我们可以得出：向上调整建堆的时间复杂度为O(N)，向下调整算法时间复杂度为O(NlogN)。

我们明显可以看出**【向下调整建堆】优于【向上调整建堆】**，具体表现在向下调整随着层数增加每个结点的调整次数会递减，而向上调整正好相反。层数越高需要调整的结点越多，因此总体来看向下调整建堆的总调整次数会更少。我们后面的建堆均会使用向下调整来建堆。

三、堆的应用

学了这么多堆的概念与操作，可能会有小伙伴们有疑问，我们如此费劲心思来创建的堆究竟有什么用呢？下面，我们就来介绍一下有关堆的两个应用：堆排序和TopK问题。

3.1 堆排序

所谓堆排序，就是利用大堆堆顶最大，小堆堆顶最小的思想来进行排序。假设有如下数组：

现要求我们使用堆排序对其进行升序排列，我们该怎么做呢？建大堆还是小堆呢？

int array[] = {27,15,19,18,28,34,14};

由于是升序，我们首先想到的就是建小堆：

建完小堆后我们就能将最小的数移动到数组前面，但当我们再想调整第二小的数时就碰到了一个问题：如果将数组剩余的元素看作堆，堆的关系就全乱了，我们需要重新建堆：

据此我们可以得出：如果我们采用升序建小堆的方法，每次选数都要重新建堆，而建堆的时间复杂度最快为，共有N个数，整体排序的时间复杂度就为。这效率肯定是不符合堆高端的身份的，不要急，我们再来看看升序建大堆的方法

大堆的特点是堆顶元素最大，即我们建完大堆后最大的元素就到了我们数组的最前方：

建完堆后我们要做什么呢？由于我们进行的是升序排列，所以我们先将堆顶的【34】和数组尾的【14】进行交换，然后进行下一次选数。这时除了根结点【14】之外，左右子树依然还是大堆，因此只需对堆顶元素【14】进行向下调整即可将剩余的数重新变为大堆。是不是很熟悉？没错，这里用到的思路和堆的删除是类似的

对上面整个数组进行堆排序的具体过程和代码如下：

void HeapSort(int* a, int n)
{
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(a, n, i);
  }
  int end = n - 1;
  while (end > 0)
  {
    Swap(&a[0], &a[end]);
    AdjustDown(a, end, 0);
    --end;
  }
}

那么，升序建大堆的时间复杂度是多少呢？

参照代码分析：首先向下调整建堆的时间复杂度为O(N)，然后每次交换后对堆顶元素进行向下调整的时间复杂度为O(logN)，共循环N-1次，因此整合后的时间复杂度为O(N+NlogN)。由于N相对NlogN来说影响甚小，因此堆排序最终的时间复杂度为O(NlogN)

最后再来回到我们最初的问题：升序建大堆还是小堆？答案想必已经显而易见了，我们直接给出结论：

升序排列建大堆

降序排列建小堆

3.2 TopK算法

介绍完堆排序后，我们再来看看另一个与堆息息相关的问题：TopK问题

所谓TopK，即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大

例如：统计专业前10名、世界500强、富豪榜、游戏战力排行榜中前100的活跃玩家等。

对于此类问题，我们第一时间想到的可能就是进行排序了，将所有数据进行排序后取前K个就好了，这有什么难的？确实，如果数据量较小时可以这么做；但是，如果数据量非常大，排序的方法就不太可取了(毕竟数据可能都不能一下子全部加载到内存中，更别谈排序了)。

TopK问题的基本思路如下：

1、将数据集合前K个数据建堆

求最大K个–>建小堆
求最小K个–>建大堆

2、用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

TopK问题的举例分析如下：

例如我们要求最大的K个数，则我们应该建小堆，小堆中的元素就是当前最大的K个数。由于小堆的堆顶最小，因此如果后面的数据大于堆顶元素，我们就需要将这个数据替换进堆，和谁替换呢？当然是和堆中最小的数据也就是堆顶数据替换，然后再向下调整为小堆即可。

void Swap(HPDataType* p1, HPDataType* p2)
{
  HPDataType tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
void AdjustDown(HPDataType* a, int n, int parent)
{
  int child = parent * 2 + 1;
  while (child < n)
  {
    if (child + 1 < n && a[child + 1] < a[child])
      child++;
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
      break;
  }
}
void CreateNDate()
{
  int n = 10000;
  srand(time(0)); //设置随机种子，用随机数生成数据
  const char* file = "data.txt";
  FILE* fin = fopen(file, "w");
  if (fin == NULL) //打开文件失败
  {
    perror("fopen error");
    return;
  }
  for (int i = 0; i < n; ++i)
  {
    int x = rand() % 1000000;
    fprintf(fin, "%d\n", x); //存入文件
  }
  fclose(fin);
  fin = NULL;
}
void PrintTopK(const char* filename, int k)
{
  FILE* fout = fopen(filename, "r");
  if (fout == NULL)
  {
    perror("malloc fail");
    return;
  }
  int* minheap = (int*)malloc(sizeof(int) * k);
  if (minheap == NULL)
  {
    perror("malloc fail");
    return;
  }
  for (int i = 0; i < k; i++)
  {
    fscanf(fout, "%d", &minheap[i]);
  }
  for (int i = (k - 2) / 2; i >= 0; --i)
  {
    AdjustDown(minheap, k, i);
  }
  int x = 0;
  while (fscanf(fout, "%d", &x) != EOF)
  {
    if (x > minheap[0])
    {
      minheap[0] = x;
      AdjustDown(minheap, k, 0);
    }
  }
  for (int i = 0; i < k; i++)
  {
    printf("%d ", minheap[i]);
  }
  printf("\n");
  free(minheap);
  fclose(fout);
}
int main()
{
    CreateNDate();
    PrintTopK("data.txt",5);
    return 0;
}

TopK问题的复杂度分析如下：

首先，我们需要申请一个大小为K的空间来存放堆，空间复杂度为O(K)。其次忽略造数不谈，建堆的时间复杂度为O(K)，每次替换后向下调整的时间复杂度为O(logK)，最坏需要调整N-K次。因此忽略影响较小者后时间复杂度为O(NlogK)。

四、堆的实现

4.1 堆的初始化

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

4.2 堆的销毁

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

4.3 数组建堆

void HeapInitArray(HP* php, int* a, int n)
{
  assert(php);
  assert(a);
  php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
  if (php->a == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  php->size = n;
  php->capacity = n;
  memcpy(php->a, a, sizeof(HPDataType) * n);
  for(int i = (n - 1 - 1) / 2; i >= 0; i--)
    AdjustDown(a, n, i);
}

4.4 堆的判空

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

4.5 取堆顶元素

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

4.6 堆的删除

void HeapPop(HP* php)
{
  assert(php);
  assert(php->size > 0);
  Swap(&php->a[0], &php->a[php->size - 1]);
  php->size--;
  AdjustDown(php->a, php->size, 0);
}

4.7 堆的插入

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*)malloc(sizeof(HPDataType) * newcapacity);
    if (tmp == NULL)
    {
      perror("malloc fail");
      exit(-1);
    }
    php->a = tmp;
    php->capacity = newcapacity;
  }
  php->a[php->size] = x;
  php->size++;
  AdjustUp(php->a, php->size - 1);
}

4.8 打印堆

void HeapPrint(HP* php)
{
  assert(php);
  for (int i = 0; i < php->size; i++)
  {
    printf("%d ", php->a[i]);
  }
  printf("\n");
}

本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言，小羊一定认真修改，写出更好的文章~~

【数据结构】二叉树之堆的实现

一、堆的概念及结构

1.1 堆的概念

1.2 堆的结构

二、堆的操作

2.1 堆的插入与向上调整（以小堆为例）

2.2 堆的删除与向下调整（以大堆为例）

2.3 向上调整建堆

2.4 向下调整建堆

2.5 向上调整VS向下调整

三、堆的应用

3.1 堆排序

3.2 TopK算法

四、堆的实现

4.1 堆的初始化

4.2 堆的销毁

4.3 数组建堆

4.4 堆的判空

4.5 取堆顶元素

4.6 堆的删除

4.7 堆的插入

4.8 打印堆

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【数据结构】二叉树之堆的实现

一、堆的概念及结构

1.1 堆的概念

1.2 堆的结构

二、堆的操作

2.1 堆的插入与向上调整（以小堆为例）

2.2 堆的删除与向下调整（以大堆为例）

2.3 向上调整建堆

2.4 向下调整建堆

2.5 向上调整VS向下调整

三、堆的应用

3.1 堆排序

3.2 TopK算法

四、堆的实现

4.1 堆的初始化

4.2 堆的销毁

4.3 数组建堆

4.4 堆的判空

4.5 取堆顶元素

4.6 堆的删除

4.7 堆的插入

4.8 打印堆

热门文章

最新文章

相关课程

相关电子书