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

相关文章

Redis 热 key 和大 key 问题小结

Redis 热 key 和大 key 问题小结

《Redis热key和大key问题小结》：本文主要介绍Redis热key和大key问题小结,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、什么是 Redis 热 key？热 key（Hot Key）定义： 热 key 常见表现：热 key 的风险：二、
阅读更多...
IntelliJ IDEA 中配置 Spring MVC 环境的详细步骤及问题解决

IntelliJ IDEA 中配置 Spring MVC 环境的详细步骤及问题解决

《IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决》：本文主要介绍IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决,本文分步骤结合实例给大... 目录步骤 1：创建 Maven Web 项目步骤 2：添加 Spring MVC 依赖1、保存后执行2、将新的依赖
阅读更多...
Spring 中的循环引用问题解决方法

Spring 中的循环引用问题解决方法

《Spring中的循环引用问题解决方法》：本文主要介绍Spring中的循环引用问题解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录什么是循环引用？循环依赖三级缓存解决循环依赖二级缓存三级缓存本章来聊聊Spring 中的循环引用问题该如何解决。这里聊
阅读更多...
Spring Boot中JSON数值溢出问题从报错到优雅解决办法

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》：本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景：为什么我的接口突然报错了？二、为什么会发生这个错误？1. Java 数据类型的“容量”限制
阅读更多...
C语言中位操作的实际应用举例

C语言中位操作的实际应用举例

《C语言中位操作的实际应用举例》：本文主要介绍C语言中位操作的实际应用,总结了位操作的使用场景,并指出了需要注意的问题,如可读性、平台依赖性和溢出风险,文中通过代码介绍的非常详细,需要的朋友可以参... 目录1. 嵌入式系统与硬件寄存器操作2. 网络协议解析3. 图像处理与颜色编码4. 高效处理布尔标志集合
阅读更多...
关于MongoDB图片URL存储异常问题以及解决

关于MongoDB图片URL存储异常问题以及解决

《关于MongoDB图片URL存储异常问题以及解决》：本文主要介绍关于MongoDB图片URL存储异常问题以及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录MongoDB图片URL存储异常问题项目场景问题描述原因分析解决方案预防措施js总结MongoDB图
阅读更多...
SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示：项目相关背景：项目场景：基于Spring
阅读更多...
解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》：本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基
阅读更多...
usb接口驱动异常问题常用解决方案

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时，可以通过多种方法来解决，其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办，USB接口驱动异常是常见问题，通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决
阅读更多...
Java中的Lambda表达式及其应用小结

Java中的Lambda表达式及其应用小结

《Java中的Lambda表达式及其应用小结》Java中的Lambda表达式是一项极具创新性的特性,它使得Java代码更加简洁和高效,尤其是在集合操作和并行处理方面,：本文主要介绍Java中的La... 目录前言1. 什么是Lambda表达式？2. Lambda表达式的基本语法例子1：最简单的Lambda表
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2