【数据结构】堆，堆的实现，堆排序，TOP-K问题

大家好！今天我们来学习数据结构中的堆及其应用

目录

1. 堆的概念及结构

2. 堆的实现

2.1 初始化堆

2.2 销毁堆

2.3 打印堆

2.4 交换函数

2.5 堆的向上调整

2.6 堆的向下调整

2.7 堆的插入

2.8 堆的删除

2.9 取堆顶的数据

2.10 堆的数据个数

2.11 堆的判空

3. 堆的实现的完整代码

3.1 Heap.h

3.2 Heap.c

3.3 Test.c

4. 建堆的时间复杂度

4.1 向上调整建堆

4.2 向下调整建堆

5. 堆的应用

5.1 堆排序

5.2 TOP-K问题

6. 总结

1. 堆的概念及结构

堆(Heap)是计算机科学中中一类特殊的数据结构，是最高效的优先级队列，堆通常是一个可以被看作一棵完全二叉树的数组对象。

堆分为最小堆（Min Heap）和 最大堆（Max Heap）和最小堆（Min Heap）。对于最小堆，父结点的值小于等于它的子结点的值。对于最大堆，父结点的值大于等于它的子结点的值；

堆的性质：

1. 堆中某个结点的值总是不大于或不小于其父结点的值。

2. 堆总是一棵完全二叉树。

3. 小堆的根是整棵树的最小值，大堆的根是整棵树的最大值。

问题：

1. 小堆的底层数组是否升序？

2. 大堆的底层数组是否降序？

2. 堆的实现

我们这里以小根堆为例（大根堆可以在小根堆的基础上稍作修改），下面是要实现堆的接口函数：

//初始化堆
void HeapInit(HP* php);
//销毁堆
void HeapDestroy(HP* php);
//打印堆
void HeapPrint(HP* php);
//交换函数
void Swap(HPDataType* p1, HPDataType* p2);
//堆向上调整算法
void AdjustUp(HPDataType* a, int child);
//堆向下调整算法
void AdjustDown(HPDataType* a, int n, int parent);
//堆的插入
void HeapPush(HP* php, HPDataType x);
//堆的删除
void HeapPop(HP* php);
//取堆顶的数据
HPDataType HeapTop(HP* php);
//堆的数据个数
int HeapSize(HP* php);
//堆的判空
bool HeapEmpty(HP* php);

堆的定义：

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

一些简单的接口函数，和我们之前实现的顺序表，链表，栈等数据结构类似。我们在这里就不详细介绍了，这里我们主要介绍堆向上调整算法和堆向下调整算法。这两个函数分别会在堆的插入和堆的删除中调用。

2.1 初始化堆

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

2.2 销毁堆

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

2.3 打印堆

//打印堆
void HeapPrint(HP* php)
{assert(php);for (int i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}

2.4 交换函数

//交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}

2.5 堆的向上调整

向上调整前提：前面的数据是堆

//堆向上调整算法
void AdjustUp(HPDataType* 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;}	}
}

2.6 堆的向下调整

向下调整前提：左右子树都是小堆或者都是大堆

//堆向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] < a[child]) //找出小的那个孩子{++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child; child = parent * 2 + 1;}else{break;}}
}

2.7 堆的插入

向堆中插入一个元素，就是这个元素插入到堆的尾部，因为堆的实际存储结构是一个数组，我们可以将元素放到数组末尾。

但是如果仅仅是将元素插入到数组末尾的话，会破坏堆的结构，我们还需要调用一个向上调整函数，保持堆的结构。

注意：在插入之前，我们需要判断堆的容量是否足够，如果堆的容量已满，需要扩容，扩容时我们在原来的基础上扩2倍。

如下图：

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

//堆的插入
void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);if (tmp == NULL){perror("realloc failed");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

2.8 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

//堆的删除
void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);--php->size;AdjustDown(php->a, php->size, 0);
}

2.9 取堆顶的数据

//取堆顶的数据
HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

2.10 堆的数据个数

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

2.11 堆的判空

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

3. 堆的实现的完整代码

3.1 Heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;//初始化堆
void HeapInit(HP* php);
//销毁堆
void HeapDestroy(HP* php);
//打印堆
void HeapPrint(HP* php);
//交换函数
void Swap(HPDataType* p1, HPDataType* p2);
//堆向上调整算法
void AdjustUp(HPDataType* a, int child);
//堆向下调整算法
void AdjustDown(HPDataType* a, int n, int parent);
//堆的插入
void HeapPush(HP* php, HPDataType x);
//堆的删除
void HeapPop(HP* php);
//取堆顶的数据
HPDataType HeapTop(HP* php);
//堆的数据个数
int HeapSize(HP* php);
//堆的判空
bool HeapEmpty(HP* php);

