堆积如山：探索数据结构中的堆-Toy模板网

这篇具有很好参考价值的文章主要介绍了堆积如山：探索数据结构中的堆。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

欢迎来到小K的数据结构专栏的第十一小节，本节将为大家带来堆的详解并带来堆题目的讲解（✨当然也为大家准备了完整的源码）~希望你看完之后，能对你有所帮助，不足请指正！共同学习交流 🐾

✨在讲堆之前我们先看看满二叉树和完全二叉树~

一、满二叉树

我们先来看看满二叉树的特性：

是一颗二叉树
每一颗子树要么没有孩子要么有两个孩子
叶子结点在同一层

✨如下就是一颗满二叉树，少了任何一个叶子结点它就不是（除非直接少了一层–——>）

堆积如山：探索数据结构中的堆

✨从上图划分的层级关系，我们一眼可以看出：

第n层节点数量一定是2^(n-1)个，比如第三次就是2的平方，4个节点
有m层的满二叉树的节点总数为2^m-1个，比方说上图的二叉树节点总数就为2³-1=7个

✨前面我们讲的树、二叉树、二叉查找树都是用链式结构描述的，那还有没有别的方法？答案是当然有~我们今天就用数组结构来描述！！！，既然要用数组来描述，那肯定要知道数组下标和树相应层级的对应关系，第一个1个空间表示第一层，第二个两个代表第二层，以此类推…

堆积如山：探索数据结构中的堆

✨我们就按顺序给满二叉树标号，作为下标，下面我们通过表格来观察一下他们有什么特点：

父	左孩子	右孩子
0	1	2
1	3	4
2	5	6
…	…	…

根据上图，如果已知父节点下标为n，左孩子下标为2ⁿ+1,右孩子下标为2ⁿ+2

那么如果已知左孩子下标为m，父节点下标为（m-1）/2，同理已知右孩子，则父节点下标为（m-2）/2

又观察得知所有左孩子的下标都是奇数，所有右孩子的下标为偶数且（偶数-1）/2==（偶数-2）/2

所以已知孩子下标为m，父节点下标为（m-1）/2

附上下图：

堆积如山：探索数据结构中的堆

二、完全二叉树

完全二叉树的特性：

是一颗二叉树
满二叉树从最下一层从右往左删（删除顺序和阅读顺序相反）
同样满足父节点和孩子节点的下标关系：已知孩子下标为m，父节点下标为（m-1）/2

所以说，满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

✨接下来我们用线性结构来描述一下完全二叉树：

很简单，我们准备一个结构体，里面存一个数组和计算计算数组大小的元素，插入直接按顺序插入

#define MAX 1024
typedef struct three 
{
	int size;
	int all_Binarythree[MAX];
}three;
void init(three* t) 
{
	//memset(t->all_Binarythree, 0, MAX);
	t->size = 0;
}
void insert(three* t, int insertData) {
	t->all_Binarythree[t->size++] = insertData;
}

测试结果

堆积如山：探索数据结构中的堆

✨发现完全吻合，没问题~附上源代码：

堆积如山：探索数据结构中的堆

三、_堆

✨堆:父子之间有序的完全二叉树,如下图就是堆，父节点都小于孩子节点
堆积如山：探索数据结构中的堆

父大于子大顶堆最大堆
父小于子小顶堆最小堆

第一步，✨堆插入

✨堆插入思想：

数组方式进入

往上（父子）线条上作插入排序

先临时保存新数据

循环和父节点比较，如果不冲突，循环结束

如果冲突，当前位置父节点数据覆盖当前位置

临时保存的数据覆盖当前位置

堆插入思想过程

堆积如山：探索数据结构中的堆

✨详解代码：

void insert(myHeap* t, int insertData)
{
	//需要新开内存
	if ((t->size) >= (t->maxSize))
	{
		//计算新开内存
		(t->maxSize) += ((t->maxSize >> 1 > 1) ? (t->maxSize >> 1) : 1);
		//新开内存
		int* pTemp = (int*)malloc(sizeof(int) * (t->maxSize));
		assert(pTemp);
		if (t->pRoot)
		{
			memcpy(pTemp, (t->pRoot), sizeof(int) * (t->size));
			free(t->pRoot);
		}
		t->pRoot = pTemp;
	}

	//insertData放入动态数组中,元素个数加1
	t->pRoot[t->size++] = insertData;

	//循环遍历，父子一条线
	//当前节点下标
	int currentIdx = t->size - 1;
	//父节点下标
	int partentIdx;
	while (1)
	{
		if (currentIdx <= 0) break;
		partentIdx = (currentIdx - 1) / 2;
		if ((t->pRoot[currentIdx]) < (t->pRoot[partentIdx]))
			t->pRoot[currentIdx] = t->pRoot[partentIdx];
		else break;
		//循环继续
		currentIdx = partentIdx;
	}
	//覆盖回来
	t->pRoot[currentIdx] = insertData;
}

