STL——Heap算法

港控/mmm° 2022-06-17 06:45 180阅读 0赞

**STL——heap算法**

1、就排序而言，heap是一种特别的元素组织方式，应用于heap排序法（heapsort）。Heap可被视为一个以序列式集合实现而成的二叉树，具有两大性质：

（1）第一个元素总是最大。

（2）总是能够在对数时间内增加或移除一个元素。

2、STL中提供了4个算法：默认的排序准则是 operator<，也可以传入一个binary predicate 作为排序准则。

（1）make\_heap()：将某个区间内的元素转化为heap；

void make_heap(RandomAccessIterator beg, RandomAccessIterator end)
    void make_heap(RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)

*  两种形式都将\[beg，end)区间内的元素转化为heap。
 *  op是个可有可无的（可选的）binary predicate，被视为排序准则，op(elem1,elem2)
 *  只有在多于一个元素的情况下，才有必要使用这些函数处理heap，如果只有单一元素，那么它自动形成一个heap。
 *  复杂度：线性，至多执行3\*numElems次比较。

（2）push\_heap()：对heap增加一个元素；

void push_heap(RandomAccessIterator beg, RandomAccessIterator end)
    void push_heap(RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)

*  两种形式都将end之前的最后一个元素加入原本就是heap的\[beg,end-1)区间内，是整个\[beg,end)区间成为一个heap。
 *  op是个可有可无的（可选的）binary predicate，被视为排序准则，op(elem1,elem2)。
 *  调用者必须保证，在进入函数时，\[beg,end-1)区间内的元素原本便已形成一个heap，而新元素紧跟其后。
 *  复杂度：对数，至多执行log(numElems)次比较。

（3）pop\_heap()：对heap取出下一个元素；

void pop_heap(RandomAccessIterator beg, RandomAccessIterator end)
    void pop_heap(RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)

*  以上两种形式都将heap\[beg,end)内的最高元素（也就是第一个元素）移到最后位置，并将剩余区间\[beg,end-1)内的元素组成一个新的heap。
 *  op是个可有可无的（可选的）binary predicate，被视为排序准则，op(elem1,elem2)。
 *  调用者必须保证，在进入函数时，\[beg,end)区间内的元素原本便已形成一个heap。
 *  复杂度：对数，至多执行2\*log(numElems)次比较。

（4）sort\_heap()：将heap转化为一个已排序群集（此后它就不再是heap了）。

void sort_heap(RandomAccessIterator beg, RandomAccessIterator end)
    void sort_heap(RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)

*  以上两种形式都可以将heap\[beg,end)转换为一个已排序序列。
 *  op是个可有可无的（可选的）binary predicate，被视为排序准则，op(elem1,elem2)。
 *  注意，此算法一旦结束，该区间就不再是个heap了。
 *  调用者必须保证，在进入函数时，\[beg,end)区间内的元素原本便已形成一个heap。
 *  复杂度：nlogn，最多执行numElems\*log(numElems)次比较。

**Heap算法使用示例：**

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
           vector<int> vec{ 1,2,3,4,7,8,5,6,9,0 };
           for (auto x : vec)
                  cout << x << " ";
           cout << endl;
    
           make_heap(vec.begin(), vec.end());         //将某区间内的元素转化为heap
           cout << "after make_heap(): ";
           for (auto x : vec)
                  cout << x << " ";
           cout << endl;
    
           vec.push_back(4);
           push_heap(vec.begin(), vec.end());          //对heap增加一个元素
           cout << "after push_heap(): ";
           for (auto x:vec)
                  cout << x << " ";
           cout << endl;
    
           pop_heap(vec.begin(), vec.end());           //对heap减少一个元素
           cout << "after pop_heap() : ";
           for (auto x : vec)
                  cout << x << " ";
           cout << endl;
    
           sort_heap(vec.begin(), vec.end()-1);       //对[beg,end-1)区间内的元素进行排序，之后就不再是heap
           cout << "after sort_heap(): ";
           for (auto x : vec)
                  cout << x << " ";
           cout << endl;
           return 0;
    }

运行结果：

**![Center][]**

**参考：Nicolai M,Josuttis. 侯捷译. C++标准库(第2版)\[M\].北京：电子工业出版社,2015:604-607.**

[Center]: /images/20220617/068672eeae7e439991b8db4d5ca1aed3.png