【数据结构】堆（Heap）_数据结构堆

一、堆的概念及结构

1、概念

堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵 完全二叉树的 数组对象。 堆是非线性数据结构，相当于一维数组，有两个直接后继。

如果有一个关键码的集合K = { k₀，k₁，k₂ ，k₃ ，…，kₙ₋₁  }，把它的所有元素按完全二叉树的顺序存储方式存储，在一个一维数组中，并满足：Kᵢ  <= K₂ *ᵢ₊₁  且 Kᵢ  <= K₂ *ᵢ₊₂  (Kᵢ  >= K₂ *ᵢ₊ ₁ 且 Kᵢ  >= K₂ *ᵢ₊₂ ) i = 0，1，2…，则称为小堆 (或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

【大根堆和小根堆】：

根结点最大的堆叫做大根堆，树中所有父亲都大于或等于孩子。

根结点最小的堆叫做小根堆，树中所有父亲都小于或等于孩子。

这个大根堆和小根堆有什么特点呢？

最值总在 0 号位，根据这个特点我们可以做很多事情。比如 TopK 问题 (在一堆数据里面找到前 K 个最大 / 最小的数)。生活中也有很多实例，比如某外卖软件中有上千家店铺，我想选出当地好评最多的十家烤肉店，这时我们不用对所有数据进行排序，只需要取出前 K 个最大 / 最小数据。使用堆排序效率也更高。 

2、性质

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

二、堆的实现

1、堆向下调整算法

给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的 向下调整算法 可以把它调整成一个 小堆 。向下调整算法有一个前提：左右子树必须是一个堆（包括大堆和小堆） ，才能调整。

• 从根节点开始，不断往下调。
• 选出根节点的左右孩子中小的那个孩子，再与父亲进行比较。
• (1)如果父亲小于孩子，就不需处理了，整个树已经是小堆了。
• (2) 如果父亲大于孩子，就跟父亲交换位置，并将原来小的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。

int array[] = {27,15,19,18,28,34,65,49,25,37}; // 根节点的左右子树都是小堆

// 向下调整算法 -- 调成小堆，把大的节点往下调整
void AdjustDown(int* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		// 判断右孩子是否存在 选出左右孩子中小的那个
		if (child + 1 < size && a[child + 1] < a[child])
		{
			++child;
		}
 
		// 孩子跟父亲比较
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

【时间复杂度】我们以满二叉树计算，最坏情况下，向下调整算法最多进行满二叉树的高度减 1 次比较，则说明向下调整算法最多调整满二叉树的高度减 1 次，n 个节点的满二叉树高度为 log₂(n+1)，估算后所以时间复杂度为 O(log₂n)。 

2、堆的创建

给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但还不是一个堆，现在我们可以通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

为什么要倒着调整呢？

因为这样我们可以把倒数第一个非叶子节点的子树的左右子树看成是一个 (大 / 小) 堆，满足向下调整的前提条件，这时才能去使用向下调整算法。 

// 建大堆
int a[] = {1,5,3,8,7,6};

建堆过程演示（以建大堆为例）：从下到上，依次遍历完所有非叶子节点，分别对每个子树进行向下调整。依次进行每一步，方框内的树进行向下调整为一个大堆。

调换 1 和 8 的位置时，8 的其左子树构成的递归结构被破坏。因此，在每一次发生元素交换时，都需要递归调用重新构造堆的结构。

#include <stdio.h>
#include <stdlib.h>
 
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
// 向下调整算法 -- 建大堆，把小的节点往下调整
void AdjustDown(int* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		// 判断右孩子是否存在 选出左右孩子中大的那个
		if (child + 1 < size && 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 HeapSort(int* a, int n)
{
	// O(N)
    // botto-top(自底向上)，依次遍历完所有子树，分别对其进行调整
	for (int i=((n-1)-1)/2; i>=0; i--) // 从最后一个叶子节点的父亲的下标开始
	{
		AdjustDown(a, n, i);
	}
 
    // 升序
	// O(N*logN)
	int end = n - 1; // 记录堆中最后一个元素的下标
	while (end > 0)
	{
		Swap(&a[0], &a[end]); // 将堆顶元素和堆中最后一个元素交换，把最大的数(堆顶)放到最后
		AdjustDown(a, end, 0);
		--end;
	}
}

【拓展】堆的创建（采用向上调整法）

下面给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但不是一个堆，我们需要通过向上调整算法把它构建成一个堆。如果根节点左右子树不是一个 (大 / 小) 堆，我们应该怎么调整呢？

我们从上到下，从第一个节点（也就是根节点）的左孩子开始，依次遍历完所有节点，分别对每个节点进行向上调整，一直到最后一个节点，就可以建成一个 (大 / 小) 堆。

我们把数组中的第一个元素看作是一个堆，剩余的元素依次插入到这个堆中。这跟堆的插入接口原理相同，就是向上调整。

如果堆的创建过程使用向上调整算法，那么每次插入一个新元素时都需要进行一次向上调整操作，以确保新插入的元素能够满足堆的性质。

【时间复杂度】

        假设堆中已经有 n 个元素，那么堆的高度 h = log₂(n+1)，在插入一个新元素的过程中，需要进行的向上调整操作次数为 h-1，则 h = log₂(n+1) - 1，该操作的时间复杂度为O(log₂n)。需要注意的是，这个时间复杂度是针对单次 “向上建堆” 操作而言的。如果需要对一个无序数组进行完整的堆排序，则需要进行 n/2 次 “向上建堆” 操作，那么整个堆排序的时间复杂度为 O(nlog n)。所以，如果使用向上调整算法来创建堆排序，那么堆的创建过程的时间复杂度为 O(n*log₂n)。

       结论： 使用向上调整算法创建堆需要进行多次调整操作，而使用向下调整算法只需要进行一次调整操作。因此，从实际操作的角度来看，使用向下调整算法创建堆更为高效。同时，向下调整算法也更为直观，容易理解和实现。因此，在实际应用中，一般会选择使用向下调整算法来创建堆。

【堆排序】

利用 堆删除 思想来进行排序（后文有介绍）

建堆和堆删除中都用到了 向下调整 ，因此掌握了向下调整，就可以完成堆排序。

（1）升序 -- 建大堆

【思考】排升序，建小堆可以吗？-- 可以（但不推荐）。

⚪首先对 n 个数建小堆，选出最小的数，接着对剩下的 n-1 个数建小堆，选出第二小的数，不断重复上述过程。

【时间复杂度】建 n 个数的堆时间复杂度是 O(N)，所以上述操作时间复杂度为 O(N²)，效率太低，关系变得杂乱，尤其是当数据量大的时候，效率就更低。同时堆的价值也没有被体现出来，这样不如用直接排序。

⚪【最佳方法】排升序，因为数字依次递增，需要找到最大的数字，得建大堆。

首先对 n 个数建大堆。将最大的数（堆顶）和最后一个数交换，把最大的数放到最后。前面 n-1 个数的堆结构没有被破坏（最后一个数不看作在堆里面的），根节点的左右子树依然是大堆，所以我们进行一次向下调整成大堆即可选出第 2 大的数，放到倒数第二个位置，然后重复上述步骤。

【时间复杂度】：建堆时间复杂度为 O(N)，向下调整时间复杂度为 O(log₂N)，这里我们最多进行N-2 次向下调整，所以堆排序时间复杂度为 O(N*log₂N)，效率相较而言是很高的。

（2）降序 -- 建小堆（与建大堆同理）

【最佳方法】排降序，因为数字越来越小，需要找到最小的数字，得建小堆。

首先对 n 个数建小堆。将最小的数（堆顶）和最后一个数交换，把最小的数放到最后。前面 n-1 个数的堆结构没有被破坏（最后一个数不看做堆里面的），根节点的左右子树依旧是小堆，所以我们进行一次向下调整成小堆即可选出第2小的数，放到倒数第二个位置，然后重复上述步骤。
【时间复杂度】：建堆时间复杂度为 O(N)，向下调整时间复杂度为 O(log₂N)，这里我们最多进行N-2 次向下调整，所以堆排序时间复杂度为O(N*log₂N)，效率相较而言是很高的。

3、建堆时间复杂度

等比数列求和公式：

建堆要从倒数第一个非叶子节点开始调整，也即是从倒数第二层开始调，可得出时间复杂度公式：
                        T ( n ) = ∑ ( 每 层 节 点 数 ∗ ( 堆 的 高 度 − 当 前 层 数 ) ) 

建堆的时间复杂度为O(N)。（向下调整算法）

4、堆的插入

5、堆的删除

6、堆的代码实现

（1）文件的创建

• test.c（主函数、测试堆各个接口功能）
• Heap.c（堆接口函数的实现）
• Heap.h（堆的类型定义、接口函数声明、引用的头文件）

（2）Heap.h 头文件代码

// Heap.h
#pragma once
 
#include <stdio.h>
#include<stdlib.h>  // malloc, free
#include <assert.h> // assert
#include <stdbool.h> // bool
#include<string.h>  // memcpy
 
typedef int HPDataType;
 
typedef struct Heap
{
 HPDataType* a; // 指向动态开辟的数组
 int size; // 数组中有效元素个数
 int capacity; // d容量
}Heap;
 
// 交换函数
void Swap(HPDataType* p, HPDataType* q);
// 向下调整函数（调成大堆，把小的往下调）
void AdjustDown(HPDataType* a, int size, int parent);
// 向上调整函数（调成大堆，把大的往上调）
void AdjustUp(HPDataType* a, int child);
// 堆的打印
void HeapPrint(Heap* hp);
 
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* arr, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);

（3）接口的实现（以大堆为例）

I.堆的创建（初始化）

堆的初始化一般是使用数组进行初始化的，还需要先实现一个向下调整算法。

//交换
void Swap(HPDataType* p, HPDataType* q)
{
	HPDataType tmp = *p;
	*p = *q;
	*q = tmp;
}
 
// 向下调整（调成大堆，把小的往下调）
void AdjustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		//选出左右孩子中大的那个
		if (child + 1 < size && 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 HeapCreate(Heap* hp, HPDataType* arr, int n)
{
	assert(hp);//断言
 
	hp->a = (HPDataType*)malloc(sizeof(HPDataType) * n);//动态开辟n个空间
	if (hp->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
 
	memcpy(hp->a, arr, sizeof(HPDataType) * n);//把给定数组的各元素值拷贝过去
	hp->size = hp->capacity = n;
 
	//建堆（建大堆）
	int parent = ((hp->size - 1) - 1) / 2; //倒数第一个非叶子节点下标
	for (int i = parent; i >= 0; i--)
	{
		AdjustDown(hp->a, hp->size, i);
	}
}

II.堆的打印 

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

III.堆的销毁

// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a); // 释放动态开辟的空间
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

IV.堆的插入

堆的插入数据不分头插、尾插。将数据插入后，原来堆的属性不变。先放在数组的最后一个位置，再进行向上调整。堆的插入，首先需要实现一个向上调整算法。

//向上调整（调成大堆，把大的往上调）
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 = (child - 1) / 2;
		}
        // 如果孩子小于父亲，说明已经为大堆了，停止调整
		else
		{
			break;
		}
	}
}
 
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
 
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : (hp->capacity) * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		hp->a = tmp;
		hp->_capacity = newcapacity;
	}
 
    // 插入元素
	hp->a[hp->size] = x;
	hp->size++;
 
	AdjustUp(hp->a, hp->size - 1); // 从插入的元素开始，进行向上调整，保持它依然是堆
}

