＜数据结构＞NO6.堆的实现|堆的应用

本文主要是介绍＜数据结构＞NO6.堆的实现|堆的应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

🐇本文用到的所有代码都放在我的gitee仓库了🐇
syseptember的gitee仓库https://gitee.com/syseptember/data-structure/tree/4f0b1f9f56e3b0bee72fa0563c23a6917b3252e8/Heap/Heap

堆的概念

堆的实现

堆的应用

堆排序

时间复杂度分析

TopK问题

时间复杂度

堆的概念

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象

📚定义：

📚性质：
①堆中某个结点的值总是不大于或不小于其父结点的值；
②堆总是可以看成一颗完全二叉树;

❗注意：堆的物理结构是数组，逻辑结构是完全二叉树,所以我们可以根据定义顺序表同样定义堆。

💭练习题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

🔑解析：答案为A

堆的实现

堆实现的功能主要有

插入(HeapPush)
删除(HeapPop)
取堆顶元素(HeapTop)
取堆数据个数(HeapSize)
判断堆是否为空(HeapEmpty)

❗注意：堆的插入是在数组末尾插入元素，堆的删除是删除数组首元素（完全二叉树的根）

①堆的结构

typedef int HPDataType;
//由于堆属于完全二叉树，因此可以使用数组存放堆的节点
//堆的结构和顺序表一样
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;

②堆的初始化

//堆的初始化
void HeapInit(Heap* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;
}

③堆的销毁

//堆的销毁
void HeapDestroy(Heap* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}

④堆的插入
插入时需要判断堆是否需要扩容，其次再在数组末尾插入元素，插入元素后有可能不满足堆的性质所以需要经过调整算法将插入的数据移动到合适的位置保持堆的结构。如

我们将插入的数据向上移动，最后使得该结构变为一个堆。最多会将插入的数据调整h-1次，也就是log(n+1)-1，所以时间复杂度为O(logN)
📚定义：称这种算法为向上调整算法(AdjustUp)。
现在我们来研究向上调整算法

向上调整算法
❓ 请思考：在堆结构中，父节点和子节点之间有什么关系？
🔑解析：堆的物理结构是数组，所以我们可以找出它们下标之间的关系
很容易发现如下关系：
🔍已知子节点下标child，父节点下标parent==(child-1) /2;
🔍已知父节点下标parent，左孩子下标childL==parent*2+1;右孩子下标childR==parent*2+2;
当堆中插入节点时，我们需要将该节点与父节点进行比较，假设我们想要的是小堆，那么如果该节点比父节点小，我们需要交换它们的位置，重复多次直到child下标等于0。
❗注意：向上调整算法前提除是最后一个节点的所有节点构成堆。

💬AdjustUp代码：

//向上调整
void AdjustUp(int* 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;}大堆：孩子比父亲小，如果孩子大于父亲，需交换//if (a[child] > a[parent])//{//	Swap(&a[child], &a[parent]);//	child = parent;//	parent = (parent - 1) / 2;//}else{break;}}
}

💬HeapPush代码：

//堆的插入--时间复杂度为O(logN)
void HeapPush(Heap* php, HPDataType x)
{assert(php);//判断是否需要扩容if (php->capacity == php->size){php->capacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * php->capacity);if (NULL != tmp)php->a = tmp;}//插入元素php->a[php->size] = x;php->size++;//向上调整AdjustUp(php->a, php->size - 1);
}

⑤堆的删除
❗注意：堆为空不可以删除。
❓ 请思考：如何删除堆顶元素？可不可以直接用数组后面元素覆盖第一个元素？
❎可以但是不建议：如果直接用后面覆盖第一个元素首先回导致时间复杂度为O(n)。并且删除前的兄弟节点是不具备大小关系的，而直接覆盖第一个元素可能会导致原来的某一对兄弟节点变成父子节点，这是就需要具备大小关系了，所以直接覆盖第一个元素后需要重新建立堆的结构，这样实现起来效率太低了。比如

✅正确思路：先将堆顶元素和最后一个元素交换，在删除最后一个元素，在将堆顶元素移动到合适位置使整个结构变成堆。堆顶节点最多需要调整h-1次，也就是log(n+1)-1，时间复杂度为O(logN)。

📚定义：这个调整算法我们称为向下调整算法(AdjustDown)

向下调整算法
根据父节点下标与子节点下标关系，我们可以类比向上调整算法实现向下调整算法。
假设我们实现的是小堆，如果父亲节点比孩子节点大，则选出较小的孩子节点，让较小的孩子节点和父亲节点交换，直到孩子节点下标等于数组有效元素个数。
❗注意：向下调整算法的前提是左右子树都为堆。

💬AdjustDown代码：

