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

迷南。 2022-07-15 10:30 330阅读 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;

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

![20161113192504674][]

[20161113191057687]: /images/20220715/f201d2879f6d4a47b0c75daa4d5ffafb.png
[20161113192148498]: /images/20220715/37c58862ef054141a8e2fe003d7a910f.png
[20161113190927340]: /images/20220715/ccaed80bdce04eacae39c4917b350ddd.png
[20161113192246233]: /images/20220715/828a6f1789154d3f96bcd23c93c0474d.png
[20161113191747501]: /images/20220715/b22de7abd5ba4a1bb262ba7fa767e46b.png
[20161113191846877]: /images/20220715/356400bd588e418fb3b45ab2e981e294.png
[20161113191938776]: /images/20220715/411163b892f04eb2b5d28de85702c0fa.png
[20161113192504674]: /images/20220715/b651f0f3eab84412bbfa34068b800b86.png