C++中堆的应用

2023-10-21 21:32

文章标签 c++ 应用中堆

本文主要是介绍C++中堆的应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

C++中堆的应用：make_heap, pop_heap, push_heap, sort_heap, priority_queue

make_heap, pop_heap, push_heap, sort_heap都是标准算法库里的模板函数，用于将存储在vector/deque 中的元素进行堆操作，对不愿自己写数据结构堆的C++选手来说，这几个算法函数很有用，下面是这几个函数操作vector中元素的例子。详细解释可以参见： http://www.cplusplus.com/reference/algorithm/push_heap/

Push element into heap range

Given a heap range [first,last-1), this function extends the range considered a heap to [first,last) by placing the value in (last-1) into its corresponding location in it.

A range can be made into a heap by calling function make_heap. Once created, its heap properties can be preserved by using push_heap and pop_heap respectively to add and remove values from it.

Parameters

first, last

Random-Access iterators to the initial and final positions of the new heap, including the pushed element. The range used is [first,last), which contains all the elements between first andlast, including the element pointed by first but not the element pointed by last.

comp

Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specificstrict weak ordering it defines, and false otherwise.

Return value

none

Example

// range heap example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
int myints[] = {10,20,30,5,15};
vector< int> v(myints,myints+5);
vector< int>::iterator it;

make_heap (v.begin(),v.end());
cout << "initial max heap : " << v.front() << endl;

pop_heap (v.begin(),v.end()); v.pop_back();
cout << "max heap after pop : " << v.front() << endl;

v.push_back(99); push_heap (v.begin(),v.end());
cout << "max heap after push: " << v.front() << endl;

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

cout << "final sorted range :";
for ( unsigned i=0; i<v.size(); i++) cout << " " << v[i];

cout << endl;

return 0;
}

Output:

initial max heap : 30
max heap after pop : 20
max heap after push: 99
final sorted range : 5 10 15 20 99

这篇关于C++中堆的应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！