//向下调整
void AdjustDown(int* a, int size, int parent)
{int child = parent * 2 + 1;//保证左孩子下标在有效范围内while (child < size){//小堆逻辑//让child是左右孩子中较小的那一个if (child + 1 < size && a[child] > a[child + 1])//左孩子存在右孩子不一定存在{child++;}//小堆孩子大于父亲，如果孩子比父亲小需要交换if (a[child] < a[parent]){Swap(&a[parent], &a[child]);}大堆逻辑child是左右孩子中较小的那一个//if (child + 1 < size && a[child] < a[child + 1])//左孩子存在右孩子不一定存在//{//	child++;//}大堆孩子小于父亲，如果孩子比父亲大需要交换//if (a[child] > a[parent])//{//	Swap(&a[parent], &a[child]);//}else{break;}parent = child;child = parent * 2 + 1;}
}

💬HeapPop代码：

//堆的删除(删除堆顶)--时间复杂度为O(logN)
void HeapPop(Heap* php)
{assert(php->size > 0);//交换顶和最后一个节点Swap(&php->a[0], &php->a[php->size - 1]);php->size--;//向下调整AdjustDown(php->a, php->size, 0);
}

⑥取出堆顶元素
💬HeapTop代码：

//取出堆顶元素
HPDataType HeapTop(Heap* php)
{assert(php); assert(!HeapEmpty(php));return php->a[0];
}

⑦获取堆数据个数
💬HeapSize代码：

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

⑧判断堆是否为空
💬HeapEmpty代码：

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

堆的应用

📚堆常见的应用有堆排序、TopK问题、优先级队列。接下来介绍堆排序和TopK问题。

堆排序

📚堆排序是一种基于堆数据结构的排序算法。它利用了堆的性质来进行排序操作。堆是一种完全二叉树，分为大堆和小堆两种类型。在大堆中，父节点的值大于或等于其子节点的值；而在小堆中，父节点的值小于或等于其子节点的值。
📚堆排序的基本思想：1.首先将待排序的元素构建成一个最大堆（或最小堆）2.然后将堆顶元素（即最大值或最小值）与最后一个元素交换位置 3.再对剩余的元素进行堆调整，使其满足堆的性质。4. 重复这个过程，直到所有的元素都排好序。
📚堆排序的优点：堆排序的优点是具有较好的平均和最坏情况时间复杂度（O(nlogn)），并且不需要额外的辅助空间。
📚堆排序的缺点：堆排序的实现较为复杂，包括构建堆和调整堆的过程，且不稳定，即相等元素的相对顺序可能会改变。

根据前面建堆的代码，我们很容易想出一种堆排序方法
💬使用堆排序排降序代码

//该方法可以，但是由缺点
//弊端1.现有一个堆 2.空间消耗
void HeapSort(int* arr, int size)
{Heap hp;HeapInit(&hp);//建堆O(NlogN)for (int i = 0; i < size; i++){HeapPush(&hp, arr[i]);}//O(N*logN)for (int i = 0; i < size; i++){arr[i] = HeapTop(&hp);HeapPop(&hp);}
//向上调整
void AdjustUp(int* 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;}}
}

🚩解释代码：首先建立一个小堆，将数组元素全部放入小堆，这让堆顶就是最小元素，每次取出最小元素放在数组未排序部分的最前面，再删除堆顶元素，取出次小元素放入数组未排序部分前面，最后成功将数组变为升序。

❎上述方法虽然可行，但是存在几点弊端。
1.必须先有堆才能实现堆排序。
2.使用了额外的空间消耗。

我们可以对上述思路进行改进，能不能想办法将传入的数组看为堆？这样就不需要额外建立堆了，也就不会使用额外的空间了。请看下面的思路👇

❓ 请思考：堆排序的第一步就是构建堆，如果我想让数组升序，是应该建立大堆还是小堆？
🔑解析：应该建大堆。🔍建立大堆：建立大堆时每次的堆顶就是最大元素，只需要将堆顶和堆中的最后一个元素交换位置，这样每次最大的元素就去了堆尾部也就是数组尾部，再对剩下未排序的元素进行向下调整(AdjustDown)维持大堆的结构，重复将堆顶元素放在当前堆末尾......，待排序有n个元素，只需重复n-1次上述操作即可完成排序。

🔍建立小堆：如果建立小堆排升序的话每次堆顶元素是最小的，选出最小的元素之后需要选出次小的，而堆顶已经是有序的了，所以接下来的堆有可能需要重新排序才满足堆的性质。所以如果排升序建立小堆的话，每次选出最小的之后都需要重新建堆，比较麻烦，所以不推荐建小堆。

🔺总结：排升序 -- 建立大堆；排降序 -- 建立小堆。

🔨step1.建堆
假设无序数组排降序，对数组进行的第一个操作就是建堆(小堆)，❗注意：这里是将数组本身就看作堆。建立小堆有两种方式，一种是取出数组元素向上调整建堆，另一种是向下调整建堆。
🔍向上调整建堆：当堆中只有一个元素时，可以将此堆看成大堆或者小堆，我们这里需要排降序。所以将一个节点看作小堆。我们这里需要将数组本身看作堆，所以数组首元素可以看成一个小堆，依次取数组第二个元素、第三个元素.....第n个元素进行向上调整保持小堆的性质。最终结果就是数组中的n个元素就是以小堆方式排列的。
🔍向下调整建堆：因为向下调整的前提是左右子树都为堆，所以对于数组最开始的状态我们不能保证数组的没个左右子树都为堆，所以我不能从数组第二个元素开始一次向下建堆，而是要到倒着开始向下建堆，将数组看成完全二叉树，我们需要从二叉树的最后一个叶子节点的父亲节点开始依次向下建堆，直到遍历到从整个二叉树的根，对该根进行向下调整后整个数组就是小堆的结构。
❗我们可以根据堆中父亲与孩子小标间的关系找到最后一个叶子节点的父亲。
如图：

