【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。

相关文章

C#数据结构之字符串(string)详解

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》：本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘
阅读更多...
Python中随机休眠技术原理与应用详解

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2
阅读更多...
SpringBoot启动报错的11个高频问题排查与解决终极指南

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突：NoSuchMethodError 的终极解法2. Bean注入失败：No qu
阅读更多...
Python Dash框架在数据可视化仪表板中的应用与实践记录

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash？1.1
阅读更多...
使用Java实现通用树形结构构建工具类

使用Java实现通用树形结构构建工具类

《使用Java实现通用树形结构构建工具类》这篇文章主要为大家详细介绍了如何使用Java实现通用树形结构构建工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录完整代码一、设计思想与核心功能二、核心实现原理1. 数据结构准备阶段2. 循环依赖检测算法3. 树形结构构建4. 搜索子
阅读更多...
MySQL新增字段后Java实体未更新的潜在问题与解决方案

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更（如新增字段）后,开发人员可... 目录引言1. 问题背景：数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作
阅读更多...
利用Python开发Markdown表格结构转换为Excel工具

利用Python开发Markdown表格结构转换为Excel工具

《利用Python开发Markdown表格结构转换为Excel工具》在数据管理和文档编写过程中,我们经常使用Markdown来记录表格数据,但它没有Excel使用方便,所以本文将使用Python编写一... 目录1.完整代码2. 项目概述3. 代码解析3.1 依赖库3.2 GUI 设计3.3 解析 Mark
阅读更多...
Android Kotlin 高阶函数详解及其在协程中的应用小结

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民（First-ClassCitizen）,使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数？3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda
阅读更多...
如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》：本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错
阅读更多...
如何解决Spring MVC中响应乱码问题

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》：本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2