make_heap 源码剖析

一：用法示例

一共两个重载：

default (1)   
template <class RandomAccessIterator>
  void make_heap ( RandomAccessIterator first ,  RandomAccessIterator last ) ;
custom (2)   
template <class RandomAccessIterator, class Compare>
  void make_heap ( RandomAccessIterator first ,  RandomAccessIterator last , Compare comp ) ;

该函数的作用就是使[ first , last )满足（大顶或小顶）堆。

例子：

#include<iostream>
#include<functional>
#include<algorithm>
#include<vector>

using namespace std;

int main()
{
  
  int a[10] = { 2,1,6,4,9,10,3,5,8,7 };
  vector<int> v(a, a + 10);//现在是一个杂乱的序列，既不满足小顶堆也不满足大顶堆

  make_heap(v.begin(), v.end());//现在是一个大顶堆，若要改为小顶堆，需要加第三参数 greater<>()

  for (auto it = v.begin(); it != v.end(); it++)
    cout << *it << " ";//10 9 6 8 7 2 3 5 4 1
  cout << endl;
  
  return 0;
}

二：源码及剖析

make_heap源码用到了pop_heap源码实现，链接在此：​​pop_heap​​

这里的源码其实不用深究，读者只要了解堆排序，这里的源码实现原理自然是不难的，所以建议读者要熟悉堆排序，堆排序代码的实现。

包括下一篇文章介绍sort_heap，读者只要熟悉堆排序，理解这两个函数源码实现都很容易。

// TEMPLATE FUNCTION make_heap WITH PRED
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 = _STD move(*(_First + _Hole));
    _Adjust_heap(_First, _Hole, _Bottom,
      _STD move(_Val), _Pred);
    }
  }

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);
  if (2 <= _Last - _First)
    { // validate _Pred and heapify
    _DEBUG_POINTER(_Pred);
    _Make_heap(_Unchecked(_First), _Unchecked(_Last), _Pred,
      _Dist_type(_First), _Val_type(_First));
    }
  }

    // TEMPLATE FUNCTION make_heap
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<>());
  }

源码摘抄自Visual Studio 2015安装目录algorithm文件中。

点击进入目录----> ​​ C++源码剖析目录​​