建最小堆min_heap_sort

2019-11-14 12:38:00

字体：大中小

来源：转载

供稿：网友

建最小堆与最大堆方法相同只要改动max_heapify()函数里的判断条件即可.

#include<iostream>

using namespace std;int Parent(int i){return i/2;}int Left(int i){return 2*i;}int Right(int i){return 2*i+1;}void exchange(int *a,int *b){int t=*a;*a=*b;*b=t;}void min_heapify(int *a,int i,int heap_size){int l=Left(i);int r=Right(i);int smallest;if(l<=heap_size&&a[l]<a[i])//改动smallest=l;elsesmallest=i;if(r<=heap_size&&a[r]<a[smallest]) ///改动smallest=r;if(smallest!=i){ exchange(&a[smallest],&a[i]); min_heapify(a,smallest,heap_size);}}void Build_min_heap(int *a,int length){int heap_size=length;for(int i=length/2;i>0;--i) min_heapify(a,i,heap_size);}void output(int *a,int size){for(int i=0;i<size;++i)cout<<a[i]<<" ";cout<<endl;}void Heap_Sort(int *a,int size){Build_min_heap(a,size);for(int i=size;i>1;--i) { exchange(&a[i],&a[1]); --size; min_heapify(a,1,size); }}int main(){int a[11]={2222,4,1,3,2,16,9,10,14,8,7};Build_min_heap(a,10);output(a+1,10);Heap_Sort(a,10);output(a+1,10);return 0;}

上一篇：P1042 乒乓球

下一篇：异步 FIFO 最小深度计算方法及原理分析（转补）