STL中的heap操作 stl heap

C ++STL 中与heap 有关的操作有 如下几个 :

make_heap(),

pop_heap(),

push_heap(),

sort_heap(),

is_heap();

is_heap():

注:visual studio的STL实现中没有该函数。

原型如下 :

1.boolis_heap(iteratorstart,iterator end);

->判断迭代器[start,end]区间类的元素是否构成一个堆.是返回true ,否则返回 false.

2.bool is_heap(iteratorstart,iterator end,StrictWeakOrdering cmp);

->判断迭代器[start,end] 区间类的元素在cmp条件下是否构成一个堆.是返回true,否则返回false.

make_heap() :

原型如下 :

1.voidmake_heap(random_access_iterator start,random_access_iterator end );

2. void make_heap(random_access_iterator start,random_access_iterator end,StrictWeakOrdering cmp );

->以 迭代器[start , end] 区间内的元素生成一个堆. 默认使用 元素类型 的< 操作符 进行判断堆的类型,因此生成的是大顶堆.

->当使用了 版本2时, 系统使用 用户定义的 cmp 函数来构建一个堆

->值得注意的是,make_heap 改变了 迭代器所指向的 容器 的值.

pop_heap():

原型如下 :

1. voidpop_heap(random_access_iterator start,random_access_iterator end );

2. voidpop_heap(random_access_iterator start,random_access_iterator end,StrictWeakOrdering cmp );

->pop_heap()并不是真的把最大(最小)的元素从堆中弹出来. 而是重新排序堆.它把首元素和末元素交换,然后将[first,last-1)的数据再做成一个堆。

此时, 原来的首元素 位于迭代器 end-1的位置,它已不再属于堆的一员!

->如果使用了 版本2, 在交换了首元素和末元素后,使用 cmp 规则 重新构建一个堆.

push_heap():

原型如下 :

1. voidpush_heap(random_access_iterator start,random_access_iterator end );

2.void push_heap(random_access_iterator start,random_access_iterator end,StrictWeakOrdering cmp );

->算法假设迭代器区间[start,end-1)内的元素已经是一个有效堆, 然后把 end-1 迭代器所指元素加入堆.

-> 如果使用了 cmp 参数,将使用 cmp 规则构建堆.

sort_heap() :

原型如下 :

1.voidsort_heap (random_access_iteratorstart,random_access_iterator end);

2.voidsort_heap (random_access_iteratorstart,random_access_iterator end,StrictWeakOrdering cmp);

-> 堆结构被完全破坏, 相当于对元素进行排序,效果和排序算法类似.

->如果使用了 cmp 参数, 将使用 cmp规则排序堆.

以下为MSDN中的详细备注:

Remarks

A heap is a sequence of elements organized like a binary tree.Each heap element corresponds to a tree node. The first value inthe sequence [First..Last) is the root and is thelargest value in the heap. Every element in the heap satisfies thefollowing: Every element is less than or equal to its parent. Thelargest element is stored in the root, and all children holdprogressively smaller values. The make_heap function converts the range[First..Last) into a heap. The sort_heap function sorts a sequence that wascreated using the make_heap function. The push_heap function inserts a new value into theheap. The pop_heap function swaps the first and lastelements in the heap specified by [First, Last), andthen reduces the length of the sequence by one before restoring theheap property. The nonpredicate versions of the heap functions useoperator< for comparisons.

