【STL】Heap算法——push_heap、pop_heap、sort_heap、make

【STL】Heap算法——push_heap、pop_heap、sort_heap、make_heap

迷南。 2022-07-15 10:30 302阅读 0赞

参考文章：《STL源码剖析》侯捷译;

C++STL算法提供make_heap, push_heap和pop_heap等算法，它们作用于随机存取迭代器。它们将迭代器当做数组的引用，并做出array-to-heap的转换。STL中默认这个算法为最大堆（max_heap）。

make_heap

make_heap 的功能是将一段现有的数据转化成一个heap（堆）。默认状态下，它会生成一个最大堆结构，我们也可以自己定义为最大堆或者最小堆。我们先看它的定义：

定义1：（默认状态）

template <class RandomAccessIterator>//模板参数
 void make_heap ( RandomAccessIterator first, RandomAccessIterator last );
我们可以看到，定义1有两个参数，参数为模板类型的迭代器。作用为当我们传一个左闭右开区间\[first,last)时，它会自动把这个区间的数据转化成一个最大堆。

定义2：（传compare）

template <class RandomAccessIterator, class Compare>
void make_heap ( RandomAccessIterator first, RandomAccessIterator last,Compare comp );
 定义2里面多了一个模板参数，用于我们给它传一个比较类型。用这个比较类型决定实现最大堆还是最小堆。以下的push\_heap，pop\_heap，sort\_heap都有两种定义，区别于make\_heap相同。

push_heap

定义1：

template <class RandomAccessIterator>
void push_heap ( RandomAccessIterator first, RandomAccessIterator last );
 定义2：
template <class RandomAccessIterator, class Compare>
void push_heap ( RandomAccessIterator first, RandomAccessIterator last,Compare comp );

push_heap的功能是往‘堆’中插入一个数据。但是，它的默认前提是这个区间[first,last)已经满足堆结构，并且要插入的数据已经插入到堆的最后即区间的最后一个位置。为什么呢？因为STL库提供的push_heap算法并没有插入元素，仅仅是完成插入元素后的调整工作，将插入元素后的区间重新恢复堆结构。无论插入几个数据，调用push_heap前都必须将数据先插入到区间中。

图解：

20161113191057687

下面看一个它的例子：

vector<int> a = { 3, 6, 2, 1, 7, 4, 9, 5 };
make_heap(a.begin(), a.end());//前提①，建堆，使区间满足堆结构
a.push_back(20);//前提②，要插入数据已经插入
push_heap(a.begin(), a.end());//push_heap做出调整
for (int i = 0; i < a.size(); ++i)
{
 cout << a[i] << " ";
}
cout << endl;

结果：

20161113192148498

pop_heap

定义1：

template <class RandomAccessIterator>
void pop_heap ( RandomAccessIterator first, RandomAccessIterator last );
   定义2：
template <class RandomAccessIterator, class Compare>
void pop_heap ( RandomAccessIterator first, RandomAccessIterator last,Compare comp );
  pop\_head实现的同样是调整工作，不过它是删除前的调整。当调用pop\_head后，我们再将区间的最后一个元素pop掉。为什么要pop最后一个元素呢？因为pop\_head完成的工作就是将堆顶的元素与最后一个元素交换，再执行调整程序，将除了区间最后一个元素（此时已经交换）的所有元素重新恢复堆结构。 最后记住。每pop一个元素，下一次操作时last要减1。(区间要缩小1)

图解：

20161113190927340

例子：

vector<int> a = { 3, 6, 2, 1, 7, 4, 9, 5 };
make_heap(a.begin(),a.end());//前提①，建堆，使区间满足堆结构
a.push_back(20);//前提②，要插入数据已经插入
push_heap(a.begin(), a.end());//push_heap做出调整
pop_heap(a.begin(), a.end());
a.pop_back();
for (int i = 0; i < a.size(); ++i)
{
    cout << a[i] << " ";
}
cout << endl;

结果：（与上图结果做比较）

20161113192246233

sort_heap

定义1：

template <class RandomAccessIterator>
    void sort_heap ( RandomAccessIterator first, RandomAccessIterator last );

定义2：

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

当我们学会了使用pop_heap后，你就会很容易理解sort_heap的实现原理了。从上我们可以知道，我们每执行一次pop_heap,就会有一个最大的元素到区间的最后，sort_heap就是多次调用pop _heap，每次将堆顶元素（最大元素）与最后元素发生交换。last—（区间缩小1），重复以上工作，直到区间只剩下1个元素。最后就完成了排序。

图解：

20161113191747501

20161113191846877

20161113191938776

例子：

vector<int> a = { 3, 6, 2, 1, 7, 4, 9, 5 };
    make_heap(a.begin(),a.end());//前提①，建堆，使区间满足堆结构
    a.push_back(20);//前提②，要插入数据已经插入
    push_heap(a.begin(), a.end());//push_heap做出调整
    pop_heap(a.begin(), a.end());
    a.pop_back();
    sort_heap(a.begin(), a.end());
    for (int i = 0; i < a.size(); ++i)
    {
        cout << a[i] << " ";
    }
    cout << endl;
  结果：（与上图结果做比较）