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

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

函数说明：

std::make_heap将[start,end)范围进行堆排序，默认使用less,即最大元素放在第一个。

std::pop_heap将front（即第一个最大元素）移动到end的前部，同时将剩下的元素重新构造成(堆排序)一个新的heap。

std::push_heap对刚插入的（尾部）元素做堆排序。

std::sort_heap将一个堆做排序,最终成为一个有序的系列，可以看到sort_heap时，必须先是一个堆（两个特性：1、最大元素在第一个 2、添加或者删除元素以对数时间），因此必须先做一次make_heap.

make_heap,sort_heap都是标准算法库里的模板函数，用于将存储在vector/deque 中的元素进行堆操作，对不愿自己写数据结构堆的C++选手来说，这几个算法函数很有用，下面是这几个函数操作vector中元素的例子。

> #include< iostream>

#include< algorithm>

#include< vector >

using namespace std;

void print_ivec(vector< int >::iterator begin,vector< int >::iterator end)

{

for(;begin != end; ++begin)

cout << *begin << 't';

cout << endl;

}

int main(int argc,char* argv[])

{

int a[] = {1,12,15,20,30};

vector< int > ivec(a,a + sizeof(a) / sizeof(a[0]));

print_ivec(ivec.begin(),ivec.end());

make_heap(ivec.begin(),ivec.end(),greater< int >());

print_ivec(ivec.begin(),ivec.end());

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

ivec.pop_back();

print_ivec(ivec.begin(),ivec.end());

ivec.push_back(99);

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

print_ivec(ivec.begin(),ivec.end());

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

return 0;

}

以及

# include

# include

# include

# include

using namespace std;

void printVec(vector nums)

{

for (int i = 0; i < nums.size(); ++i)

cout << nums[i] << " ";

cout << endl;

}

int main(void)

{

int nums_temp[] = {8,3,4,8,9,2,4};

vector nums(nums_temp,nums_temp + 8);

cout << "sorce nums: ";

printVec(nums);

cout << "(默认)make_heap: ";

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

printVec(nums);

cout << "(less)make_heap: ";

make_heap(nums.begin(),nums.end(),less ());

printVec(nums);

cout << "(greater)make_heap: ";

make_heap(nums.begin(),greater ());

printVec(nums);

cout << "此时，nums为小顶堆" << endl;;

cout << "push_back(3)" << endl;

nums.push_back(3);

cout << "忽略第三个参数，即为默认)push_heap: ";

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

printVec(nums);

cout << "第三个参数为greater: ";

push_heap(nums.begin(),greater());

printVec(nums);

cout << "(做替换)pop_heap: ";

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

printVec(nums);

cout << "pop_back(): ";

nums.pop_back();

printVec(nums);

}

结果为：

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!