// <algorithm> 
// 默认(1)
template <class RandomAccessIterator>
    void make_heap (
​        RandomAccessIterator first,
        RandomAccessIterator last);
// 自定义(2)    
template <class RandomAccessIterator,
    class Compare>
    void make_heap (
        RandomAccessIterator first,
        RandomAccessIterator last,
        Compare comp );

用给定范围构造出一个堆。

该函数等价于:

template<class _RanIt> inline
void make_heap(_RanIt _First, _RanIt _Last)
{	// make [_First, _Last) into a heap, using operator<
    _STD make_heap(_First, _Last, less<>());
}

template<class _RanIt,
class _Pr> inline
    void make_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
{	// make [_First, _Last) into a heap, using _Pred
    _DEBUG_RANGE(_First, _Last);
    _DEBUG_POINTER(_Pred);
    if (1 < _Last - _First)
        _Make_heap(_Unchecked(_First), _Unchecked(_Last), _Pred,
        _Dist_type(_First), _Val_type(_First));
}

template<class _RanIt,
class _Diff,
class _Ty,
class _Pr> inline
    void _Make_heap(_RanIt _First, _RanIt _Last, _Pr _Pred, _Diff *, _Ty *)
{	// make nontrivial [_First, _Last) into a heap, using _Pred
    _Diff _Bottom = _Last - _First;
    for (_Diff _Hole = _Bottom / 2; 0 < _Hole;)
    {	// reheap top half, bottom to top
        --_Hole;
        _Ty _Val = _Move(*(_First + _Hole));
        _Adjust_heap(_First, _Hole, _Bottom,
            _Move(_Val), _Pred);
    }
}

template<class _RanIt,
class _Diff,
class _Ty,
class _Pr> inline
    void _Adjust_heap(_RanIt _First, _Diff _Hole, _Diff _Bottom,
    _Ty&& _Val, _Pr _Pred)
{	// percolate _Hole to _Bottom, then push _Val, using _Pred
    _Diff _Top = _Hole;
    _Diff _Idx = 2 * _Hole + 2;

    for (; _Idx < _Bottom; _Idx = 2 * _Idx + 2)
    {	// move _Hole down to larger child
        if (_DEBUG_LT_PRED(_Pred, *(_First + _Idx), *(_First + (_Idx - 1))))
            --_Idx;
        *(_First + _Hole) = _Move(*(_First + _Idx));
        _Hole = _Idx;
    }

    if (_Idx == _Bottom)
    {	// only child at bottom, move _Hole down to it
        *(_First + _Hole) = _Move(*(_First + (_Bottom - 1)));
        _Hole = _Bottom - 1;
    }
    _Push_heap(_First, _Hole, _Top, _Move(_Val), _Pred);
}
  • firstlast

    分别指向将被构造成堆的序列中初始及末尾位置的随机访问迭代器(Random-access Iterators)。这个范围即 [first,last) ,包括 first 到 last 间的所有元素,包括 first 指向的元素,但不包括 last 指向的元素。

    comp

    二元谓词(Binary)函数,以两个元素为参数,然后返回一个可转换成 bool 类型的值。

    其返回值表明按所指定的严格弱序排序(Strict weak ordering)时,第一个参数所传进来的元素是否在第二个参数所传进来的元素前面。

    该函数不能修改其参数。

    可以是函数指针(Function pointer)类型或函数对象(Function object)类型。

  • 无。

  • 参照 std::sort 以获得与自定义函数谓词、函数对象谓词、对象数组、lambda 表达式 C++11、初始化列表 std::initializer_list C++11 等相关的例子。

    例 1

    #include <iostream>
    #include <algorithm>
    #include <iterator>
    #include <vector>
    
    #define CLASSFOO_VECTOR(type, name, ...) \
    static const type name##_a[] = __VA_ARGS__; \
    std::vector<type> name(name##_a, name##_a + sizeof(name##_a) / sizeof(*name##_a))
    
    namespace ClassFoo{
    
        void MakeHeap_1() {
    // 构造 vector 对象 CLASSFOO_VECTOR(int, foo, { 0, 6, 33, 8, 10, -2, 13 }); // 构造一个堆 std::make_heap(foo.begin(), foo.end()); // 打印 foo std::copy( foo.begin(), foo.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl; // 从堆中弹出(最大)元素 std::pop_heap(foo.begin(), foo.end()); // 实际删除 foo.pop_back(); // 打印 foo std::copy( foo.begin(), foo.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl; // 向堆中压入一个元素 // 先压入元素至向量末尾 foo.push_back(56); // 压入堆中 std::push_heap(foo.begin(), foo.end()); // 打印 foo std::copy( foo.begin(), foo.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl; // 排序 std::sort_heap(foo.begin(), foo.end()); // 打印 foo std::copy( foo.begin(), foo.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl; } } int main() { ClassFoo::MakeHeap_1(); return 0; }

    33 10 13 8 6 -2 0 
    13 10 0 8 6 -2 
    56 10 13 8 6 -2 0 
    -2 0 6 8 10 13 56 

  • 复杂度

    O(3*N)N 等值于 std::distance(first,last)

    数据争用相关

    修改在范围 [first,last) 中的部分(或所有)元素。

    异常安全性相关

    如果元素比较、元素交换(Swap)、元素移动(Move)或操作某个迭代器抛异常,该函数才会抛异常。

    注意 无效参数将导致未定义行为(Undefined behavior)