第二步，✨堆删除

删除堆顶元素思想：

临时保存堆顶元素

用最后一个元素覆盖堆顶元素

从堆顶开始往下循环

越界循环结束

最小孩子大于最后一个数据结束循环

最小孩子不大于最后一个数据，那就子覆盖父（孩子中最小的接替父节点）

循环结束后，最后一个节点覆盖当前位置

size–

返回堆顶元素

✨删除过程如下：
堆积如山：探索数据结构中的堆

代码详解：

int pop(myHeap* t)
{
	if (0 == t->size) return -666666;
	//1. 临时保存堆顶元素
	int delData = t->pRoot[0];
	if (1 == t->size) 
	{
		t->size = t->maxSize = 0;
		free(t->pRoot);
		t->pRoot = NULL;
		return delData;
	}
	//2. 用最后一个元素覆盖堆顶元素
	t->pRoot[0] = t->pRoot[t->size - 1];
	//3. 从堆顶开始往下循环
	//当前点下标
	int currentIdx = 0;
	//最小孩子下标
	int minchildIdx;
	while (1)
	{
		//越界循环结束
		if ((currentIdx * 2 + 2) > (t->size-1)) break;

		//求最小孩子
		//假设左孩子为最小孩子
		minchildIdx = currentIdx * 2 + 1;
		if (t->pRoot[minchildIdx] > t->pRoot[minchildIdx + 1]) minchildIdx++;

		//最小孩子大于最后一个数据结束循环
		if (t->pRoot[minchildIdx] > t->pRoot[t->size - 1]) break;

		//最小孩子不大于最后一个数据，那就子覆盖父（孩子中最小的接替父节点）
		t->pRoot[currentIdx] = t->pRoot[minchildIdx];

		//循环
		currentIdx = minchildIdx;
	}
	//4. 循环结束后，最后一个节点覆盖当前位置
	t->pRoot[currentIdx] = t->pRoot[t->size - 1];
	//5. size--
	t->size--;
	//6. 返回堆顶元素
	return delData;
}

✨结果演示：

堆积如山：探索数据结构中的堆

我们发现删除之后输出就变得有序了，这似乎和我们接下来将要讲的堆排序有点相似

第三步，✨堆排序

你猜对了，不是相似~就是

✨堆排序：

无序数组用堆插入思想插入

用删除堆顶思想删除

堆积如山：探索数据结构中的堆

✨堆排序代码详解：

void heapSort(int* a, int len) 
{
	int* pTemp = (int*)malloc(sizeof(int) * len);
	assert(pTemp);
	myHeap h;
	init(&h);
	for (int i = 0; i < len; i++)
		insert(&h, a[i]);
	for (int i = 0; i < len; i++)
		pTemp[i] = pop(&h);
	memcpy(a, pTemp, sizeof(int)*len);
	free(pTemp);
}

✨综合代码：

堆积如山：探索数据结构中的堆

第四步，✨堆排序实际应用，Leetcode——215. 数组中的第K个最大元素

✨题目

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

✨ 示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

✨示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

✨ 提示：

1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104

我们这里的思路很简单，就是建立一个大顶堆，然后做k-1次删除，堆顶元素就是我们要找的

✨这里先放一下官方题解

void maxHeapify(int* a, int i, int heapSize) 
{
    int left = i * 2 + 1, right = i * 2 + 2, largest = i;
    if (left < heapSize && a[left] > a[largest]) 
        largest = left;
    if (right < heapSize && a[right] > a[largest]) 
        largest = right;
    if (largest != i)
    {
        int t = a[i];
        a[i] = a[largest], a[largest] = t;
        maxHeapify(a, largest, heapSize);
    }
}

void buildMaxHeap(int* a, int heapSize) 
{
    for (int i = heapSize / 2; i >= 0; --i) 
        maxHeapify(a, i, heapSize);
}

int findKthLargest(int* nums, int numsSize, int k) 
{
    int heapSize = numsSize;
    buildMaxHeap(nums, heapSize);
    for (int i = numsSize - 1; i >= numsSize - k + 1; --i) 
    {
        int t = nums[0];
        nums[0] = nums[i], nums[i] = t;
        --heapSize;
        maxHeapify(nums, 0, heapSize);
    }
    return nums[0];
}