堆排序，优先队列实现

//堆排序#include <iostream>#include <vector>using namespace std;//vector<int> heap;//父亲节点int parent(int i){if( i>=0) return (i+1)/2-1;else return 0;}//左孩子int left(int i){if(i>=0) return (i+1)*2-1;else return 0;}//右孩子int right(int i){if(i>=0) return (i+1)*2;else return 0;}void maxHeapify(vector<int> & heap1,int i) { int large=0; bool flag =true; int l=left(i),r=right(i); int length=heap1.size(); if(!(i <0)&&i < length){if(l < length)//有可能有left但没right，此时只要成立一个条件就好，因为不存在没有left但有right！不考虑了{if (heap1[i] < heap1[l]) large =l;else large = i;if(r <length){if(heap1[large] <heap1[r]) large =r;//左右根取其中最大}}else flag =false; } if(flag&&large !=i)//有一个孩子也能做下一步 {int temp = heap1[large];heap1[large] = heap1[i];heap1[i] = temp;maxHeapify(heap1,large); } }//建堆 void buildMaxheap(vector<int> & heap1) { int length =heap1.size(); for(int i=length/2-1;i >= 0;i–)maxHeapify(heap1,i); } //堆排序 vector<int> sortHeap(vector<int> heap1) { vector<int> v; int temp; int length =heap1.size(); for(int i = length-1;i >= 0;i–) {v.push_back(heap1[0]);temp =heap1[0];heap1[0] = heap1[i];heap1[i] = temp;heap1.pop_back();maxHeapify(heap1,0); } return v; }void increaseHeapKey(vector<int> &heap1,int i,int key) {//优先队列堆某handler增加优先级应用场景 int length =heap1.size(); i=i-1; if(i<length&&i >= 0&&key > heap1[i]) {heap1[i] = key;while(i){if(heap1[i] > heap1[parent(i)]){int temp = heap1[i];heap1[i] = heap1[parent(i)];heap1[parent(i)] = temp;i = parent(i);}else break;} } }void insertHeap(vector<int> &heap1,int key) {//优先队列加入某handler int length =heap1.size(); heap1.push_back(key);//没判断capacity int i =length-1; while(i) {if(heap1[i] > heap1[parent(i)]){int temp = heap1[i];heap1[i] = heap1[parent(i)];heap1[parent(i)] = temp;i = parent(i);}else break; } }void show(vector<int> & heap1) { vector<int>::const_iterator pos; for(pos =heap1.begin();pos !=heap1.end();++pos)cout<<*pos<<" "; cout<<endl; }void main() {int h[14]={0,1,3,4,5,7,8,9,10,12,13,16,17,27}; vector<int> heap(h,h+14); cout<<"******************初始堆******************"<<endl; show(heap); buildMaxheap(heap); cout<<"******************最大堆******************"<<endl; show(heap); cout<<"**************引用传参堆排序**************"<<endl; show(sortHeap(heap)); cout<<"****************最大堆不变****************"<<endl; show(heap); increaseHeapKey(heap,11,55); cout<<"******优先队列堆某handler增加优先级*******(此处增加11节点的为55)"<<endl; show(heap); insertHeap(heap,106); cout<<"**********优先队列加入某handler***********（增加一个节点106）"<<endl; show(heap); int m; cin>>m; }

小弟刚实现忘指正

，使用双手的是劳工，使用双手和头脑的舵手，

相关文章：

你感兴趣的文章：

标签云：