题目描述
给定一组数据，使用堆排序完成数据的降序排序。（建小顶堆)。
输入
数据个数n，n个整数数据
输出
初始创建的小顶堆序列
每趟交换、筛选后的数据序列，输出格式见样例
输入样例1
8 34 23 677 2 1 453 3 7
输出样例1
8 1 2 3 7 23 453 677 34 8 2 7 3 34 23 453 677 1 8 3 7 453 34 23 677 2 1 8 7 23 453 34 677 3 2 1 8 23 34 453 677 7 3 2 1 8 34 677 453 23 7 3 2 1 8 453 677 34 23 7 3 2 1 8 677 453 34 23 7 3 2 1
思路分析
首先要建立一个小顶堆，建立堆的过程是一个反复筛选的过程。
一个筛选的过程是一个自堆顶到叶子的调整过程，排序原理就是输出堆顶元素，然后把堆的最后一个元素移到堆顶，然后重新调整使之重新成为一个堆。这样一个调整的过程，在建立堆的时候需要从第n/2个元素开始反复调整。
AC代码
代码语言：javascript复制#include<iostream>
using namespace std;
class MinHeap{
int data[256],n;
public:
MinHeap(){
cin>>n;
for(int i=0;i<n;i )
cin>>data[i];
for(int i=n/2;i>=0;i--)
Adjust(i,n-1);
Show();
HeapSort();
}
void Adjust(int i,int m){
int temp=data[i];
for(int j=2*i 1;j<=m;j=j*2 1){
if(j<m&&data[j]>data[j 1])
j ;
if(data[j]>=temp)
break;
data[i]=data[j];
i=j;
}
data[i]=temp;
}
void HeapSort(){
for(int i=n-1;i>0;i--){
swap(data[0],data[i]);
Adjust(0,i-1);
Show();
}
}
void Show(){
cout<<n<<' ';
for(int i=0;i<n-1;i )
cout<<data[i]<<' ';
cout<<data[n-1]<<endl;
}
};
int main() {
MinHeap test;
}
