什么是堆？堆的实现以及堆排序（C语言版） 超详细！

堆，英语heap，是计算机科学中的一种特别的完全二叉树。

来源：

堆始于J. W. J. Williams在1964年发表的堆排序（heap sort），当时他提出了二叉堆树作为此算法的数据结构。

性质：

• 任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）。
• 堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。

若母节点的值恒小于等于子节点的值，此堆称为最小堆/小顶堆（min heap）
若母节点的值恒大于等于子节点的值，此堆称为最大堆/大顶堆（max heap）
在堆中最顶端的那一个节点，称作根节点（root node），根节点本身没有母节点（parent node）。

#include<stdio.h>
#include<stdlib.h>
#define maxn 100000 + 7//可以存放的树的结点数目
int n;
int h[maxn];//存放指向树结点地址的指针

int Swap(int x, int y)//间接交换结点
{
	int tmp = h[x];
	h[x] = h[y];
	h[y] = tmp;
}

//下沉操作
void shift_down(int cur)//传入当前结点的所在位置
{
	if(cur * 2 > n) return ;//如果说不是父节点 退出
	int pos = cur * 2;//如果有孩子结点，让pos指向其左孩子
	if(cur * 2 + 1 <= n && h[cur * 2 + 1] < h[pos])//如果右结点存在并且右结点的值小于左结点的数值
	{
		pos = cur * 2 + 1;//让pos为较小的那个结点
	}
	if(h[cur] > h[pos])//接着比较当前结点与较小的孩子结点哪个小，如果孩子结点小
	{
		Swap(cur, pos);//交换当前结点与较小的孩子结点，pos指向最小的结点、当前结点
		shift_down(pos);//递归执行shift_down()，对交换后破坏的较小子结点的“局部树”进行“重建”
	}
}

//建堆，大洗牌，重建小顶堆
void build()
{
	for(int i = n / 2; i >= 1; i--)//对每个父子结点执行shift_down操作
	{
		shift_down(i);
	}
}

//取堆的根节点
int get_top()
{
	int ans = h[1];
	h[1] = h[n];//交换首尾结点
	n--;//去掉最后一个结点（最小的结点）
	shift_down(1);//回复小顶堆的性质
	return ans;//返回最小结点的地址
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &h[i]);
	}

	build();//建堆

	int len = n;
	for(int i = 1; i <= len; i++)
	{//由小到大输出数值
		printf("%d%c", get_top(), i == len ? '\n' : ' ');
	}

	return 0;
}

运行结果示图：

如有错误欢迎指正！~