rein0 2020-04-08
草草整理一下,以后再完善一点
堆排序的复杂度是比较稳定的\(O(nlgn)\),并且具有空间原址性。
二叉堆是一个是一个数组,通过类似线段树的方式来表示父结点和子结点
其中1结点代表根,在大根堆中代表最大的数
任何子结点在循环前都可以看作一个平凡堆
大根堆中,每个结点都要比它的子结点大,维护这个性质,只需要将该结点与子结点取一个最大的交换到根,然后将可能违背性质的点递归
#include<bits/stdc++.h> using namespace std; struct heap{ int *A; int length; heap(int n){ length = n; A = new int[n+5]; for(int i=1;i<=n;++i){ cin>>A[i]; } } void Max_Heapify(int pos){ int l = pos*2; int r = pos*2+1; int largest; if(l <= length && A[l] > A[pos]){ largest = l; }else{ largest = pos; } if(r <= length && A[r] > A[largest]){ largest = r; } if(largest != pos){ swap(A[pos],A[largest]); Max_Heapify(largest); } } void build_max_heap(){ for(int i=length/2;i>=1;--i){ Max_Heapify(i); } } void heapSort(){ build_max_heap(); int n = length; for(int i=length;i>=2;--i){ swap(A[1],A[i]); length--; Max_Heapify(1); } for(int i=1;i<=n;++i){ cout<<A[i]<<" "; } } }; int main(){ int n; cin>>n; heap *test = new heap(n); test ->heapSort(); return 0; }