最小堆的构建_最小堆建立过程

堆是什么？

是一种特殊的完全二叉树，such as:

但是这个二叉树有一个特点，就是所有的父节点都比子节点要小，符合这样特点的完全二叉树我们称为最小堆。反之，如果所有父节点都要比子节点要大，这样的完全二叉树称为最大堆。

如何构建堆

如下图所示，我们先把一串数字存储在数组里面，因违反二叉树存在一个节点下标i的左子树下标是2i,右子树的下标是2i+1；所以我们存在二维数组里面也可以很好的查找到一个节点的左右孩子。

存入以后，我们可以从最后一个非根节点的点开始，一次判断以这个节点为根的子树是否符合最小堆的特性。如果所有的子树都符合最小堆的特性，那么整棵树就是最小堆了。
所以就是先判断7这个节点是否满足最小堆，然后判断6这个节点，一直判断到结点1.
如果7不满足最小堆，则将7向下调整，然后将其左右子树中最小的那个子树往上调至7的位置 。

最后的结果：

代码如下：

#include<bits/stdc++.h>
using namespace std;
int h[100];
int n; 
void swap(int i,int t){
	int temp;
	temp=h[i];
	h[i]=h[t];
	h[t]=temp;
}
void shiftdown(int i){
	int flag=0; //用于标记是否还需要向下调 
	int t=i;//存数字小的下标 
	while(i*2<=n&&flag==0){  //至少存在左子树 
		if(h[i*2]<h[i])    t=i*2;
		if(i*2+1<=n){  //存在右子树 
			if(h[i*2+1]<h[t])   t=i*2+1;
		}
		if(t!=i){   //发现最小的节点编号不是自己，即子节点中存在比父节点小的数 
			swap(i,t);
			i=t;   //更新i点，以便于再次比较下面的点 
		}
		else
		flag=1;   //该点比一下的点都小，不需要向下找了 
	}
}
int main(){
	fill(h,h+100,0);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){   //读入所有的数 
		scanf("%d",&h[i]);
	}
	for(int i=n/2;i>0;i--){   //构建最小堆 
		shiftdown(i);
	}
	for(int i=1;i<=n;i++){   //显示最小堆 
		printf("%d    ",h[i]);
	} 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40