堆的构建 (二)

#include
#include
#include
#include
using namespace std;
int main()
{
int arr[]={0,1,2,3,4,8,9,3,5};
vectorivec(arr,arr+9);
//greater comp;//最小堆
less comp;//最大堆
make_heap(ivec.begin(),ivec.end(),greater,comp);

//9 5 8 3 4 0 2 3 1
for(int i=0;i cout< }
cout<

ivec.push_back(7);
push_heap(ivec.begin(),ivec.end(),comp);
//9 7 8 3 5 0 2 3 1 4
for(int i=0;i cout< }
cout<

pop_heap(ivec.begin(),ivec.end(),comp);
cout< ivec.pop_back();

sort_heap(ivec.begin(),ivec.end(),comp);
//9 7 8 3 5 0 2 3 1 4
for(int i=0;i cout< }

system("pause");
return 0;
}

（2）利用priority_queue构建堆（STL源码剖析P183，其实利用了上面的接口）

STL中提供了一种priority_queue，缺省情况下利用max_heap完成。STL中的priority_queue往往不被归类为容器，而是被归类为容器迭代器。

STL中的声明priority_queue声明如下：

template,class Compare=less>

class priority_queue{

....

}

从上面的定义看出，STL的priority_queue采用vector实现，且Compare比较函数为仿函数less，我们可以传入greater，构造最小堆。

[cpp]
#include
#include
#include
using namespace std;
int main()
{
int arr[]={0,1,2,3,4,5,8,9,3,5};
priority_queue ipq(arr,arr+9);
cout<<"size="< while(!ipq.empty()){
cout< ipq.pop();
}
system("pause");
}

#include
#include
#include
using namespace std;
int main()
{
int arr[]={0,1,2,3,4,5,8,9,3,5};
priority_queue ipq(arr,arr+9);
cout<<"size="< while(!ipq.empty()){
cout< ipq.pop();
}
system("pause");
}

换一个仿函数就能构造最小堆：

[cpp]
#include
#include
#include
using namespace std;
int main()
{
int arr[]={0,1,2,3,4,5,8,9,3,5};
priority_queue,greater> ipq(arr,arr+9);
cout<<"size="< while(!ipq.empty()){
cout< ipq.pop();
}
system("pause");
return 0;
}

#include
#include
#include
using namespace std;
int main()
{
int arr[]={0,1,2,3,4,5,8,9,3,5};
priority_queue,greater> ipq(arr,arr+9);
cout<<"size="< while(!ipq.empty()){
cout< ipq.pop();
}
system("pause");
return 0;
}

（3）利用set（或者multiset）构建堆（剑指offer P169页）

[cpp]
#include
#include
#include
#include
using namespace std;

typedef greater Greater;//最大堆
typedef less Less;//最小堆
typedef multiset MaxHeap;
typedef multiset::iterator Iterator;


int main()
{
int arr[]={0,1,2,3,4,8,9,3,5};

MaxHeap heap;
for(int i=0;i<9;i++){
heap.insert(arr[i]);
}
for(Iterator it = heap.begin();it!=heap.end();++it){
cout<<*it<<" ";
}
cout<
heap.erase(heap.begin());
heap.insert(10);
for(Iterator it = heap.begin();it!=heap.end();++it){
cout<<*it<<" ";
}
system("pause");
return 0;
}

#include
#include
#include
#include
using namespace std;

typedef greater Greater;//最大堆
typedef less Less;//最小堆
typedef multiset MaxHeap;
typedef multiset::iterator Iterator;

int main()
{
int arr[]={0,1,2,3,4,8,9,3,5};

MaxHeap heap;
for(int i=0;i<9;i++){
heap.insert(arr[i]);
}
for(Iterator it = heap.begin();it!=heap.end