【数据结构】堆，堆的实现，堆排序，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.niftyadmin.cn/n/5060662.html

相关文章

在MyBatisPlus中添加分页插件

在MyBatisPlus中添加分页插件

开发过程中&#xff0c;数据量大的时候&#xff0c;查询效率会有所下降&#xff0c;这时&#xff0c;我们往往会使用分页。 具体操作入下&#xff1a; 1、添加分页插件&#xff1a; package com.zhang.config;import com.baomidou.mybatisplus.extension.plugins.Pagination…
阅读更多...
数据结构与算法设计分析—— 数据结构及常用算法

数据结构与算法设计分析—— 数据结构及常用算法

目录 一、常用的数据结构&#xff08;一&#xff09;线性结构1、顺序表与链表2、栈3、队列 &#xff08;二&#xff09;非线性结构1、树与二叉树2、图3、集合 二、算法的基本概念&#xff08;一&#xff09;算法的特性&#xff08;二&#xff09;算法与数据结构 三、算法设计步…
阅读更多...
Openresty通过Lua+Redis 实现动态封禁IP

Openresty通过Lua+Redis 实现动态封禁IP

求背景 为了封禁某些爬虫或者恶意用户对服务器的请求&#xff0c;我们需要建立一个动态的 IP 黑名单。对于黑名单之内的 IP &#xff0c;拒绝提供服务。并且可以设置失效 1.安装Openresty&#xff08;编译安装&#xff09; wget https://openresty.org/download/openresty-1.…
阅读更多...
华为云云耀云服务器L实例评测｜部署在线图表和流程图绘制工具drawio

华为云云耀云服务器L实例评测｜部署在线图表和流程图绘制工具drawio

华为云云耀云服务器L实例评测&#xff5c;部署在线图表和流程图绘制工具drawio 一、云耀云服务器L实例介绍1.1 云服务器介绍1.2 优势及其应用场景1.3 支持镜像 二、云耀云服务器L实例配置2.1 重置密码2.2 服务器连接2.3 安全组配置 三、部署 drawio3.1 drawio 介绍3.2 Docker 环…
阅读更多...
ArcGIS 10.7软件安装包下载及安装教程！

ArcGIS 10.7软件安装包下载及安装教程！

【软件名称】&#xff1a;ArcGIS 10.7 【安装环境】&#xff1a;Windows 【下载链接 】&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1IwsPubYWGHd9ztmn45QLJA 提取码&#xff1a;1oeq 复制这段内容后打开百度网盘手机App&#xff0c;操作更方便哦 软件简介 ArcGIS…
阅读更多...
基于SpringBoot的师生共评的作业管理系统设计与实现

基于SpringBoot的师生共评的作业管理系统设计与实现

目录 前言 一、技术栈 二、系统功能介绍 课程管理 作业管理 作业互评 小组管理 作业管理 作业评分 三、核心代码 1、登录模块 2、文件上传模块 3、代码封装 前言 随着信息互联网信息的飞速发展&#xff0c;无纸化作业变成了一种趋势&#xff0c;针对这个问题开发一个…
阅读更多...
idea Springboot 校园助学贷款系统VS开发mysql数据库web结构java编程计算机网页源码maven项目

idea Springboot 校园助学贷款系统VS开发mysql数据库web结构java编程计算机网页源码maven项目

一、源码特点 springboot 校园助学贷款系统是一套完善的信息系统&#xff0c;结合springboot框架和bootstrap完成本系统&#xff0c;对理解JSP java编程开发语言有帮助系统采用springboot框架&#xff08;MVC模式开发&#xff09;&#xff0c;系统 具有完整的源代码和数据库&…
阅读更多...
web：[极客大挑战 2019]PHP

web：[极客大挑战 2019]PHP

题目 点进页面显示如下 根据页面提示&#xff0c;这个网站有备份文件&#xff0c;备份文件一般是bak文件格式&#xff0c;用dirsearch扫描 访问之后下载了一个文件 里面都是一些代码 在index.php中发现了一个类的文件&#xff0c;一个get传参&#xff0c;然后将传进的值进行反序…
阅读更多...
最新文章

Copyright @ 2022~2023