数据结构——堆的介绍以及应用
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
前言对于数据结构而言大多存在着对应的物理结构和逻辑结构而我们一开始介绍的顺序表链表栈队列等的物理结构和逻辑结构还是比较类似的。今天要介绍的堆则有所不同其物理结构是数组而逻辑结构是完全二叉树并且其应用还是比较重要的我们需要好好掌握其中的知识内容。
目录
一堆的简单介绍
(1) 概念
如果有一个集合K = {k0k1 k2…kn-1}把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足K(i)<= K(2i+1) 且 K(i)<=K(2i+2) (i表示物理结构中数组的下标) 则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。
(2) 性质
1. 堆中某个节点的值总是不大于或不小于其父节点的值
eg: 小堆K(i)<= K(2i+1) 且 K(i)<=K(2i+2) 大堆: K(i)>= K(2i+1) 且 K(i)>=K(2i+2)
2. 堆总是一棵完全二叉树(具体见下)。
(3) 结构
二堆的实现
(1) 基本框架的搭建
1. 测试函数(自己设置)
#include "Heap.h"
void HeapTest1(int* arr,int n)//堆相关接口函数的测试
{
HP hp;//定义一个堆
HeapInit(&hp);//初始化堆
int i = 0;
for (i = 0;i < n;i++)
{
HeapPush(&hp, arr[i]);//将数组元素入堆
}
HeapPrint(&hp, n);//打印堆
printf("%d\n", HeapTop(&hp));//打印堆顶数据
HeapPop(&hp);
HeapPop(&hp);
HeapPop(&hp);//删除三次堆内的数据
HeapPrint(&hp, (&hp)->size);//删除后再打印
printf("%d\n", HeapTop(&hp));//打印堆顶数据
}
int main()
{
int arr[] = { 70,33,28,40,55,60,59,20,44 };
int sz = sizeof(arr) / sizeof(arr[0]);
HeapTest1(arr, sz);//测试堆的一些接口函数
return 0;
}2. 堆的初始化
void HeapInit(HP* hp)
{
assert(hp);
hp->a = NULL;
hp->size = hp->capacity = 0;
}3. 数据的打印
void HeapPrint(HP* hp,int n)
{
int i = 0;
for (i = 0;i < n;i++)
{
printf("%d ", hp->a[i]);
}
printf("\n");
}4. 获取堆顶数据
HPDataType HeapTop(HP* hp)
{
assert(hp);
return hp->a[0];
}5. 堆的销毁
void HeapDestroy(HP* hp)
{
assert(hp);
free(hp->a);
hp->a = NULL;
hp->size = hp->capacity = 0;
}6. 数据的交换
void Swap(HPDataType* px, HPDataType* py)
{
HPDataType tmp = *px;
*px = *py;
*py = tmp;
}如果实现了顺序表的结构完成大致框架难度就不大接下来就要实现堆这个数据结构与顺序表不同之处。
(2) 数据入堆的实现 (向上调整算法)
入堆其实就是将一个数据加在数组最后一个元素后面依旧需要扩容插入数据。
void HeapPush(HP* hp, HPDataType x)
{
assert(hp);
if (hp->size == hp->capacity)
{
int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
hp->a = tmp;
hp->capacity = newCapacity;
}
hp->a[hp->size] = x;
hp->size++;
//AdjustUp(hp->a,hp->size - 1);//向上调整,建堆(需要传递最后一个元素的下标)
}但是由堆的第一个性质我们知道堆是有特殊结构的那么在插入数据之后堆的结构很有可能会被破坏(使得不是一个堆了)所以入堆操作不仅仅需要将数据插入数组我们还要对插入数据之后的数组进行调整使保证它的堆结构那么就要涉及下面的向上调整算法了。
向上调整算法
1. 思路
要实现向上调整算法首先要明确其思路有以下三点
(1)首先我们要清楚向上调整的对象:
从插入数据的第一个父节点开始一直到祖先节点的一条路径上的所有父节点
(2)其次是向上调整的条件
当子节点小于或大于(由堆的大小决定)对应的父节点时就进行交换调整(3)最后是要明确停止调整的条件有两个条件会停止向下调整
1. 当祖先节点作为子节点时 2. 调整路径上遇到子节点与父节点不满足对应大小关系时
2. 图示
3. 代码实现
void AdjustUp(HPDataType* a,int child)//向上调整算法
{
int parent = (child - 1) / 2; //利用到了二叉树中以知父节点求子节点的公式
//当满足两个条件就停止向上调整
while (child > 0) //1.child移动到祖先节点
{
//相当于子节点小于父节点,开始向上调整
if (a[child] < a[parent]) //这里小于就调表示原本是小堆, 如果原本是大堆, 改成大于号即可
{
Swap(&a[child], &a[parent]); //交换
child = parent; //child向上移动
parent = (child - 1) / 2; //继续计算对应的父节点
}
else
{
break; //2.子节点不小于(或大于)父节点(交换关系不满足)
}
}
}
(3) 堆顶数据的删除 (向下调整算法)
此出的pop函数是对堆顶数据的删除(即数组的第一个元素)但在删除之后堆的结构会大变使其不再是一个堆所以在删除时我们要想到一定的方法使得既能删除堆顶数据又能够保持堆的结构不变。
解决方法
1. 将堆顶的数据跟数组最后一个数据交换
2. 然后删除数组最后一个数据
3. 再进行向下调整算法
完成这三步就可以很好地实现堆顶数据的删除了。那这里又要涉及一个向下调整算法的实现具体见下。
void HeapPop(HP* hp)//删除堆顶元素
{
assert(hp);
assert(hp->size > 0);
Swap(&hp->a[0], &hp->a[hp->size - 1]); //先交换
hp->size--; //删除最后一个数据
AdjustDown(hp->a, hp->size, 0); //调堆:从堆顶开始向下调整(需要传递数组元素个数,堆顶元素下标)
}
向下调整算法
1. 思路
向下调整算法与向上调整算法类似完成以下两步即可
(1) 调整过程的实现
1. 将交换后新的祖先节点作为父节点比较它两个子节点的大小原来是大堆就选择较大的子节点小堆就选择较小的子节点
2. 将父节点与选择好的子节点进行比较满足需求的大小关系就进行交换
(3) 调整停止的条件
1. 所得新的子节点下标超过数组下标2. 调整过程中子节点与父节点不满足交换的大小关系
2. 图示
3. 代码实现
void AdjustDown(HPDataType* a, int n, int parent)//向下调整
{
int child = parent * 2 + 1; //以知父节点算子节点的公式
//当满足两个条件就停止向下调整
while (child < n)//1.下标超过数组元素个数
{
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//2.父子节点大小关系不符合时
{
break;
}
}
}三堆的两个经典应用
(1) Top-K问题
1. 简单介绍
Top-K问题即求数据集合N中前K个最大的元素或者最小的元素一般情况下数据量N都比较大。
2. 实现思路
Top-K问题的解决方法有很多其中最好的一种就是利用堆的结构特性使用堆解决。具体思路(eg:选N个数中最大的K个数)
(1) 要选N个数中最大的K个数先用N个数的前K个数建立小堆
(2) 再将剩余的N-K个数与堆顶的元素进行比较如果比堆顶元素大就进行替换再调整堆维持原来的小堆结构(这样可以将更大的数沉在二叉树结构的下部)
最后堆中剩余的K个数就是要选的k个数。
3. 代码实现
//(1)topK问题:选取N个元素中最大(小)的K个
//解决方法:选小建大堆,选大建小堆,剩余元素再与堆顶元素进行比较
void TopKPrint(HPDataType* a, int n, int k)
{
HP hp;//定义堆
HeapInit(&hp);
//1.选大数建小堆,将n个数的前k个数建成小堆
for (int i = 0;i < k;i++)
{
HeapPush(&hp, a[i]);//将前k个数插入堆中,建堆
}
//2.将n个数中剩余的n-k个数依次与堆顶的元素进行比较,更大就入堆,再调整堆
for (int i = k;i < n;i++)
{
if (a[i] > HeapTop(&hp))
{
HeapPop(&hp);//删除堆顶元素
HeapPush(&hp, a[i]);//再入堆(push函数中涉及了调堆的过程)
}
}
//3.打印
HeapPrint(&hp, k);
HeapDestroy(&hp);
}
void TesttopK()//选出n个数中最大的10个数(测试)
{
int n = 10000;
int* a = (int*)malloc(sizeof(int) * n);
if (a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
srand(time(0));
for (int i = 0; i < n; ++i)
{
a[i] = rand() % 1000000; //产生随机的n个数一定比1000000小
}
a[5] = 1000000 + 1;
a[1231] = 1000000 + 2;
a[531] = 1000000 + 3;
a[5121] = 1000000 + 4;
a[115] = 1000000 + 5;
a[2335] = 1000000 + 6;
a[9999] = 1000000 + 7;
a[76] = 1000000 + 8;
a[423] = 1000000 + 9;
a[3144] = 1000000 + 10;
TopKPrint(a, n, 10);
}
int main()
{
TestTopK();
return 0;
}(2) 堆排序
1. 简单介绍
堆排序其实就是一种利用堆的结构进行的排序算法。
2. 实现思路:
(1) 排降序建小堆(利用类似二叉树子树递归的思想)
(2) 将堆顶元素与堆(数组)的最后一个元素进行交换(此时最后一个元素就是最小的一个)
(3) 不将最后一个元素看成堆内的元素调整堆
(4) 循环进行上述操作直至排序完毕
3. 图示
4. 代码实现
//堆排序,排降序建小堆 1.建堆 + 2.调堆
void HeapSort(HPDataType* a, int n)
{
//1.将数组内元素从最后一个非叶子节点开始一直向前,将各个子树利用向下调整算法构建成堆 O(N)
int i = 0;
//(n-1-1)/2表示最后一个非叶子节点的下标,根节点也要执行(i=0不可少)
for (i = (n - 1 - 1) / 2;i >= 0;i--)
{
AdjustDown(a, n, i);
}
//2.利用堆删除的思想,将堆顶元素(最小)与最后一个元素进行交换,然后不将最后一个元素看成堆内元素
//再通过向下调整,选出次小的一个,继续交换,循环执行,直到排到第一个元素为止 O(N*logN)
for (i = n - 1;i > 0;i--)
{
Swap(&a[0], &a[i]);
AdjustDown(a, i, 0);//注意堆的最后一个元素由i的变化而变化,即实参不是n-1而是i
}
}四完整代码展示
(1) Test.c
#include "Heap.h"
void HeapTest1(int* arr,int n)
{
HP hp;//定义一个堆
HeapInit(&hp);//初始化堆
int i = 0;
for (i = 0;i < n;i++)
{
HeapPush(&hp, arr[i]);//将数组元素入堆
}
HeapPrint(&hp, (&hp)->size);//打印堆内数据
printf("%d\n", HeapTop(&hp));//打印堆顶数据
HeapPop(&hp);
HeapPop(&hp);
HeapPop(&hp);//删除三次堆内的数据
HeapPrint(&hp, (&hp)->size);//删除后再打印
printf("%d\n", HeapTop(&hp));//打印堆顶数据
}
void TesttopK()//选出n个数中最大的10个数
{
int n = 10000;
int* a = (int*)malloc(sizeof(int) * n);
if (a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
srand(time(0));
for (size_t i = 0; i < n; ++i)
{
a[i] = rand() % 1000000;
}
a[5] = 1000000 + 1;
a[1231] = 1000000 + 2;
a[531] = 1000000 + 3;
a[5121] = 1000000 + 4;
a[115] = 1000000 + 5;
a[2335] = 1000000 + 6;
a[9999] = 1000000 + 7;
a[76] = 1000000 + 8;
a[423] = 1000000 + 9;
a[3144] = 1000000 + 10;
TopKPrint(a, n, 10);
}
int main()
{
int arr[] = { 70,33,28,40,55,60,59,20,44 };
int sz = sizeof(arr) / sizeof(arr[0]);
for (int i = 0;i < 9;i++)
{
printf("%d ", arr[i]);
}
printf("\n");
HeapTest1(arr, sz);//测试堆的一些接口函数
TesttopK();//测试topK问题
HeapSort(arr, sz);//堆排序
for (int i = 0;i < 9;i++)
{
printf("%d ", arr[i]);
}
return 0;
}(2) Heap.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>
//定义堆内数据的数据类型
typedef int HPDataType;
//定义一个数组结构作为堆的物理结构(堆的实际结构是一颗完全二叉树)
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
} HP;
//接口函数的定义
void HeapInit(HP* hp);//初始化
void HeapPrint(HP* hp,int n);//打印
void HeapPush(HP* hp, HPDataType x);//向堆内插入数据,需要利用向上调整算法保证堆的性质
void HeapPop(HP* hp);//删除堆顶元素,需要利用向下调整算法保证堆的性质
void AdjustDown(HPDataType* a, int n, int parent);//向下调整算法
void AdjustUp(HPDataType* a, int child);//向上调整算法
HPDataType HeapTop(HP* hp);//获取堆顶数据
void HeapDestroy(HP* hp);//销毁堆
//堆的应用
void TesttopK();//测试topK问题
void TopKPrint(HPDataType* a, int n, int k);//topK问题的实现
void HeapSort(HPDataType* a, int n);//堆排序的实现(3) Heap.c
#include "Heap.h"
void Swap(HPDataType* px, HPDataType* py)
{
HPDataType tmp = *px;
*px = *py;
*py = tmp;
}
void HeapInit(HP* hp)
{
assert(hp);
hp->a = NULL;
hp->size = hp->capacity = 0;
}
void HeapPrint(HP* hp,int n)
{
int i = 0;
for (i = 0;i < n;i++)
{
printf("%d ", hp->a[i]);
}
printf("\n");
}
void AdjustUp(HPDataType* a,int child)//向上调整算法
{
int parent = (child - 1) / 2; //利用到了二叉树中以知父节点求子节点的公式
//当满足两个条件就停止向上调整
while (child > 0)//1.child移动到祖先节点
{
//相当于子节点小于父节点,开始向上调整
if (a[child] < a[parent])//这里小于就调表示原本是小堆, 如果原本是大堆, 改成大于号即可
{
Swap(&a[child], &a[parent]);//交换
child = parent;//child向上移动
parent = (child - 1) / 2;//继续计算对应的父节点
}
else
{
break;//2.子节点不小于(或大于)父节点
}
}
}
void AdjustDown(HPDataType* a, int n, int parent)//向下调整
{
int child = parent * 2 + 1; //以知父节点算子节点的公式
//当满足两个条件就停止向下调整
while (child < n)//1.下标超过数组元素个数
{
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//2.父子节点大小关系不符合时
{
break;
}
}
}
void HeapPush(HP* hp, HPDataType x)
{
assert(hp);
if (hp->size == hp->capacity)
{
int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
hp->a = tmp;
hp->capacity = newCapacity;
}
hp->a[hp->size] = x;
hp->size++;
AdjustUp(hp->a,hp->size - 1);//向上调整
}
void HeapPop(HP* hp)//删除堆顶元素
{
assert(hp);
assert(hp->size > 0);
Swap(&hp->a[0], &hp->a[hp->size - 1]); //先交换
hp->size--; //删除最后一个数据
AdjustDown(hp->a, hp->size, 0); //从堆顶开始向下调整(调堆)
}
HPDataType HeapTop(HP* hp)
{
assert(hp);
return hp->a[0];
}
void HeapDestroy(HP* hp)
{
assert(hp);
free(hp->a);
hp->a = NULL;
hp->size = hp->capacity = 0;
}
//堆的两个应用: 1topK问题 (2)堆排序
//(1)topK问题:选取N个元素中最大(小)的K个
//解决方法:选小建大堆,选大建小堆,剩余元素再与堆顶元素进行比较
void TopKPrint(HPDataType* a, int n, int k)
{
HP hp;//定义堆
HeapInit(&hp);
//1.选大数建小堆,将n个数的前k个数建成小堆
for (int i = 0;i < k;i++)
{
HeapPush(&hp, a[i]);//将前k个数插入堆中,建堆
}
//2.将n个数中剩余的n-k个数依次与堆顶的元素进行比较,更大就入堆,再调整堆
for (int i = k;i < n;i++)
{
if (a[i] > HeapTop(&hp))
{
HeapPop(&hp);//删除堆顶元素
HeapPush(&hp, a[i]);//再入堆(push函数中涉及了调堆的过程)
}
}
//3.打印
HeapPrint(&hp, k);
HeapDestroy(&hp);
}
//(2)堆排序,排降序建小堆,再排序;排升序建大堆,再排序 1.建堆 + 2.调堆
void HeapSort(HPDataType* a, int n)
{
//1.将数组内元素从最后一个非叶子节点开始,将各个子树利用向下调整算法构建成堆 O(N)
int i = 0;
//(n-1-1)/2表示最后一个非叶子节点的下标,根节点也要执行(i=0不可少)
for (i = (n - 1 - 1) / 2;i >= 0;i--)
{
AdjustDown(a, n, i);
}
//2.利用堆删除的思想,将堆顶元素(最小)与最后一个元素进行交换,然后不将最后一个元素看成堆内元素
//再通过向下调整,选出次小的一个,继续交换,循环执行,直到排到第一个元素为止 O(N*logN)
for (i = n - 1;i > 0;i--)
{
Swap(&a[0], &a[i]);
AdjustDown(a, i, 0);//注意堆的最后一个元素由i的变化而变化,即实参不是n-1而是i
}
}总结
在本次分享的内容中最重要的就是其中的向上向下调整算法理解这两步其他只要明白了思路实现起来也简单那这次的分享就到这里结束希望对各位有些许帮助再见。
