STL中的堆操作

STL裡面的堆操作一般用到的隻有4個:make_heap();、pop_heap();、push_heap();、sort_heap();

他們的頭檔案函數是#include <algorithm>

首先是make_heap();

他的函數原型是：void make_heap(first_pointer,end_pointer,compare_function);

一個參數是數組或向量的頭指針，第二個向量是尾指針。第三個參數是比較函數的名字。在預設的時候，預設是大跟堆。（下面的參數都一樣就不解釋了）

作用：把這一段的數組或向量做成一個堆的結構。範圍是(first,last)

然後是pop_heap();

它的函數原型是：void pop_heap(first_pointer,end_pointer,compare_function);

作用：pop_heap()不是真的把最大（最小）的元素從堆中彈出來。而是重新排序堆。它

把first和last交換，然後将[first,last-1)的資料再做成一個堆。

接着是push_heap()

void pushheap(first_pointer,end_pointer,compare_function);

作用：push_heap()假設由[first,last-1)是一個有效的堆，然後，再把堆中的新元素加

進來，做成一個堆。

最後是sort_heap()

void sort_heap(first_pointer,end_pointer,compare_function);

作用是sort_heap對[first,last)中的序列進行排序。它假設這個序列是有效堆。（當然

，經過排序之後就不是一個有效堆了）

下面是例程：

#include<algorithm>

#include<cstdio>

using namespace std;

bool cmp(int a,int b)

{

return a>b;

}

int main()

int i,number[20]={29,23,20,22,17,15,26,51,19,12,35,40};

make_heap(&number[0],&number[12]);

//結果是:51 35 40 23 29 20 26 22 19 12 17 15

for(i=0;i<12;i++)

printf("%d ",number[i]);

printf("\n");

make_heap(&number[0],&number[12],cmp);

//結果：12 17 15 19 23 20 26 51 22 29 35 40

//加入元素8

number[12]=8;

//加入後調整

push_heap(&number[0],&number[13],cmp);

//結果：8 17 12 19 23 15 26 51 22 35 40 20

for(i=0;i<13;i++)

//彈出元素8

pop_heap(&number[0],&number[13],cmp);

sort_heap(&number[0],&number[12],cmp);

//結果不用說都知道是有序的了！

return 0;

Compile options needed: /GX

//

// heap_functions.cpp : Illustrates how to use the

// make_heap, sort_heap, push_heap

// and pop_heap functions.

// Functions:

// make_heap : convert a sequence to a heap

// sort_heap : sort a heap

// push_heap : insert an element in a heap

// pop_heap : remove the top element from a heap

// Written by Kalindi Sanghrajka

// of Microsoft Product Support Services,

// Software Core Developer Support.

// Copyright (c) 1996 Microsoft Corporation. All rights reserved.

//////////////////////////////////////////////////////////////////////

// disable warning C4786: symbol greater than 255 character,

// okay to ignore

#pragma warning(disable: 4786)

#include <iostream>

#include <algorithm>

#include <functional>

#include <vector>

void main()

const int VECTOR_SIZE = 8 ;

// Define a template class vector of int

typedef vector<int, allocator<int> > IntVector ;

//Define an iterator for template class vector of strings

typedef IntVector::iterator IntVectorIt ;

IntVector Numbers(VECTOR_SIZE) ;

IntVectorIt it ;

// Initialize vector Numbers

Numbers[0] = 4 ;

Numbers[1] = 10;

Numbers[2] = 70 ;

Numbers[3] = 10 ;

Numbers[4] = 30 ;

Numbers[5] = 69 ;

Numbers[6] = 96 ;

Numbers[7] = 100;

// print content of Numbers

cout << "Numbers { " ;

for(it = Numbers.begin(); it != Numbers.end(); it++)

cout << *it << " " ;

cout << " }\n" << endl ;

// convert Numbers into a heap

make_heap(Numbers.begin(), Numbers.end()) ;

cout << "After calling make_heap\n" << endl ;

// sort the heapified sequence Numbers

sort_heap(Numbers.begin(), Numbers.end()) ;

cout << "After calling sort_heap\n" << endl ;

//insert an element in the heap

Numbers.push_back(7) ;

push_heap(Numbers.begin(), Numbers.end()) ;

// you need to call make_heap to re-assert the

// heap property

cout << "After calling push_heap and make_heap\n" << endl ;

// remove the root element from the heap Numbers

pop_heap(Numbers.begin(), Numbers.end()) ;

cout << "After calling pop_heap\n" << endl ;

程式輸出為：

Numbers { 4 10 70 10 30 69 96 100 }

之後調用 make_heap

Numbers { 100 30 96 10 4 69 70 10 }

之後調用 sort_heap

Numbers { 4 10 10 30 69 70 96 100 }

之後調用 push_heap 和 make_heap

Numbers { 100 69 96 30 4 70 10 10 7 }

之後調用 pop_heap

Numbers { 96 69 70 30 4 7 10 10 100 }

本文轉自郝峰波部落格園部落格，原文連結：http://www.cnblogs.com/fengbohello/archive/2013/01/25/2876655.html，如需轉載請自行聯系原作者