首页 > 代码库 > 最大堆
最大堆
swim() 表示上浮:作者将其比喻为黑帮新人(插入的新元素),能力高(值大的)的被提升,将能力不够的前辈踩在脚下,直到遇到一个更强的领导。sink ()表示下沉:比喻为黑帮领导,能力不行的或退休的(删除)就被下属取代。每次帮派有新人加入,或有领到退休,帮内都必须重新论资排辈。这个比喻还是挺有意思的。
#include <iostream> using namespace std; class MaxHeap { private: int *a; int N; public: MaxHeap(){ N=0; } MaxHeap(int n){ a=new int[n]; N=0; } ~MaxHeap(){ delete a; } int left(int i) { return 2*i; } int right(int i) { return 2*i+1; } int parent(int i) { return i/2; } bool isEmpty() { return N==0; } bool size() { return N; } void insert(int val){ // 这样a[0]是没有存数据的 //cout<<val<<endl; a[++N]=val; // 每插入一个数,都调用swim,保持最大堆的性质 swim(N); } void swap(int i,int j){ int temp=a[i]; a[i]=a[j]; a[j]=temp; } int delMax(){ int maxVal=a[1]; a[1]=a[N]; sink(1); N--; return maxVal; } void swim(int k){ while(k>1){ if(a[parent(k)]<a[k]){ swap(parent(k),k); k=parent(k); } else break; } } void sink(int k){ // 将a[k]与子节点中较大的交换 while(left(k)<=N){ int j=left(k); // 找到子节点中较大的那一个 if(right(k)<=N && a[left(k)]<a[right(k)]) j=right(k); if(a[k]>a[j]) break; swap(k,j); k=j; } } void show(){ for(int i=1;i<=N;i++){ cout<<a[i]<<" "; } cout<<endl; } }; int main(){ int a[10]= {3,6,2,7,9,0,8,1,4,5}; MaxHeap h(100); for(int i=0;i<10;i++){ h.insert(a[i]); } h.show(); for(int i=0;i<10;i++){ cout<<h.delMax()<<" "; } cout<<endl; return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。