【Super数据结构】堆结构的建立与调整堆的应用（含堆排序/topK问题）

2024-04-10 08:52
文章标签 问题 应用 数据结构 结构 建立 堆排序 调整 topk super

本文主要是介绍【Super数据结构】堆结构的建立与调整堆的应用（含堆排序/topK问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

🏠关于此专栏：Super数据结构专栏将使用C/C++语言介绍顺序表、链表、栈、队列等数据结构，每篇博文会使用尽可能多的代码片段+图片的方式。
🚪归属专栏：Super数据结构
🎯每日努力一点点，技术累计看得见

文章目录

  • 二叉树的顺序存储
  • 堆的概念及结构
  • 堆的实现
    • 堆向下调整算法
    • 堆向上调整算法
    • 堆的创建
    • 建堆的时间复杂度
    • 堆的插入
    • 堆的删除
    • 堆的实现代码（含堆的各个常用接口）
  • 堆的应用
    • 堆排序
    • topK问题

二叉树的顺序存储

对于完全二叉树（包含满二叉树），它的结点中，h-1层的结点均是满的，最后一层从左到右连续有结点（不存在结点和空相间的情况）。像这种结构是适合使用二叉树来存储的。

例如下图是一颗完全二叉树，它的高度h为4，它的h-1，即前3层均为满，最后一层从左到右连续有结点。这时，第一层保存在0号下标，第二层保存在1到2号下标，第三层保存在3到6号下标，最后一层保存在7号下标。当要寻找某个结点的左子树根节点时，可以使用i * 2 + 1来得到；例如根节点存储在0号，它的左子树根节点下标等于0 * 2 + 1=1。当要寻找某个结点的右子树根节点时，可以使用i * 2 + 2来得到；例如根节点存储在0号，它的右子树根节点等于0 * 2 + 2=2来得到。如果要寻找某个结点的双亲结点，则可以使用(i - 1) / 2来得到；例如值为7的结点，它的下标为6，可以通过计算(6 - 1) / 2=2得到它的双亲结点位于2号下标。
在这里插入图片描述
那如果是普通的二叉树呢？我们以下图这颗二叉树为例。下图为了保持使用i * 2 + 1找左孩子，i * 2 + 2找右孩子，(i - 1) / 2找双亲节点，不得不浪费大量空间。这颗二叉树存储为数组，如下图所示（其中?表示空出来不适用的位置），这当中存在大量浪费的空间。因此，普通二叉树不适合使用顺序结构存储。
在这里插入图片描述

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

堆的概念及结构

如果有一个关键码的集合 K = { k 0 ， k 1 ， k 2 ， … ， k n − 1 } K = \{ k_{0}，k_{1} ，k_{2} ，…，k_{n-1} \} K={k0​，k1​，k2​，…，kn−1​}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： k i < = k 2 ∗ i + 1 k_{i}<=k_{2*i+1} ki​<=k2∗i+1​ 且 k i < = k 2 ∗ i + 2 k_{i}<=k_{2*i+2} ki​<=k2∗i+2​ （其中i=0，1，2…），则称为小堆，也称为最小堆或小根堆。如果满足 k i > = k 2 ∗ i + 1 k_{i}>=k_{2*i+1} ki​>=k2∗i+1​ 且 k i > = k 2 ∗ i + 2 k_{i}>=k_{2*i+2} ki​>=k2∗i+2​ （其中i=0，1，2…），则称为大堆，也称为最大堆或大根堆。

用大白话描述：小根堆就是所有节点满足：当前节点的值小于其左右孩子的值；大根堆的所有节点满足：当前节点的值大于其左右孩子的值。

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

下面给出一个小堆的示例：下图中的二叉树，所有节点都满足：当前节点的值小于其左右孩子的值。
在这里插入图片描述
下面给出一个大堆的示例：下图中的二叉树，所有节点都满足：当前节点的值大于其左右孩子的值。
在这里插入图片描述
这里的堆，我们使用的是数组存储的，因而我们可以定义一个结构体，其中包含指向动态开辟的数组的首地址的指针、数组有效元素个数、数组容量。

typedef int HPDataType;
typedef struct Heap
{HPDataType* _data;int _size;int _capacity;
}Heap;

堆的实现

堆向下调整算法

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

