大佬们点点关注，点点赞？！
前言
在上篇博客中我们已经介绍了树和二叉树的相关概念，相信大家都已经清楚了树和二叉树的基本思想，下面我们就来着重看看二叉树堆的实现。
在看堆的实现，我们先看看二叉树的顺序存储
一 二叉树的顺序存储
二叉树的顺序存储就是以顺序表来实现的，也就是把二叉树装进数组中去实现，其中坐标代表着各个结点的位置，这里我们用到一个二叉树的性质，也就是上篇博客的性质4。如果我们存的二叉树的的结构不是完全二叉树或者是满二叉树，那么就会有空间的浪费。
那就会有人问了，为啥空的地方不存储呢， 这也是我们的性质4的原因，因为我们在存的时候，需要找的孩子结点，或者父亲结点，他们的下标很重要
比如知道父亲坐标找孩子：leftchild=parent*2+1，rightchild=parent*2+2;
知道孩子坐标找父亲：parent=(leftchild-1)/2; 这里不需要判断是左孩子还是右孩子，因为这里是向下取整（因为int型向下取整的特点），所以得到的结果都是一样的。
所以如果用顺序存储最好是完全二叉树比较好，这样避免了空间的浪费，在操作中用数组存储的也就只有完全二叉树，这也从而让堆实现起来！
二 堆的概念
这里的堆和操作系统里面的堆是两个东西，一个是数据结构，一个是管理系统的一块分区，这里要区分开来
现在有一段数据，然后我们把这些数据按完全二叉树的形式存储到我们的数组中，如果这组数组拆分成二叉树，符合父亲结点大于孩子结点的我们称之为大堆，反之称为小堆。
三 堆的性质
1.堆的某个结点值总是不大于或者不小于其父亲结点的
2.堆总是完全二叉树
3.堆中的结点如果没有左孩子，那么肯定没有右孩子
4.堆不一定有序
四 堆的实现
4.1 结构体的创建
首先堆是用顺序结构实现的，所以我们用的结构也就是和顺序表的形式是一样的
typedef int HeapDataType;
typedef struct Heap
{
HeapDataType * a;
int size;//当前大小
int capacity;//容量
}Heap;//这里和顺序表一样4.2 堆的初始化和销毁
这里的初始化也可以直接给空间，看个人的喜好
void HeapIint(Heap* hp)
{
assert(hp);//断言，因为hp不可能为空
hp->a = NULL;
hp->size = 0;
hp->capacity = 0;
}void HeapDestory(Heap* hp)
{
assert(hp);
free(hp->a);
hp->a = NULL;
hp->size = 0;
hp->capacity = 0;
}4.3 堆的插入
堆的插入，也就是在最后面插入一个数据，这个数据插入以后，这个堆就不是堆了，因为如果是小堆，我们插入的数据比根节点还小，那么这就不符合堆的性质，所以我们需要向上调整这个算法
向上调整的算法思路就是 把这个插入的数据和他这条路径上的所有数进行比较，如果小那么就交换，最终把破坏的结构恢复过来，也就是8，16，12这条路径，其他的没影响
向上调整需要用到父亲结点，也就是我们插入的是孩子，所以我们需要用孩子的坐标算出父亲的坐标
void HeapPush(Heap* hp, HeapDataType x)
{
assert(hp);
if (hp->size == hp->capacity)//开辟空间
{
int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;//
HeapDataType* tmp = (HeapDataType*)realloc(hp->a, sizeof(HeapDataType) * newcapacity);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
hp->a = tmp;
hp->capacity = newcapacity;
}
hp->a[hp->size] = x;//放入数据
hp->size++;
AdjustUp(hp->a, hp->size - 1);//向上调整
//这里的参数一个是数组，一个是插入数据的坐标
}4.4 向上调整算法
void AdjustUp(HeapDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child>0)//当孩子在第一个位置的时候也就没必要比较了所以是>0
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);//交换函数，进行交换
child = parent;//换位置，继续比较
parent = (child - 1) / 2;
}
else
{
break;//如果符合堆的性质，那么不玩了，直接退出来就行
}
}
}这里while的条件判断可能有的人会用parent>=0去比较，这虽然可以，但是纯属巧合，具有风险，这里还是推荐使用上面的条件判断
这里函数的参数没用传堆的结构，只是传了一个数组的结构，这是因为这个的算法应用面比较广，所以不能限制死了
4.5 交换函数
void Swap(HeapDataType* p1, HeapDataType* p2)
{
HeapDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}4.6 堆的删除
这里堆的删除如果是删最后一个元素那么就会变的毫无价值，所以我们删除第一个元素！！
如果我们删除第一个元素，那么我们的堆也就被破坏了，有两种方法，第一种也就是挪动覆盖，和数组一样，但是这样第二个元素就变成了根结点，那么他的兄弟就变成了他的儿子？！然后我们再重新建堆，因为他们的关系全乱了，所以只能这样，建堆也就是上面的操作想想都复杂。
假如之前的堆是这样的
，那么调整挪动后就变成这样了
很明显这已经是发生了很大的改变。
第二种方法就是向下调整，也就是不删除第一个元素，先把他和最后一个元素交换，把最后一个元素删除，然后再让第一个元素向下调整比较，比他小的就交换（因为是小堆），最后形成的结构还是小堆，同时也成功把第一个元素删除了
void HeapPop(Heap* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
Swap(&hp->a[0], hp->a[hp->size - 1]);//交换，然后删除最后一个元素
hp->size--;
AdjustDown(a, hp->size, 0);
}4.7 向下调整算法
这里的我们得到的是父亲结点，需要算出孩子结点，所以我们传参的时候传父亲的下标，同时由于在比较过程中需要有一个跳出循环的条件，所以我们需要把n传进去
void AdjustDown(HeapDataType* a, int n, int parent)
{
int child = parent*2+1;
while (child<n)//如果孩子都大于等于n了，说明比较已经到最后了，也没必要比了，再比就越界了
{
if (child + 1 < n && a[child + 1] < a[child])//这里需要算出哪个孩子比较小（小堆）
//child+1就是右孩子
//同时右孩子可能不存在，所以要有前面的判断条件
{
child++;
}
if (a[child] < a[parent])//下面的就和向上调整的算法差不多了
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent*2+1;
}
else
{
break;
}
}
}有了上面的操作，那么下面的操作也就变得比较简单了
4.8 取堆顶元素
HeapDataType HeapTop(Heap* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
return hp->a[0];
}4.9 堆的数据判空
bool HeapEmpty(Heap* hp)
{
assert(hp);
return hp->size == 0;
}4.10 堆的测试
int main()
{
Heap hp;
HeapIint(&hp);
int a[] = { 12 ,15, 16, 30, 45, 25, 8 };
for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
HeapPush(&hp, a[i]);//把数据一个个插入进去，最终形成堆
}
while (!HeapEmpty(&hp))
{
int top = HeapTop(&hp);//取出第一个元素
cout << top << " ";//打印
HeapPop(&hp);//然后删除第一个元素，但是后面还是保持堆，因为采取了向下调整去维护
}
HeapDestory(&hp);
return 0;
}
打印结果： 8 12 15 16 25 30 45
但是我们的本意是堆排序，并不是把这堆数据打印出来，所以我们可以这样
int main()
{
Heap hp;
HeapIint(&hp);
int a[] = { 12 ,15, 16, 30, 45, 25, 8 };
for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
HeapPush(&hp, a[i]);
}
int i = 0;
while (!HeapEmpty(&hp))
{
a[i++] = HeapTop(&hp);//把取出来的数据放进数组里面去
HeapPop(&hp);
}
HeapDestory(&hp);
for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
cout << a[i] << " ";
}
return 0;
}但是我们又会发现这样是不是太麻烦了每次都要建一个堆，才能排序
那我们就有了下面的方法
五 堆排序
5.1 向上调整建堆
假设给定一个数组，那么我们从第二个元素开始，依次去比较，比如先给第一个元素，那么这肯定是个堆。然后给第二个元素，和第一个元素比较，比较完以后，那么这个还是一个堆，然后依次放入元素，最后就形成了堆，并且还是在数组里面的
for (int i = 1; i < n; i++)//第一个元素不用比较，所以从第二个元素开始
{
AdjustUp(a, i);
}5.2 向下调整建堆
向下调整建堆我们需要从最后一个父亲结点开始， 因为最后的元素肯定都是叶结点，开始的时候他们不用去比较。比较完以后，那么当前的子树就是一个堆，那么继续往向上一个结点去向下调整，最后只剩根结点，然后进行一次向下调整即可
for (int i = (n - 1 - 1) / 2; i >= 0; i--)//从最后一个父亲结点开始
{
AdjustDown(a, n, i);
}
可能图画的比较抽象，但是画的没错！
既然有两种方法那可能有一个快一个慢，这里可以直接得出向下调整比较快时间复杂度为O(N),向上调整是N*O(logN);至于具体的解释这里就不说明了，自己也可以感觉一下，假如叶子结点有N个，那么向上调整会比向下调整的要多
5.3 排序
建完堆以后我们就要开始排序了，排序用向下调整算法，因为向下调整可以选出最大的和最小的数，因为他可以跟他的左右孩子比较，向上调整就不具备这样的优势
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);//这里的end是一直在变动的，因为排好的元素不需要进行比较了
end--;
}
for (int i = 0; i < n; i++)
cout << a[i] << " ";
}如果是升序：建大堆
如果是降序：建小堆
因为后面的排序会把第一个元素放到后面，所以排完以后，就会变成有序的序列
5.3 topK问题
如果我们要求从一个数组中选出前k个最大的数或者最小的数，那么我们的思路是直接建立一个大堆然后依次pop9次就行，因为最后一个不用pop，直接拿出来就行，每次pop,都是最大的数所以能够完成，虽然这行得通，但是如果是几亿的数，这种方法也会很慢
所以有了下面的改进
我们可以先建立一个k个数的小堆，然后与后面N-k个元素进行比较，不满足就替换堆顶元素，然后先下调整，这里调整的范围是K，不是N,所有比较大的数会在这个小堆的底部，最后形成一个k个数最大的小堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, k, i);//建小堆
}
for (int i = k; i < n; i++)
{
if (a[i] > a[0])//选出k个最大的数
{
a[0] = a[i];
AdjustDown(a, k, 0);
}
}
for (int i = 0; i < k; i++)
cout << a[i] << " ";
}以上便是堆排序的全内容 希望大家喜欢，都看到这里了
版权声明：本文为博主作者：我的电脑会说烫原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/m0_74092462/article/details/137233081
