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 *****************************************/
本文由用戶 iddi5896 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！