下图中根节点的左右子树均为一个小堆。如果要将下图这颗树调整为小堆，则我们可以采用向下调整算法。
在这里插入图片描述
向下调整算法思路如下：
1.从某个节点向下调整，则需要使用该节点与其左右孩子进行比较。上图中，从根节点开始调整，则使用数值为9的节点，与它的左右孩子比较（即与值为1和值为4的节点进行比较）。此时要构建的是小堆，则要与数值小的进行交换，让数值小的节点向上移动。（即数值为9的节点与数值为1的节点进行交换）
在这里插入图片描述
2.值为9的节点继续向下调整，此时从它的左右孩子中挑选出最小的，如果如果值为9的节点比值小的节点的数值还要小，则调整结束。但这里值为9的节点比值为3的节点大，故需要继续向下调整。（即值为3的节点与值为9的节点交换）
在这里插入图片描述
3.此时值为9的节点已经到达最后一层，调整结束。

下面给出向下（小堆）调整代码↓↓↓

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//data ---> 指向待调整堆结构数组的起始地址
//parent ---> 向下调整的起始位置
//n ---> 调整的范围
void AdjustDown(HPDataType* data, int parent, int n)
{int child = parent * 2 + 1;while(child < n){if(child + 1 < n && data[child + 1] < data[child]){child++;}if(data[child] < data[parent]){Swap(&data[child], &data[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

下面给出的代码是构建大堆的↓↓↓

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//data ---> 指向待调整堆结构数组的起始地址
//parent ---> 向下调整的起始位置
//n ---> 调整的范围
void AdjustDown(HPDataType* data, int parent, int n)
{int child = parent * 2 + 1;while(child < n){if(child + 1 < n && data[child + 1] > data[child]){child++;}if(data[child] > data[parent]){Swap(&data[child], &data[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

堆向上调整算法

我们通常在给堆插入新元素时，都会插入在它的末尾，新元素插入后就需要使用向上调整算法（在插入新元素前，需要保证当前数组为堆存储结构）。

下图蓝色接变表示原来的堆结构，橙色节点表示新插入的节点。原本的结构是一个小堆。插入新元素后，需要使用向上调整算法，使其变为一个新的小堆。
在这里插入图片描述
向上调整算法的思路（以小堆为例）如下：
1.使用当前节点与其双亲结点比较，如果比其双亲结点小，则与其双亲结点交换（即向上调整）。值为2的结点比其双亲结点（值为4的结点）值要小，故需要与其双亲结点。
在这里插入图片描述
2.经过上一次的向上调整操作后，需要继续与它新的双亲结点比较，如果比它的双亲结点小，则继续向上调整，否则停止调整。值为2的结点比其双亲结点（值为1）的值要大，此时停止调整，算法结束。

下面给出向上的代码↓↓↓

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* data, int child)
{int parent = (child - 1) / 2;while(child > 0){if(data[child] < data[parent]){Swap(&data[child], &data[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

对于大堆的向上调整算法如下所示↓↓↓

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* data, int child)
{int parent = (child - 1) / 2;while(child > 0){if(data[child] > data[parent]){Swap(&data[child], &data[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

堆的创建

堆的存储结构中，本质是一颗使用数组存储的二叉树，起始时其实还不是一个堆。我们需要怎样才能将其构建成一个堆呢？

如果二叉树中只有一个结点，则它也可以是一个堆。因此，我们对于一个存在左右子树，左右子树均只有一个结点的结构，我们可以将其看作是一个左右子树均为堆的结构。此时我们可以使用向下调整算法，将其调整为堆。

上面这段话描述的本质就是：从第一个非叶子结点开始，从该结点到根节点，依次执行向下调整算法。

我们以下面这颗二叉树为例，使用它来构建一个堆（小堆）。我们从第一个非叶子结点，也就是值为8的结点，从该结点及其左侧各个兄弟/堂兄弟结点到根节点，依次指向向下调整。
在这里插入图片描述
8的左右子树只有1个结点，可以将它们看作已经调整好的小堆。由于此时构建的是小堆，从左右孩子中选择小的那个，与8比较发现，比8小。此时需要将结点值为8的与结点值为2的进行交换。
在这里插入图片描述
接下来调整的是值为9的结点，堆它执行向下调整算法。
在这里插入图片描述
此时轮到值为1的结点执行向下调整，此时它的左右子树已经是调整好的小堆结构。但值为1的结点比它的左右孩子结点的值都要小，因此不会发生交换。根节点调整完后，则堆建立完成。

void makeHeap()
{HPDataType data[] = {1,9,8,7,5,6,2};int len = sizeof(data) / sizeof(data[0]);for(int i = (len - 1 - 1) / 2; i >= 0; i++){AdjustDown(data, i, len);}
}

建堆的时间复杂度

由于堆是完全二叉树，满二叉树属于完全二叉树的特例。这里为了计算方便，使用满二叉树来推导计算建堆的时间复杂度。

下图分析了每一层的节点个数及每一层的节点需要向下调整的最大次数。
在这里插入图片描述
建堆的时间复杂度为O(N)，推导过程如下图所示。
在这里插入图片描述
上面分析的是向下调整建堆，那如果使用的是向上调整建堆呢？
下图分析了每一层的节点个数及每一层的节点需要向上调整的最大次数。
在这里插入图片描述
建堆的时间复杂度为O(NlogN)，推导过程如下图所示。
在这里插入图片描述
由于向上调整建堆的时间复杂度高于向下调整建堆，故我们常规建堆均采用向下调整。

堆的插入

将堆插入至存储堆的数组的末尾，再从末尾执行向上调整算法。

void HeapPush(Heap* php, HPDataType x)
{assert(php);if (php->_size == php->_capacity){HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * php->_capacity * 2);memcpy(tmp, php->_data, sizeof(HPDataType) * php->_size);free(php->_data);php->_data = tmp;php->_capacity *= 2;}php->_data[php->_size] = x;AdjustUp(php->_data, php->_size);php->_size++;
}

堆的删除

删除堆的时候，为了保证堆的结构不被破坏，我们可以执行如下操作：①被删除结点与堆的最后一个结点进行值交换；②将最后一个结点删除（由于最后一个结点是叶子结点，因此不会影响堆结构）；③发生值交换的那个结点，由于将最后一个结点的值交换上来，因此无法保证整个结构还是堆；但是能保证该结点的左右子树还是堆，此时我们可以从该结点开始，指向向下调整算法。

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}bool HeapEmpty(Heap* php)
{return php->_size == 0;
}//头删
void HeapPop(Heap* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->_data[0], &php->_data[php->_size - 1]);php->_size--;AdjustDown(php->_data, 0, php->_size);
}

堆的实现代码（含堆的各个常用接口）

头文件Heap.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* _data;int _size;int _capacity;
}Heap;void HeapInit(Heap* php);void HeapDestroy(Heap* php);void HeapPush(Heap* php, HPDataType x);void HeapPop(Heap* php);HPDataType HeapTop(Heap* php);bool HeapEmpty(Heap* php);int HeapSize(Heap* php);

Heap.c源文件

#include "Heap.h"void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustDown(HPDataType* data, int parent, int n)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && data[child + 1] < data[child]){child++;}if (data[child] < data[parent]){Swap(&data[child], &data[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void AdjustUp(HPDataType* data, int child)
{int parent = (child - 1) / 2;while (child > 0){if (data[child] < data[parent]){Swap(&data[child], &data[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}void HeapInit(Heap* php)
{assert(php);php->_data = (HPDataType*)malloc(sizeof(HPDataType) * 2);php->_size = 0;php->_capacity = 2;
}void HeapDestroy(Heap* php)
{assert(php);if (php->_data) free(php->_data);php->_size = php->_capacity = 0;
}void HeapPush(Heap* php, HPDataType x)
{assert(php);if (php->_size == php->_capacity){HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * php->_capacity * 2);memcpy(tmp, php->_data, sizeof(HPDataType) * php->_size);free(php->_data);php->_data = tmp;php->_capacity *= 2;}php->_data[php->_size] = x;AdjustUp(php->_data, php->_size);php->_size++;
}void HeapPop(Heap* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->_data[0], &php->_data[php->_size - 1]);php->_size--;AdjustDown(php->_data, 0, php->_size);
}HPDataType HeapTop(Heap* php)
{assert(!HeapEmpty(php));return php->_data[0];
}bool HeapEmpty(Heap* php)
{assert(php);return php->_size == 0;
}int HeapSize(Heap* php)
{assert(php);return php->_size;
}

堆的应用

堆排序

在进行堆排序前，我们需要先使得数组称为堆结构。在已经是堆结构得数组中（如果是大根堆），则将堆首元素与最后一个元素交换，此时最后一个元素就是最大。
在这里插入图片描述
在这里插入图片描述
此时对除了数组最后一个元素的余下元素，执行向下调整算法，得到第二大的数，即数字8。将它与下标为5的元素交换，此时最后两个元素分别是8和9，是有序的。
在这里插入图片描述
在这里插入图片描述
此时对除了最后两个元素的其他元素做向下调整，此时堆顶是第三大的元素，即数字7。将它与下标为4的元素做交换，此时最后3个元素是有序的。以此类推，不断使用向下调整寻找新的最大的数，将其放置到后面，这样就可以实现堆排序。
在这里插入图片描述
在这里插入图片描述
从上面的分析可知，如果要从小到大排序，需要构建大堆；如果要从大到小排序，需要构建小堆。

下面给出的是堆排序的代码↓↓↓

void HeapSort(int arr[], int len)
{//构建堆for(int i = (len - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, len);}while(len > 0){Swap(&arr[0], &arr[len - 1]);len--;AdjustDown(arr, 0, len);}
}

topK问题

如果需要从100000个数据中选出最大的5个数，我们应该怎么做呢？可能你会想到使用排序算法，再从中选出最大的5个数。但这并不是最优的，这里还有别的思路。

如果我们要选择最大的5个数，可以建立包含5个元素的小堆。因为堆顶存的是当前堆中的最小元素，如果某个元素比整个的堆的最小元素要大，则是截至目前为止的最大的5个最大元素之一；此时将它与堆顶元素元素互换数值，并重新构建小堆。在整个过程中，堆中存的都是截至目前最大的5个数。

下面给出找出最大k个元素的算法代码↓↓↓

void AdjustDown(HPDataType* data, int parent, int n)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && data[child + 1] < data[child]){child++;}if (data[child] < data[parent]){Swap(&data[child], &data[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
int* topKMax(int arr[], int len, int k)
{int* kmax = (int*)malloc(sizeof(int) * k);for(int i = 0; i < k; i++){kmax[i] = arr[i];}//建小堆for(int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(kmax, i, k);}for(int i = k; i < len; i++){if(arr[i] > kmax[0]){kmax[0] = arr[i];AdjustDown(kmax, 0, k);}}return kmax;
}

如果是要求100000个数中最小的5个数，则需要构建大堆。实现代码如下↓↓↓

void AdjustDown(HPDataType* data, int parent, int n)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && data[child + 1] > data[child]){child++;}if (data[child] > data[parent]){Swap(&data[child], &data[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}int* topKMin(int arr[], int len, int k)
{int* kmin = (int*)malloc(sizeof(int) * k);for (int i = 0; i < k; i++){kmin[i] = arr[i];}//建大堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(kmin, i, k);}for (int i = k; i < len; i++){if (arr[i] < kmin[0]){kmin[0] = arr[i];AdjustDown(kmin, 0, k);}}return kmin;
}

如果使用排序算法实现100000个数据中找最大的5个数，则算法时间复杂度至少为O(NlogN)。而采用topk算法后，前k个元素建堆的时间复杂度为O(k)，k 到n的元素即使每次都需要向下调整，则时间复杂度为O((n-k)logK)，整体的算法复杂度为O(k+(n-k)logk)，当k特别小时，此时的算法复杂度趋于O(N)。

🎈欢迎进入Super数据结构专栏，查看更多文章。
如果上述内容有任何问题，欢迎在下方留言区指正b(￣▽￣)d

这篇关于【Super数据结构】堆结构的建立与调整堆的应用（含堆排序/topK问题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/890604。

相关文章

关于@MapperScan和@ComponentScan的使用问题

关于@MapperScan和@ComponentScan的使用问题

《关于@MapperScan和@ComponentScan的使用问题》文章介绍了在使用`@MapperScan`和`@ComponentScan`时可能会遇到的包扫描冲突问题,并提供了解决方法,同时,... 目录@MapperScan和@ComponentScan的使用问题报错如下原因解决办法课外拓展总结@
阅读更多...
MybatisGenerator文件生成不出对应文件的问题

MybatisGenerator文件生成不出对应文件的问题

《MybatisGenerator文件生成不出对应文件的问题》本文介绍了使用MybatisGenerator生成文件时遇到的问题及解决方法,主要步骤包括检查目标表是否存在、是否能连接到数据库、配置生成... 目录MyBATisGenerator 文件生成不出对应文件先在项目结构里引入“targetProje
阅读更多...
C#使用HttpClient进行Post请求出现超时问题的解决及优化

C#使用HttpClient进行Post请求出现超时问题的解决及优化

《C#使用HttpClient进行Post请求出现超时问题的解决及优化》最近我的控制台程序发现有时候总是出现请求超时等问题,通常好几分钟最多只有3-4个请求,在使用apipost发现并发10个5分钟也... 目录优化结论单例HttpClient连接池耗尽和并发并发异步最终优化后优化结论我直接上优化结论吧，
阅读更多...
Java内存泄漏问题的排查、优化与最佳实践

Java内存泄漏问题的排查、优化与最佳实践

《Java内存泄漏问题的排查、优化与最佳实践》在Java开发中,内存泄漏是一个常见且令人头疼的问题,内存泄漏指的是程序在运行过程中,已经不再使用的对象没有被及时释放,从而导致内存占用不断增加,最终... 目录引言1. 什么是内存泄漏？常见的内存泄漏情况2. 如何排查 Java 中的内存泄漏？2.1 使用 J
阅读更多...
numpy求解线性代数相关问题

numpy求解线性代数相关问题

《numpy求解线性代数相关问题》本文主要介绍了numpy求解线性代数相关问题,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 在numpy中有numpy.array类型和numpy.mat类型，前者是数组类型，后者是矩阵类型。数组
阅读更多...
解决systemctl reload nginx重启Nginx服务报错:Job for nginx.service invalid问题

解决systemctl reload nginx重启Nginx服务报错:Job for nginx.service invalid问题

《解决systemctlreloadnginx重启Nginx服务报错:Jobfornginx.serviceinvalid问题》文章描述了通过`systemctlstatusnginx.se... 目录systemctl reload nginx重启Nginx服务报错:Job for nginx.javas
阅读更多...
Redis缓存问题与缓存更新机制详解

Redis缓存问题与缓存更新机制详解

《Redis缓存问题与缓存更新机制详解》本文主要介绍了缓存问题及其解决方案,包括缓存穿透、缓存击穿、缓存雪崩等问题的成因以及相应的预防和解决方法,同时,还详细探讨了缓存更新机制,包括不同情况下的缓存更... 目录一、缓存问题1.1 缓存穿透1.1.1 问题来源1.1.2 解决方案1.2 缓存击穿1.2.1
阅读更多...
将Python应用部署到生产环境的小技巧分享

将Python应用部署到生产环境的小技巧分享

《将Python应用部署到生产环境的小技巧分享》文章主要讲述了在将Python应用程序部署到生产环境之前,需要进行的准备工作和最佳实践,包括心态调整、代码审查、测试覆盖率提升、配置文件优化、日志记录完... 目录部署前夜：从开发到生产的心理准备与检查清单环境搭建：打造稳固的应用运行平台自动化流水线：让部署像
阅读更多...
vue解决子组件样式覆盖问题scoped deep

vue解决子组件样式覆盖问题scoped deep

《vue解决子组件样式覆盖问题scopeddeep》文章主要介绍了在Vue项目中处理全局样式和局部样式的方法,包括使用scoped属性和深度选择器（/deep/）来覆盖子组件的样式,作者建议所有组件... 目录前言scoped分析deep分析使用总结所有组件必须加scoped父组件覆盖子组件使用deep前言
阅读更多...
解决Cron定时任务中Pytest脚本无法发送邮件的问题

解决Cron定时任务中Pytest脚本无法发送邮件的问题

《解决Cron定时任务中Pytest脚本无法发送邮件的问题》文章探讨解决在Cron定时任务中运行Pytest脚本时邮件发送失败的问题,先优化环境变量,再检查Pytest邮件配置,接着配置文件确保SMT... 目录引言1. 环境变量优化：确保Cron任务可以正确执行解决方案：1.1. 创建一个脚本1.2. 修
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2