3.2 Heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"//初始化堆
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}//销毁堆
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}//打印堆
void HeapPrint(HP* php)
{assert(php);for (int i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}//交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//堆向上调整算法
void AdjustUp(HPDataType* 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;}	}
}//堆向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] < a[child]) //找出小的那个孩子{++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child; child = parent * 2 + 1;}else{break;}}
}//堆的插入
void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);if (tmp == NULL){perror("realloc failed");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}//堆的删除
void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);--php->size;AdjustDown(php->a, php->size, 0);
}//取堆顶的数据
HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}//堆的数据个数
int HeapSize(HP* php) 
{assert(php);return php->size;
}//堆的判空
bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

3.3 Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"int main()
{int a[] = { 2,3,5,7,4,6,8};HP hp;HeapInit(&hp);for (int i = 0; i < sizeof(a) / sizeof(int); i++){HeapPush(&hp, a[i]);}HeapPrint(&hp);int sz = HeapSize(&hp);printf("堆中元素个数为%d个\n", sz);while (!HeapEmpty(&hp)){printf("%d ", HeapTop(&hp));HeapPop(&hp);}HeapDestroy(&hp);return 0;
}

4. 建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个结点不影响最终结果)：

4.1 向上调整建堆

因此向上调整建堆的时间复杂度是O(N*logN)

4.2 向下调整建堆

因此，向下调整建堆的时间复杂度为O(N)

因为向下调整建堆的时间复杂度是O(N)，小于向上调整建堆的时间复杂度O(N*logN)，所以一般情况下，我们都采用向下调整建堆。

5. 堆的应用

5.1 堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆

升序：建大堆

降序：建小堆

2. 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

这里我们以大堆为例，通过堆排序进行升序

我们也可以在堆的底层数组中进一步理解堆排序的过程

因为是大堆，所以我们要稍微修改向下调整部分的代码（我们在上面堆的实现中是以小堆为例）

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]) //找出大的那个孩子{++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child; child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{//从倒数第一个非叶子结点开始调for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);  //向下调整建堆}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);  //向下调整[0,end]的元素--end;}
}int main()
{int a[] = { 20,17,4,16,5,3 };HeapSort(a, sizeof(a) / sizeof(int));for (int i=0 ; i < sizeof(a) / sizeof(int); i++){printf("%d ", a[i]);}printf("\n");return 0;
}

5.2 TOP-K问题

TOP- K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆

前k个最大的元素，则建小堆

前k个最小的元素，则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

实际应用：在1000000个随机数中找出前十个最大的数字

void PrintTopK(int* a, int n, int k)
{int* KMaxHeap = (int*)malloc(sizeof(int) * k);assert(KMaxHeap);for (int i = 0; i < k; i++){KMaxHeap[i] = a[i];}//建小根堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(KMaxHeap, k, i);}//依次比较a数组中剩余的元素for (int i = k; i < n; i++){if (a[i] > KMaxHeap[0]){KMaxHeap[0] = a[i];}AdjustDown(KMaxHeap, k, 0);}//打印for (int i = 0; i < k; i++){printf("%d ", KMaxHeap[i]);}printf("\n");
}void TestTopK()
{int n = 1000000;int* a = (int*)malloc(sizeof(int) * n);srand(time(0));for (int i = 0; i < n; i++){a[i] = rand() % n;}//手动设定10个最大的数a[5] = n + 1;a[1231] = n + 2;a[531] = n + 3;a[5121] = n + 4;a[115] = n + 5;a[2335] = n + 6;a[9999] = n + 7;a[76] = n + 8;a[423] = n + 9;a[3144] = n + 10;PrintTopK(a, n, 10);
}int main()
{TestTopK();return 0;
}

6. 总结

到这里，我们就用学习完了数据结构中堆的相关知识点。有什么问题欢迎在评论区讨论。如果觉得文章有什么不足之处，可以在评论区留言。如果喜欢我的文章，可以点赞收藏哦！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/145348.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

内存函数的介绍和模拟实现

内存函数的介绍和模拟实现

目录 1.memcpy的使用(内存拷贝) 2.memcpy的实现 3.memmove的使用&#xff08;内存拷贝&#xff09; 4.memmove的实现 5.memset 的使用&#xff08;内存设置&#xff09; 6.memcmp的使用&#xff08;内存比较&#xff09; 1.memcpy的使用(内存拷贝) void * memcpy ( void * …
阅读更多...
整型提升——（巩固提高——字符截取oneNote笔记详解)

整型提升——（巩固提高——字符截取oneNote笔记详解)

文章目录 前言一、整型提升是什么&#xff1f;二、详细图解1.图解展示 总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 整型提升是数据存储的重要题型&#xff0c;也是计算机组成原理的核心知识点。学习c语言进阶的时候,了解内存中数据怎么存&#…
阅读更多...
孤举者难起，众行者易趋，openGauss 5.1.0版本正式发布！

