sort_heap

转换堆到排序的范围。

template<class RandomAccessIterator>
   void sort_heap(
      RandomAccessIterator _First, 
      RandomAccessIterator _Last
   );
template<class RandomAccessIterator, class Predicate>
   void sort_heap(
      RandomAccessIterator _First, 
      RandomAccessIterator _Last,
      Predicate _Comp
   );

参数

• _First
  处理第一元素位置的随机访问迭代器。堆目标。

• _Last
  寻址最终元素的随机访问迭代器位置一个目标。堆

• _Comp
  用户定义的谓词函数对象定义一个元素小于另一个。 二进制谓词采用两个参数，并且在满足时返回 true，在未满足时返回 false。

备注

堆具有两个属性：

• 第一个元素。始终最大。

• 元素在对数时间可能添加或删除。

在应用程序之后，则此算法，范围应用于它不再是堆。

因为元素不一定相同的相对顺序保留，这不是一个稳定排序。

堆为一个极好的方式实现优先级别队列，并用于标准模板库 (STL) 容器 priority_queue 类适配器的实现。

引用的范围必须是有效的；所有指针必须 dereferenceable，然后在序列中的最后位置从开始来访问通过递增。

N 是最复杂记录 N，其中 N = (_Last - _First)。

示例

// alg_sort_heap.cpp
// compile with: /EHsc
#include <algorithm>
#include <functional>
#include <iostream>
#include <ostream>
#include <string>
#include <vector>
using namespace std;

void print(const string& s, const vector<int>& v) {
    cout << s << ": ( ";

    for (auto i = v.begin(); i != v.end(); ++i) {
        cout << *i << " ";
    }

    cout << ")" << endl;
}

int main() {
    vector<int> v;
    for (int i = 1; i <= 9; ++i) {
        v.push_back(i);
    }
    print("Initially", v);

    random_shuffle(v.begin(), v.end());
    print("After random_shuffle", v);

    make_heap(v.begin(), v.end());
    print("     After make_heap", v);

    sort_heap(v.begin(), v.end());
    print("     After sort_heap", v);

    random_shuffle(v.begin(), v.end());
    print("             After random_shuffle", v);

    make_heap(v.begin(), v.end(), greater<int>());
    print("After make_heap with greater<int>", v);

    sort_heap(v.begin(), v.end(), greater<int>());
    print("After sort_heap with greater<int>", v);
}

示例输出

Initially: ( 1 2 3 4 5 6 7 8 9 )
After random_shuffle: ( 9 2 7 3 1 6 8 4 5 )
     After make_heap: ( 9 5 8 4 1 6 7 2 3 )
     After sort_heap: ( 1 2 3 4 5 6 7 8 9 )
             After random_shuffle: ( 5 8 3 1 2 9 7 6 4 )
After make_heap with greater<int>: ( 1 2 3 4 5 9 7 6 8 )
After sort_heap with greater<int>: ( 9 8 7 6 5 4 3 2 1 )

要求

标头： <算法>

命名空间: std

请参见

参考

heap

标准模板库