示例代码(摘自MSDN http://msdn.microsoft.com/en-us/library/6y3edk6s(VS.71).aspx):

// heapfunc.cpp// compile with: /EHsc// // 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// disable warning C4786: symbol greater than 255 characters,// okay to ignore#pragma warning(disable: 4786)#include <iostream>#include <algorithm>#include <functional>#include <vector>using namespace std;int main(){const int VECTOR_SIZE = 8 ;// Define a template class vector of inttypedef vector<int > IntVector ;//Define an iterator for template class vector of stringstypedef IntVector::iterator IntVectorIt ;IntVector Numbers(VECTOR_SIZE) ;IntVectorIt it ;// Initialize vector NumbersNumbers[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 Numberscout << "Numbers { " ;for(it = Numbers.begin(); it != Numbers.end(); it++)cout << *it << " " ;cout << " }n" << endl ;// convert Numbers into a heapmake_heap(Numbers.begin(), Numbers.end()) ;cout << "After calling make_heapn" << endl ;// print content of Numberscout << "Numbers { " ;for(it = Numbers.begin(); it != Numbers.end(); it++)cout << *it << " " ;cout << " }n" << endl ;
//注意:该部分排序后将破坏堆的结构! // sort the heapified sequence Numberssort_heap(Numbers.begin(), Numbers.end()) ;cout << "After calling sort_heapn" << endl ;// print content of Numberscout << "Numbers { " ;for(it = Numbers.begin(); it != Numbers.end(); it++)cout << *it << " " ;cout << " }n" << endl ;
    //若此前调用了sort_heap,为了保持堆的性质,在调用push_heap之前必须调用该行,否则程序将崩溃。此处原文未调用,故原文测试程序有invalid heap错误。
 // you need to call make_heap to re-assert the// heap propertymake_heap(Numbers.begin(), Numbers.end()) ;//insert an element in the heapNumbers.push_back(7) ;
push_heap(Numbers.begin(), Numbers.end()) ;
// you need to call make_heap to re-assert the// heap propertymake_heap(Numbers.begin(), Numbers.end()) ;cout << "After calling push_heap and make_heapn" << endl ;// print content of Numberscout << "Numbers { " ;for(it = Numbers.begin(); it != Numbers.end(); it++)cout << *it << " " ;cout << " }n" << endl ;// remove the root element from the heap Numberspop_heap(Numbers.begin(), Numbers.end()) ;cout << "After calling pop_heapn" << endl ;// print content of Numberscout << "Numbers { " ;for(it = Numbers.begin(); it != Numbers.end(); it++)cout << *it << " " ;cout << " }n" << endl ;}
若利用STL中的堆函数来实现堆排序,则代码十分简洁。以下是代码:
cout << "堆排序example:n";
STL中的heap操作 stl heap
cout << "Numbers { " ;
for(it = Numbers.begin(); it != Numbers.end(); it++)
cout << *it << " " ;
cout << " }n" << endl ;
make_heap(Numbers.begin(), Numbers.end());
for(it = Numbers.end(); it!=Numbers.begin(); it--)
pop_heap(Numbers.begin(), it);
cout << "after 堆排序:n";
cout << "Numbers { " ;
for(it = Numbers.begin(); it != Numbers.end(); it++)
cout << *it << " " ;
cout << " }n" << endl ;
事实上,sort_heap就是堆排序的一种实现。

  

爱华网本文地址 » http://www.aihuau.com/a/25101017/352457.html

更多阅读

汽车大灯修复翻新的具体操作步骤 大灯翻新设备价格

汽车大灯修复翻新的具体操作步骤——简介据相关部门统计,中国机动车保有量已超过1.8亿辆,持续增长周期至少还有20年。道路越修越宽,城市汽车保有量也越来越大,围绕汽车销售,汽车后服务方面的工作强度也显然加大。由于汽车前大灯、尾灯在

线程中的悲观锁和乐观锁 java中乐观锁和悲观锁

线程中的锁可以分为乐观锁和悲观锁,这两个都是实现锁机制的两种办法。悲观锁:根据字面意思,悲观,就是不是太好的。当一个线程访问这个数据的时候,悲观锁会把这个数据给锁住,不被其他线程所访问,直到这个线程完成了对数据的提交后,其他线程

如何消除音乐中的人声制作伴奏音乐 精 消除人声制作伴奏

如何消除音乐中的人声(制作伴奏音乐) 精——简介?在各种晚会中都会用到没有人声的音乐,但是有时候我们很难找到某个音乐的伴奏音乐,这样我们就只能自己来制作伴奏带了,利用goldwave这个软件就可以很容易的实现消除人声的作用,不过音乐的品

matlab中的最大值和最小值_待_雪 函数最大值和最小值

matlab中的的最大值和最小值MATLAB提供的求数据序列的最大值和最小值的函数分别为max和min,两个函数的调用格式和操作过程类似。1.求向量的最大值和最小值求一个向量X的最大值的函数有两种调用格式,分别是:(1) y=max(X):返回向量X的最

声明:《STL中的heap操作 stl heap》为网友学荟放棄分享!如侵犯到您的合法权益请联系我们删除