注意：这里的 while 括号里的条件不能写成 (parent >= 0)，因为 parent 在这里不会小于 0。（假设child 为 0，则 parent = (0-1) / 2 = 0）。

V.堆的删除

删除堆顶元素，删除后保持它依然是堆。

// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
    assert(!HeapEmpty(hp)); // 堆不能为空
 
	Swap(&(hp->a[0]), &(hp->a[hp->size - 1])); // 将堆顶元素和最后一个元素交换
	hp->size--; // 删除堆中最后一个元素
 
    // 从根节点开始，对剩下元素进行向下调整成大堆，保持它依然是堆
	AdjustDown(hp->a, hp->size, 0); 
}

VI.取堆顶元素

// 取堆顶的数据（最值）
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp)); // 堆不能为空
 
	return hp->a[0];
}

VII.堆的数据个数

// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
 
	return hp->size;
}

VIII.堆的判空

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

// 堆的判空
bool HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

（4）代码整合

// Heap.c
#include "Heap.h"
 
//交换
void Swap(HPDataType* p, HPDataType* q)
{
	HPDataType tmp = *p;
	*p = *q;
	*q = tmp;
}
 
// 打印
void HeapPrint(Heap* hp)
{
	assert(hp);
 
	for (int i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}
 
// 向下调整（调成大堆，把小的往下调）
void AdjustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		//选出左右孩子中大的那个
		if (child + 1 < size && 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 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 = (child - 1) / 2;
		}
        // 如果孩子小于父亲，说明已经为大堆了，停止调整
		else
		{
			break;
		}
	}
}
 
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* arr, int n)
{
	assert(hp);//断言
 
	hp->a = (HPDataType*)malloc(sizeof(HPDataType) * n);//动态开辟n个空间
	if (hp->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
 
	memcpy(hp->a, arr, sizeof(HPDataType) * n);//把给定数组的各元素值拷贝过去
	hp->size = hp->capacity = n;
 
	//建堆（建大堆）
	int parent = ((hp->size - 1) - 1) / 2; //倒数第一个非叶子节点下标
	for (int i = parent; i >= 0; i--)
	{
		AdjustDown(hp->a, hp->size, i);
	}
}
 
// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a); // 释放动态开辟的空间
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}
 
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
 
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : (hp->capacity) * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		hp->a = tmp;
		hp->_capacity = newcapacity;
	}
 
    // 插入元素
	hp->a[hp->size] = x;
	hp->size++;
 
	AdjustUp(hp->a, hp->size - 1); // 从插入的元素开始，进行向上调整，保持它依然是堆
}
 
// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
    assert(!HeapEmpty(hp)); // 堆不能为空
 
	Swap(&(hp->a[0]), &(hp->a[hp->size - 1])); // 将堆顶元素和最后一个元素交换
	hp->size--; // 删除堆中最后一个元素
 
    // 从根节点开始，对剩下元素进行向下调整成大堆，保持它依然是堆
	AdjustDown(hp->a, hp->size, 0); 
}
 
// 取堆顶的数据（最值）
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp)); // 堆不能为空
	return hp->a[0];
}
 
// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}
 
// 堆的判空
bool HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

（5）程序运行效果

三、堆的应用

【TOP-K问题】 

TOP-K 问题：即求数据结合中前 K 个最大的元素或者最小的元素，一般情况下数据量都比较大。

在生活中，也有不少例子：班级前 10 名、世界 500 强、富豪榜等。

方法一：对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了（可能数据都不能一下子全部加载到内存中）。

排序 --【时间复杂度为】：O(N*logN)。

方法二：建一个 N 个数的堆(优先级队列)，不断选数，选出前 K 个。

【时间复杂度】： O(N+K*log(N))

 假设 N 是十亿，显然前两个方法都不适用。

// test.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
 
void PrintTopK(int* a, int n, int k)
{
	// 1、建堆 -- 用a中前k个元素建堆(0~k-1)
	int* kMinHeap = (int*)malloc(sizeof(int) * k);
	assert(kMinHeap);
	for (int i = 0; i < k; ++i)
	{
		kMinHeap[i] = a[i];
	}
	for (int i = (k - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(kMinHeap, k, i);
	}
 
	// 2、将剩余n-k个元素依次与堆顶元素交换，不满则则替换(k~n)
	for (int j = k; j < n; ++j)
	{
		if (a[j] > kMinHeap[0])
		{
			kMinHeap[0] = a[j];
			AdjustDown(kMinHeap, k, 0);
		}
	}
	for (int i = 0; i < k; ++i)
	{
		printf("%d ", kMinHeap[i]);
	}
	printf("\n");
}
 
void TestTopk()
{
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
 
    // 创建随机数种子
	srand((unsigned int)time(0));
	for (int i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000; // 生成随机数
	}
 
    // 如果找出这10个数，说明TOP-K算法是正确的
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[120] = 1000000 + 5;
	a[99] = 1000000 + 6;
	a[0] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
	PrintTopK(a, n, 10);
}