STLalgorithm算法pop_heap,push_heap(45)

pop_heap原型：

std::pop_heap

default (1)

template
void pop_heap (RandomAccessIterator first, RandomAccessIterator last);

custom (2)

template <class RandomAccessIterator, class Compare>
void pop_heap (RandomAccessIterator first, RandomAccessIterator last,
Compare comp);

该函数是将堆中第一个元素（即最大值）移动到last-1的位置。然后将剩下的元素重新构造成一个heap(包括原来的last-1位置的值，该值被移动到了first).但是实际上并不会删除该堆的最大值。

调用该方法后，范围内的元素依旧保持堆的属性。

一个简单的例子：

#include
#include
#include
using namespace std;
int main(){
vector vi{1,7,5,6,8,9,3};
cout<<”at first vi=”;
for(int i:vi)
cout<<i<<” “;
cout<<endl;
make_heap(vi.begin(),vi.end());
cout<<”after make_heap(vi.begin(),vi.end())\nvi=”;
for(int i:vi)
cout<<i<<” “;
cout<<endl;

pop_heap(vi.begin(),vi.end());
cout<<”after pop_heap(vi.begin(),vi.end())”<<endl;
cout<<”vi=”;
for(int i:vi)
cout<<i<<” “;
cout<<endl;
}

运行截图：

可以看到，9依旧保留在原范围的last-1位置。如果需要，需要手动删除。

除此之外，前面的元素依旧以堆的形式存放。

push_heap原型：

std::push_heap

default (1)

template
void push_heap (RandomAccessIterator first, RandomAccessIterator last);

custom (2)

template <class RandomAccessIterator, class Compare>
void push_heap (RandomAccessIterator first, RandomAccessIterator last,
Compare comp);

该函数是在插入一个元素到一个堆中之后调用该函数使该该元素插入到堆中。

这句话有点拗口。

看一个例子就很容易明白了。

// range heap example
#include // std::cout
#include // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap
#include // std::vector

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

std::make_heap (v.begin(),v.end());
std::cout << “initial max heap : “ << v.front() << ‘\n’;

std::pop_heap (v.begin(),v.end()); v.pop_back();
std::cout << “max heap after pop : “ << v.front() << ‘\n’;

v.push_back(99); std::push_heap (v.begin(),v.end());
std::cout << “max heap after push: “ << v.front() << ‘\n’;

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

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

std::cout << ‘\n’;

return 0;
}

运行截图：

仔细看这一句：

v.push_back(99); std::push_heap (v.begin(),v.end());

是先将元素加入到原范围的end()位置，然后再调用push_heap函数！

也就是说，先将要插入的元素插入到序列的最后，然后再插入到堆中！

——————————————————————————————————————————————————————————————————

//写的错误或者不好的地方请多多指导，可以在下面留言或者点击左上方邮件地址给我发邮件，指出我的错误以及不足，以便我修改，更好的分享给大家，谢谢。

转载请注明出处：http://blog.csdn.net/qq844352155

author:天下无双

Email:coderguang@gmail.com

2014-9-22

于GDUT

——————————————————————————————————————————————————————————————————

原文链接

赏

感谢支持

支付宝

微信