孤举者难起，众行者易趋，openGauss 5.1.0版本正式发布！

&#x1f4e2;&#x1f4e2;&#x1f4e2;&#x1f4e3;&#x1f4e3;&#x1f4e3; 哈喽&#xff01;大家好&#xff0c;我是【IT邦德】&#xff0c;江湖人称jeames007&#xff0c;10余年DBA及大数据工作经验 一位上进心十足的【大数据领域博主】&#xff01;&#x1f61c;&am…
阅读更多...
华为云云耀云服务器L实例评测｜云耀云服务器L实例搭建个人镜像站

华为云云耀云服务器L实例评测｜云耀云服务器L实例搭建个人镜像站

华为云云耀云服务器L实例评测&#xff5c;云耀云服务器L实例搭建个人镜像站 一、云耀云服务器L实例介绍1.1 云耀云服务器L实例简介1.2 云耀云服务器L实例特点 二、Apache介绍2.1 Apache简介2.2 Apache特点 三、本次实践介绍3.1 本次实践简介3.2 本次环境规划 四、远程登录华为云…
阅读更多...
SpringCloud Alibaba 入门到精通 - Sentinel

SpringCloud Alibaba 入门到精通 - Sentinel

SpringCloud Alibaba 入门到精通 - Sentinel 一、基础结构搭建1.父工程创建2.子工程创建 二、Sentinel的整合SpringCloud1.微服务可能存在的问题2.SpringCloud集成Sentinel搭建Dashboard3 SpringCloud 整合Sentinel 三、服务降级1 服务降级-Sentinel2 Sentinel 整合 OpenFeign3…
阅读更多...
【深度学习实验】卷积神经网络（三）：自定义二维卷积层：步长、填充、输入输出通道

【深度学习实验】卷积神经网络（三）：自定义二维卷积层：步长、填充、输入输出通道

目录 一、实验介绍 二、实验环境 1. 配置虚拟环境 2. 库版本介绍 三、实验内容 0. 导入必要的工具包 1. 步长、填充 a. 二维互相关运算&#xff08;corr2d&#xff09; b. 二维卷积层类&#xff08;Conv2D&#xff09; c. 模型测试 d. 代码整合 2. 输入输出通道 a…
阅读更多...
Arcgis克里金插值报错：ERROR 999999: 执行函数时出错。 表名无效。 空间参考不存在。 ERROR 010429: GRID IO 中存在错误

Arcgis克里金插值报错：ERROR 999999: 执行函数时出错。 表名无效。 空间参考不存在。 ERROR 010429: GRID IO 中存在错误

ERROR 999999: 执行函数时出错。 问题描述 表名无效。 空间参考不存在。 ERROR 010429: GRID IO 中存在错误: WindowSetLyr: Window cell size does not match layer cell size. name: c:\users\lenovo\appdata\local\temp\arc2f89\t_t164, adepth: 32, type: 1, iomode: 6, …
阅读更多...
智能合约漏洞，Dyna 事件分析

智能合约漏洞，Dyna 事件分析

智能合约漏洞&#xff0c;Dyna 事件分析 1. 漏洞简介 https://twitter.com/BlockSecTeam/status/1628319536117153794 https://twitter.com/BeosinAlert/status/1628301635834486784 2. 相关地址或交易 攻击交易 1&#xff1a; https://bscscan.com/tx/0x7fa89d869fd1b89e…
阅读更多...
算法通过村第十一关-位运算|青铜笔记|初始位运算

算法通过村第十一关-位运算|青铜笔记|初始位运算

文章目录 前言1. 数字在计算中的表示拓展&#xff1a;为什么要有原码、反码和补码? 2. 位运算规则2.1 与、或、异或和取反2.2 位移运算2.3 位移运算和乘除的关系2.4 位运算的常用技巧 总结 前言 提示&#xff1a;我的父亲从我出生起便认识我&#xff0c;可他对我的了解却那么少…
阅读更多...
西北主要河流水系（绿洲）流域（山区）及高程分类数据集（一）

西北主要河流水系（绿洲）流域（山区）及高程分类数据集（一）

最近收集整理的了西北地区主要河流水系&#xff08;绿洲&#xff09;流域&#xff08;山区&#xff09;及高程分类数据&#xff0c;&#xff0c;本次主要是新疆的河流水系&#xff08;绿洲&#xff09;流域&#xff08;山区&#xff09;及高程分类数据&#xff08;矢量&#xf…
阅读更多...
ThemeForest – Canvas 7.2.0 – 多用途 HTML5 模板

ThemeForest – Canvas 7.2.0 – 多用途 HTML5 模板

