STL_算法_Heap算法（堆排）（精）
/*****************************************
STL-算法--Heap算法
堆排序算法 (heapsort)
make_heap() //把容器内的数据做堆排序
push_heap() //向堆内放入元素
pop_heap() //删除堆顶元素
sort_heap() //把堆排还原成普通排序
*****************************************/
/**----------------------------------------------------------------------------------
make_heap(b,e) 9
make_heap(b,e,cp) / \
push_heap(b,e) 8 6
push_heap(b,e,cp) / \ / \
pop_heap(b,e) 7 7 5 5
pop_heap(b,e,cp) / \ / \ / \ /
sort_heap(b,e) 3 6 4 1 2 3 4
sort_heap(b,e,cp)
----------------------------------------------------------------------------------**/
/**------http://blog.csdn.net/u010579068------**/ #include<iostream> #include<cstdio> #include<string> #include<vector> #include<list> #include<deque> #include<algorithm> using namespace std; /***************************************** STL-算法--Heap算法 堆排序算法 (heapsort) make_heap() //把容器内的数据做堆排序 push_heap() //向堆内放入元素 pop_heap() //删除堆顶元素 sort_heap() //把堆排还原成普通排序 *****************************************/ /**---------------------------------------------------------------------------------- make_heap(b,e) 9 make_heap(b,e,cp) / \ push_heap(b,e) 8 6 push_heap(b,e,cp) / \ / \ pop_heap(b,e) 7 7 5 5 pop_heap(b,e,cp) / \ / \ / \ / sort_heap(b,e) 3 6 4 1 2 3 4 sort_heap(b,e,cp) ----------------------------------------------------------------------------------**/ /************************************************************************************* std::make_heap 所有排序容器适用 algorithm -------------------------------------------------------------------------------------- template <class RandomAccessIterator> void make_heap ( RandomAccessIterator first, RandomAccessIterator last ); template <class RandomAccessIterator, class Compare> void make_heap ( RandomAccessIterator first, RandomAccessIterator last, Compare comp ); //eg： *************************************************************************************/ /************************************************************************************* std::push_heap 所有排序容器适用 algorithm -------------------------------------------------------------------------------------- template <class RandomAccessIterator> void push_heap ( RandomAccessIterator first, RandomAccessIterator last ); template <class RandomAccessIterator, class Compare> void push_heap ( RandomAccessIterator first, RandomAccessIterator last, Compare comp ); //eg： *************************************************************************************/ /************************************************************************************* std::pop_heap 所有排序容器适用 algorithm -------------------------------------------------------------------------------------- template <class RandomAccessIterator> void pop_heap ( RandomAccessIterator first, RandomAccessIterator last ); template <class RandomAccessIterator, class Compare> void pop_heap ( RandomAccessIterator first, RandomAccessIterator last, Compare comp ); //eg： *************************************************************************************/ /************************************************************************************* std::sort_heap 所有排序容器适用 algorithm -------------------------------------------------------------------------------------- template <class RandomAccessIterator> void sort_heap ( RandomAccessIterator first, RandomAccessIterator last ); template <class RandomAccessIterator, class Compare> void sort_heap ( RandomAccessIterator first, RandomAccessIterator last, Compare comp ); //eg： *************************************************************************************/ template<typename T> void Print(T& V) { typename T::iterator iter=V.begin(); while(iter != V.end()) { cout<<*iter++<<" "; } cout<<endl; } int main() { vector<int> ivec; for(int i=3;i<=7;++i) ivec.push_back(i); for(int i=5;i<=9;++i) ivec.push_back(i); for(int i=1;i<=4;++i) ivec.push_back(i); cout<<"原数据："; Print(ivec); make_heap(ivec.begin(),ivec.end());//做最大堆排序，其实还在vector容器内 cout<<"堆排后："; Print(ivec); pop_heap(ivec.begin(),ivec.end());//删除最大堆，其实是把数据放到最后了！ cout<<"删除后："; Print(ivec); ivec.pop_back(); pop_heap(ivec.begin(),ivec.end());//删除最大堆，其实是把数据放到最后了！ cout<<"删除后："; Print(ivec); ivec.pop_back(); ivec.push_back(15); cout<<"添加数据后："; Print(ivec); push_heap(ivec.begin(),ivec.end());//放入最大堆，其实是把新加入的数据，按照堆排加入堆内 cout<<"把最后一个数加入堆里:\n"; Print(ivec); sort_heap(ivec.begin(),ivec.end());//把堆排顺序，还原成一般的排序算法 cout<<"还原堆排顺序：\n"; Print(ivec); return 0; }
/***************************************** //Output: 原数据：3 4 5 6 7 5 6 7 8 9 1 2 3 4 堆排后：9 8 6 7 7 5 5 3 6 4 1 2 3 4 删除后：8 7 6 7 4 5 5 3 6 4 1 2 3 9 删除后：7 7 6 6 4 5 5 3 3 4 1 2 8 添加数据后：7 7 6 6 4 5 5 3 3 4 1 2 15 把最后一个数加入堆里: 15 7 7 6 4 6 5 3 3 4 1 2 5 还原堆排顺序： 1 2 3 3 4 4 5 5 6 6 7 7 15 *****************************************/