【调整堆】（C++ 代码实现注释详解）

自定义结构体：

#define sz 105
typedef struct node{
	int length;
	int l[sz];
}SqList;

调整堆的函数：

HeapAdjust函数思路说明：

//目标：将以s为根的子树调整为大根堆

//具体操作：将路径上比s大的都往上移动,s往下移动,直到遇到比s还小的,就“放下”s

void HeapAdjust(SqList &L, int s, int m)//将以s为根的子树调整为大根堆<=>将路径上比s大的都往上移动,s往下移动,直到遇到比s还小的,就放下s
{
	int rc = L.l[s];
	for(int j = 2*s; j <= m; j *= 2)//j指向s的左子树
	{
		if(j<m && L.l[j] < L.l[j+1] ) j+=1;//j指向s的子树中较大的那个
		if(rc >= L.l[j]) break;//此时接着执行L.l[s] = rc; 便可实现上述目标
		L.l[s] = L.l[j]; s = j;//将路径上比s大的都往上移动,s往下移动
	}
	L.l[s] = rc;
}

void CreateHeap(SqList &L)
{
	int n = L.length;
	for(int i=n/2; i>0; i--)//从n/2向下取整得到的整数所对应的结果开始,依次进行调整堆的操作
	{						//关于为什么从n/2开始: 因为在n/2后面的节点都是叶子结点,不需要调整
		HeapAdjust(L, i, n);
	}
}

完整代码：

#include<bits/stdc++.h>
using namespace std;
#define sz 105
typedef struct node{
	int length;
	int l[sz];
}SqList;

void HeapAdjust(SqList &L, int s, int m)//将以s为根的子树调整为大根堆<=>将路径上比s大的都往上移动,s往下移动,直到遇到比s还小的,就放下s
{
	int rc = L.l[s];
	for(int j = 2*s; j <= m; j *= 2)//j指向s的左子树
	{
		if(j<m && L.l[j] < L.l[j+1] ) j+=1;//j指向s的子树中较大的那个
		if(rc >= L.l[j]) break;//此时接着执行L.l[s] = rc; 便可实现上述目标
		L.l[s] = L.l[j]; s = j;//将路径上比s大的都往上移动,s往下移动
	}
	L.l[s] = rc;
}

void CreateHeap(SqList &L)
{
	int n = L.length;
	for(int i=n/2; i>0; i--)//从n/2向下取整得到的整数所对应的结果开始,依次进行调整堆的操作
	{						//关于为什么从n/2开始: 因为在n/2后面的节点都是叶子结点,不需要调整
		HeapAdjust(L, i, n);
	}
}

int main()
{
	SqList L;
	L.length = 0;
	srand(time(NULL));//随机数种子
	for(int i=1; i<=100; i++)
	{
		int rand_int = rand()%100;//生成0 ~ 99的随机整数
		L.l[i] = rand_int;
		cout<<rand_int<<" "; 
		L.length++;
	}
	CreateHeap(L);
	cout<<"\n"<<"after Adjustment: "<<endl;
	for(int i=1; i<=L.length; i++ )
	{
		cout<<L.l[i]<<" ";
	}
	return 0;
}

运行结果示例：