ThemeForest 上的 HTML 网站模板受到全球数百万客户的喜爱。与包含网站所有页面并允许您在 WP 仪表板中自定义字体和样式的 WordPress 主题不同&#xff0c;这些设计模板是用 HTML 构建的。您可以在 HTML 编辑器中编辑模板&#xff0c;但不能在 WordPress 上编辑模板&#xff0…
阅读更多...
机器人过程自动化(RPA)入门 7. 处理用户事件和助手机器人

机器人过程自动化(RPA)入门 7. 处理用户事件和助手机器人

在UiPath中，有两种类型的Robot用于自动化任何流程。一个是后台机器人，它在后台工作。它独立工作，这意味着它不需要用户的输入或任何用户交互。另一个是前台机器人，也被称为助理机器人。 本章介绍前台机器人。在这里，我们将了解自动化过程中通过简单按键、单击鼠标等触发事…
阅读更多...
【Vue】数据监视输入绑定

【Vue】数据监视输入绑定

hello&#xff0c;我是小索奇&#xff0c;精心制作的Vue系列持续发放&#xff0c;涵盖大量的经验和示例&#xff0c;如有需要&#xff0c;可以收藏哈 本章给大家讲解的是数据监视&#xff0c;前面的章节已经更新完毕&#xff0c;后面的章节持续输出&#xff0c;有任何问题都可以…
阅读更多...
Pikachu-xxe （xml外部实体注入漏洞）过关笔记

Pikachu-xxe （xml外部实体注入漏洞）过关笔记

Pikachu-xxe过关笔记 有回显探测是否有回显file:///协议查看本地系统文件php://协议查看php源代码&#xff08;无法查看当前网页代码&#xff0c;只能看别的&#xff09;http://协议爆破开放端口&#xff08;两者的加载时间不同&#xff09; 无回显第一步第二步第三步 运行结果…
阅读更多...
【面试题】2023前端面试真题之JS篇

【面试题】2023前端面试真题之JS篇

前端面试题库 &#xff08;面试必备&#xff09; 推荐&#xff1a;★★★★★ 地址&#xff1a;前端面试题库 表妹一键制作自己的五星红旗国庆头像&#xff0c;超好看 世界上只有一种真正的英雄主义&#xff0c;那就是看清生活的真相之后&#xff0c;依然热爱生活。…
阅读更多...
1.项目创建与角色移动

1.项目创建与角色移动

目录 1.创建项目 2.导入素材 3.搭建场景 4.创建玩家 1.创建项目 2.导入素材 3D GUNS | Guns Pack | 3D 武器 | Unity Asset Storehttps://assetstore.unity.com/packages/3d/props/weapons/3d-guns-guns-pack-228975 Prototyping Pack (Free) | 3D | Unity Asset S…
阅读更多...
外包公司干了2个月，技术倒退两年...

外包公司干了2个月，技术倒退两年...

先说一下自己的情况&#xff0c;本科生&#xff0c;19年通过校招进入杭州某软件公司&#xff0c;干了接近3年的功能测试&#xff0c;今年8月份&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了三年的功能测试…
阅读更多...
87、Redis 的 value 所支持的数据类型（String、List、Set、Zset、Hash）----＞List相关命令

87、Redis 的 value 所支持的数据类型（String、List、Set、Zset、Hash）----＞List相关命令

本次讲解要点&#xff1a; List相关命令&#xff1a;是指value中的数据类型 启动redis服务器&#xff1a; 打开小黑窗&#xff1a; C:\Users\JH>e: E:>cd E:\install\Redis6.0\Redis-x64-6.0.14\bin E:\install\Redis6.0\Redis-x64-6.0.14\bin>redis-server.exe redi…
阅读更多...
R语言绘制环状柱状堆积图+分组+显著性

R语言绘制环状柱状堆积图+分组+显著性

无叠加、显著性的代码&#xff1a; #设置工作环境 rm(listls()) setwd("D:/Desktop/0000/code-main/条形图")#加载R包 library(ggplot2) # Create Elegant Data Visualisations Using the Grammar of Graphics library(tidyverse) # Easily Install and Load the Ti…
阅读更多...
HarmonyOS/OpenHarmony原生应用-ArkTS万能卡片组件Badge

HarmonyOS/OpenHarmony原生应用-ArkTS万能卡片组件Badge

可以附加在单个组件上用于信息标记的容器组件。该组件从API Version 7开始支持。 支持单个子组件。子组件类型&#xff1a;系统组件和自定义组件&#xff0c;支持渲染控制类型&#xff08;if/else、ForEach和LazyForEach&#xff09;。 一、接口 方法1&#xff1a; Badge(value…
阅读更多...
最新文章

Copyright @ 2022~2023