小伙伴们大家晚上好，今天又是双更的一天。现在为大家带来堆的讲解。
1.完全二叉树以及堆的含义
首先大家应该明白什么是堆：堆是一种特殊的完全二叉树，又可以分为最大堆和最小堆。我首先展示什么是完全二叉树（以两张图作为例子）：
这张图片就展示了完全二叉树。
这张图片就不是完全二叉树。
那该如何区分呢？教大家一个简单的方法 ：从第一层开始，从左往右，看结点是否只有右子树而没有左子树，只要有一个结点符合就不是完全二叉树，若所有结点均不符合，则是完全二叉树。
最大堆：父节点比其子节点均大的完全二叉树
最小堆：父节点比其子节点均小的完全二叉树
这种性质能让我们很好的用数组模拟树结构，数组下标从1开始，那一个节点i的父节点就是i/2，其子节点就是2*i和2*i+1，（可能不存在子节点的某些）大家可以对照上图试验。
下面我们以最大堆为例展示代码。
2.最大堆的逐个插入
2.1问题分析
当插入第一个节点时，肯定是最大堆。当插入第二个元素时，只要检查其与其父节点的大小关系，当大于父节点则交换，否则无需交换。同理其它元素，一直交换到其比父节点小或已经位于树根（i==1）。别忘了heapsize++。
2.2代码展示
void heapinsert(int *heap,int x){
heap[++heapsize]=x;//下标从1开始记录
int i=heapsize;
while(i>1&&heap[i/2]<heap[i]){
swap(heap[i],heap[i/2]);
i=i/2;
}
}其中heapsize为最大堆节点个数。
3.最大堆的删除
3.1问题分析
当我们构建好了最大堆时，要想进行删除，则将堆顶删除，同时将heapsize--，并将heapsize位置节点放置堆顶，开始往下和其子节点比较，如果比其子节点最大值小，则交换。否则无需操作。直到其比子节点的最大值大或者其没有子节点。
3.2代码展示
int heapdelete(int *heap){
int x=heap[1];
int i=1,maxchild;
heap[i]=heap[heapsize--];
int left=i*2;
while(left<=heapsize){
if(left+1<=heapsize&&heap[left]<heap[left+1]){
maxchild=left+1;
}
else{
maxchild=left;
}
if(heap[i]<heap[maxchild]){
swap(heap[i],heap[maxchild]);
i=maxchild;
left=i*2;
}
else{
break;
}
}
return x;
}要注意右子树是否存在！！否则会越界。
4.最大堆某个节点的修改
4.1问题分析
要想修改某个节点的值并仍然维持最大堆，就要判断原值和新值的大小关系。若新值大，则其可能向上走（逐个插入的上沿操作）。若新值小，则其可能向下走（删除操作的下顺操作）。
4.2代码展示
void heapchange(int *heap,int i,int x){
if(heap[i]<x){
heap[i]=x;
while(i>1&&heap[i]>heap[i/2]){
swap(heap[i],heap[i/2]);
i=i/2;
}
}
if(heap[i]>x){
heap[i]=x;
int left=i*2,maxchild;
while(left<=heapsize){
if(left+1<=heapsize&&heap[left+1]>heap[left]){
maxchild=left+1;
}
else{
maxchild=left;
}
if(heap[maxchild]>heap[i]){
swap(heap[maxchild],heap[i]);
i=maxchild;
left=2*i;
}
}
}
}5.最大堆一次性构建
5.1问题分析
如果已经存在一颗完全二叉树，要想将其构造成最大堆，则将每个节点进行下沿操作即可（从节点下标最大处开始）。
5.2代码展示
void heapify(int *heap,int i){
int left=2*i,maxchild;
while(left<=heapsize){
if(left+1<=heapsize&&heap[left]<heap[left+1]){
maxchild=left+1;
}
else{
maxchild=left;
}
if(heap[i]<heap[maxchild]){
swap(heap[i],heap[maxchild]);
i=maxchild;
left=i*2;
}
else{
break;
}
}
}
//主函数部分
heapsize=5;
for(int i=heapsize;i>=1;i--){
heapify(heap,i);
}i代表第i个位置。
6.堆排序
6.1问题分析
如果只是考虑简单的话，一直进行delete操作取出其堆顶元素存入数组，最后将新数组逆序输出即可。但会引进额外的空间复杂度。因此我们更希望在原数组中操作。我们每次将堆顶和堆尾元素交换，heapsize--，再调用heapify（heap，1），这样堆的最大值就会被我们踢出堆，并且除去后仍然为堆，重复操作直至heapsize==0。最后将数组顺序输出即可。
6.2代码展示
void heapsort(int *heap){
swap(heap[1],heap[heapsize--]);
while(heapsize>0){
heapify(heap,1);
swap(heap[1],heap[heapsize--]);
}
}7.总代码（+测试）
#include<iostream>
using namespace std;
int heapsize=0;
//最大堆
//N*logN
void heapinsert(int *heap,int x){
heap[++heapsize]=x;//下标从1开始记录
int i=heapsize;
while(i>1&&heap[i/2]<heap[i]){
swap(heap[i],heap[i/2]);
i=i/2;
}
}
//N*logN
int heapdelete(int *heap){
int x=heap[1];
int i=1,maxchild;
heap[i]=heap[heapsize--];
int left=i*2;
while(left<=heapsize){
if(left+1<=heapsize&&heap[left]<heap[left+1]){
maxchild=left+1;
}
else{
maxchild=left;
}
if(heap[i]<heap[maxchild]){
swap(heap[i],heap[maxchild]);
i=maxchild;
left=i*2;
}
else{
break;
}
}
return x;
}
void heapchange(int *heap,int i,int x){
if(heap[i]<x){
heap[i]=x;
while(i>1&&heap[i]>heap[i/2]){
swap(heap[i],heap[i/2]);
i=i/2;
}
}
if(heap[i]>x){
heap[i]=x;
int left=i*2,maxchild;
while(left<=heapsize){
if(left+1<=heapsize&&heap[left+1]>heap[left]){
maxchild=left+1;
}
else{
maxchild=left;
}
if(heap[maxchild]>heap[i]){
swap(heap[maxchild],heap[i]);
i=maxchild;
left=2*i;
}
}
}
}
//将数组一次性构成最大堆
//每个节点位置向下遍历 N
void heapify(int *heap,int i){
int left=2*i,maxchild;
while(left<=heapsize){
if(left+1<=heapsize&&heap[left]<heap[left+1]){
maxchild=left+1;
}
else{
maxchild=left;
}
if(heap[i]<heap[maxchild]){
swap(heap[i],heap[maxchild]);
i=maxchild;
left=i*2;
}
else{
break;
}
}
}
//堆排序 n*logn
void heapsort(int *heap){
swap(heap[1],heap[heapsize--]);
while(heapsize>0){
heapify(heap,1);
swap(heap[1],heap[heapsize--]);
}
}
int main(){
int heap[10]={0,2,7,1,3,2};
// heapinsert(heap,2);
// heapinsert(heap,7);
// heapinsert(heap,1);
// heapinsert(heap,3);
// heapinsert(heap,2);
heapsize=5;
for(int i=heapsize;i>=1;i--){
heapify(heap,i);
}
// heapsort(heap);
// for(int i=1;i<=5;i++){
// cout<<heap[i]<<" ";
// }
// cout<<endl;
// heapchange(heap,3,9);
for(int i=1;i<=heapsize;i++){
cout<<heap[i]<<" ";
}
// cout<<endl;
// int x=heapdelete(heap);
// cout<<x<<endl;
// for(int i=1;i<=heapsize;i++){
// cout<<heap[i]<<" ";
// }
} 本次分享到此结束，感谢观看，多多点赞！！
标签：int,堆排序,heapsize,heap,left,maxchild,节点,结构 From： https://blog.csdn.net/weixin_74901355/article/details/143081167