🔨step2.交换堆顶和最后一个叶子节点
将数组变成大堆后，我们只需交换堆顶和最后一个叶子节点就可以让堆中最后一个元素变成最大值。

💬HeapSort代码：

///复杂度O(NlogN)
void HeapSort(int* arr, int size)
{//升序 -- 建大堆//降序 -- 建小堆//向上调整建堆---o(nlogn)for (int i = 1; i < size; i++){AdjustUp(arr, i);}向下调整建堆(从最后一个叶子节点的父亲开始调整)---O(n)//for (int i = (size-1-1)/2; i >= 0; i--)//{//	AdjustDown(arr, size, i);//}int end = size - 1;//O(NlogN)while (end > 0){//最小的元素和最后一个元素交换Swap(&arr[end], &arr[0]);//向下调整 -- 找出次小的元素O(logn)AdjustDown(arr, end, 0);//调整时减去已经有序的元素end--;}}

时间复杂度分析

🔍向上调整建堆的时间复杂度O(NlogN);
🔍向下调整建堆的时间复杂度O(N);
无论哪种建堆方法，HeapSort的时间复杂度都为O(NlogN)。
感兴趣的同学可以看下推导：

TopK问题

📚Top-k问题是一种优质筛选问题：从一个数据集合中找出前 k 个最大（或最小）的元素。这个问题在数据处理和算法设计中非常常见，有许多不同的解决方法。

❎我们可以直接对数据进行排序，在选出数组前k个数组，但是这样有缺陷的，比如数据个数很大时内存中无法开辟容纳它们的空间。

//该方法可以，但是由缺点
//弊端1.现有一个堆 2.空间消耗
void HeapSort(int* arr, int size)
{Heap hp;HeapInit(&hp);//建堆O(NlogN)for (int i = 0; i < size; i++){HeapPush(&hp, arr[i]);}//N*logNfor (int i = 0; i < size; i++){arr[i] = HeapTop(&hp);HeapPop(&hp);}

⚡优化：假设我们需要选出最大的k个数据

创建一个大小为 k 的最小堆。
将数据集合中前k个元素入堆。
遍历数据集合中剩下的n-k个元素，如果遍历的数据大于堆顶元素则用该数据替换堆顶元素。并且像下调整保持小堆。
遍历完所有元素后，堆中保留的就是前 k 个最大的元素。

建立小堆是因为可以让堆顶元素是当前堆中k个元素最小的，如果其余元素比堆顶(当前堆中k个元素最小的元素)要大，那么可以让该元素替换堆顶的元素。此时堆中的所有元素是遍历到目前最大的k个元素，直到遍历结束堆中的k个元素就是所有元素中最大的。
❓请思考：如果找最大的k个建立的是大堆会怎么样？
🔑解析：如果建立的是大堆，假设推中的k个元素有所有元素中最大的元素，由于是大堆，所以最大元素一定在堆顶，剩下的n-k个元素即使有次大的，和堆顶比较依然小于堆顶，也就是说堆顶被 ”挡住了“，所以无法找到前k个最大的元素。

🔺总结：前k个最大的 -- 建立大小为k的小堆；前k个最小的 -- 建立大小为k的大堆。

💬TopK代码

//优质筛选问题
void TestTopK(int* arr, int n, int k)
{int* kminHeap = (int*)malloc(sizeof(int) * k);if (kminHeap == NULL){perror("kminHeap申请失败:");exit(EXIT_FAILURE);}思路1排序----当数据很大时无法实现，内存中没有那么多空间可以开辟//  时间复杂度O(nlogn)//HeapSort(arr, size);//for (int i = 0; i < k; i++)//{//	kminHeap[i] = arr[i];//}//for (int i = 0; i < k; i++)//{//	printf("%d ", kminHeap[i]);//}//思路2（重点）//找前k个最小的 -- 建大堆//找前k个最大的 -- 建小堆//1.先将k个数据放入堆中，在将n-k个数据依次和堆顶比较：//2.如果寻找前个k最小的，将比大堆堆顶小的元素放入堆中，进行向下调整//  如果寻找前个k最大的，将比小堆堆顶大的元素放入堆中，进行向下调整//前k个元素建立堆for (int i = 0; i < k; i++){kminHeap[i] = arr[i];}//F(n)=(n - k) * (H - 1) = (n - k) * (log(k+1) - 1) -- O(nlogk)for (int i = k; i < n; i++){if (arr[i] > kminHeap[0]){kminHeap[0] = arr[i];AdjustDown(kminHeap, k, 0);//AdjustDown建小堆}}for (int i = 0; i < k; i++){printf("%d ", kminHeap[i]);}free(kminHeap);
}