【数据结构】堆与堆排序
前言 本篇博客我们来仔细说一下二叉树顺序存储的堆的结构，我们来看看堆到底如何实现，以及所谓的堆排序到底是什么 💓 个人主页：小张同学zkf ⏩ 文章专栏：数据结构 若有问题 评论区见📝 🎉欢迎大家点赞👍收藏⭐文章
1.二叉树的顺序结构
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆 ( 一种二叉树 ) 使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
2.堆的概念及结构
如果有一个关键码的集合K={k0,k1,k2,k3,k4,……,kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：ki<=k2*i+1且ki<=k2*i+2(ki>=k2*i+1且ki>=k2*i+2)i=0,1,2……,则称为小堆
将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。
堆的性质： 堆中某个结点的值总是不大于或不小于其父结点的值； 堆总是一棵完全二叉树。
3.堆的实现
3.1堆向下调整算法
现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提： 左右子树必须是一个堆，才能调整 。
3.2堆的创建
下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根结点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子结点的子树开始调整，一直调整到根结点的树，就可以调整成堆。
3.3建堆时间复杂度
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明 ( 时间复杂度本来看的就是近似值，多几个结点不影响最终结果) ：
因此：建堆的时间复杂度为O(N)。
3.3堆的插入
先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆
3.4堆的删除
删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
3.5堆的代码实现
.h文件
typedef int HPDataType;
typedef struct Heap
{
HPDataType* _a;
int _size;
int _capacity;
}Heap;
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);.c文件
#define _CRT_SECURE_NO_WARNINGS 1
#include "堆的实现.h"
void HeapInit(HP* php)
{
assert(php);
php->_a = NULL;
php->_capacity = php->_size = 0;
}
void HeapDestory(HP* hp)
{
assert(hp);
free(hp->_a);
hp->_a = NULL;
hp->_capacity = hp->_size = 0;
}
void swap(HPDataType* x1, HPDataType* x2)
{
HPDataType as = *x1;
*x1 = *x2;
*x2 = as;
}
void adjustup(HPDataType* a, int child)
{
int father = (child - 1) / 2;
while (child > 0)
{
if (a[child] < a[father])
{
swap(&a[child], &a[father]);
child = father;
father = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapPush(HP* hp, HPDataType x)
{
assert(hp);
if (hp->_capacity == hp->_size)
{
int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
HPDataType* newa = (HPDataType*)realloc(hp->_a,newcapacity * sizeof(HPDataType));
if (newa == NULL)
{
perror("malloc");
return;
}
hp->_a = newa;
hp->_capacity = newcapacity;
}
hp->_a[hp->_size] = x;
hp->_size++;
adjustup(hp->_a, hp->_size-1);
}
void adjustdown(HPDataType* a, int n, int parent)
{
// 先假设左孩子小
int child = parent * 2 + 1;
while (child < n) // 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 HeapPop(HP* hp)
{
assert(hp && hp->_size);
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];
}
int HeapSize(HP* hp)
{
assert(hp);
return hp->_size;
}
int HeapEmpty(HP* hp)
{
assert(hp);
return hp->_size == 0;
}4.堆排序
堆排序即利用堆的思想来进行排序，总共分为两个步骤：
1. 建堆
升序：建大堆
降序：建小堆
2. 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
堆排序的代码实现
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void swap(int* x1, int* x2)
{
int as = *x1;
*x1 = *x2;
*x2 = as;
}
void adjustup(int* a, int child)
{
int father = (child - 1) / 2;
while (child > 0)
{
if (a[child] < a[father])
{
swap(&a[child], &a[father]);
child = father;
father = (child - 1) / 2;
}
else
{
break;
}
}
}
void adjustdown(int* a, int n, int parent)
{
// 先假设左孩子小
int child = parent * 2 + 1;
while (child < n) // 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 = 1; i < n; i++)//向上建堆
//{
// adjustup(a, i);
//}
for (int i = (n - 1 - 1) / 2; i >= 0;i--)//向下建堆
{
adjustdown(a,n,i);
}
//排序
int douwenze = n - 1;
while (douwenze>0)
{
swap(&a[0], &a[douwenze]);
adjustdown(a, douwenze, 0);
douwenze--;
}
}
int main()
{
int a[] = { 2,4,6,34,13,67,23,56 };
HeapSort(a,sizeof(a)/sizeof(int));
for (int i = 0; i < sizeof(a) / sizeof(int);i++)
{
printf("%d ", a[i]);
}
}注意这个代码，并不需要构建堆的数据结构，直接用堆数据结构里的向下调整函数就行
5.TOP-K问题
TOP-K 问题：即求数据结合中前 K 个最大的元素或者最小的元素，一般情况下数据量都比较大 。
比如：专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。
对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了 ( 可能数据都不能一下子全部加载到内存中) 。最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前 K 个元素来建堆
前 k 个最大的元素，则建小堆
前 k 个最小的元素，则建大堆
2. 用剩余的 N-K 个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余 N-K 个元素依次与堆顶元素比完之后，堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素。
假如文件里随机生成了N个数里面，打印出最大的前K个，先将这些数从文件里读取出来，再将前K个数建小堆，剩下的N-K个数据就与堆顶数据一个个比较，若大于堆顶数据，将这个数赋值给堆顶数据，然后向下调整堆，再往后比较，代码如下
结束语 本篇博客主要说了堆的有关知识，但二叉树这一块还有很多东西没总结，堆也只是二叉树顺序储存的一种结构，下片博客我们继续深入二叉树的有关知识总结 OK，本篇博客结束！！！
腾讯云开发者
