最小堆的C++代码实现

最小堆的C++代码实现

Description

给定一维int型数组, 请构造一棵最小堆. 总是优先向左子树调整.

Input

输入第1行有一个int型正整数m (m<100), 表示有m行输入.
每行输入的第一个数为int型正整数n (8

Output

输出m行, 每行为排好序的输出.

Sample Input

2
7 3 8 4 1 6 3 2
8 2 4 5 9 8 7 6 3

Sample Output

1 3 2 8 6 3 4 
2 3 5 4 8 7 6 9
 

题目难点分析：

1. 用数组来表示堆（完全二叉树），i为一个节点，则其左孩子为2i, 右孩子为2i+1

2.最小堆，调整顺序是自下向上，自右向左；但是每次单个调整中，比较完了调整了，还需要和子节点的子节点比较，继续调整，即单次调整中是 自上向下调整

代码：

#include 
#include  
using namespace std;
 

void heapsort(int a[],int current,int high){//current 是需要调整的节点，high为数组边界，末尾 
	
	int i=current;
	int j=i*2;
	while(j<=high){
		if(a[j+1]> m;
	while(m--){
		int n;
		cin >> n;
		int a[n+1];
		for(int i = 1; i <= n; i++)
			cin >> a[i];
		for(int j = n/2; j >= 1; j--)    //这里就是自下向上，自右向左调整顺序，j=n/2，则孩子为2n. 
			heapsort(a, j, n);
		for(int i = 1; i <= n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
        return 0;
	}