有点基础来看STL 排序算法之sort_heap

C++ STL（Standard Template Library）是C++标准库中的一个重要组成部分，提供了丰富的模板函数和容器，用于处理各种数据结构和算法。在STL中，排序、算数和集合算法是常用的功能，可以帮助我们对数据进行排序、统计、查找以及集合操作等。

STL提供的这些算法，能够满足各种数据处理和分析的需求。通过灵活使用这些算法，我们可以高效地对数据进行排序、查找和聚合操作，提高代码的性能和可读性。在实际编程中，根据具体问题的需求选择合适的算法，能够更好地发挥STL的优势，提高程序的效率。

基本使用

sort_heap()算法函数，用于对堆容器进行排序。sort_heap的用法如下：

template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);

其中，first、last是随机访问迭代器，表示待排序的堆容器的范围。sort_heap函数将[first, last]范围的堆容器排序，并将排序后的结果存储在相同的容器中。

读者需要注意，sort_heap函数执行前，必须先使用make_heap函数对容器进行堆化，然后再利用堆排序算法对其进行排序。

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

using namespace std;


void MyPrint(int val) { cout << val << "  "; }

int main() {

	vector<int> ivec{ 45,76,89,32,11,23,45,9,0,3 };
	for_each(ivec.begin(), ivec.end(), MyPrint);
	cout << endl;


	// 建立堆
	make_heap(ivec.begin(), ivec.end());

	//查堆是否建立成功
	if (is_heap(ivec.begin(), ivec.end()))
	{
		sort_heap(ivec.begin(), ivec.end()); //做堆排序
	}
	
	for_each(ivec.begin(), ivec.end(), MyPrint);


	return 0;
}

sort_heap该函数通过重复执行pop_heap操作来实现排序。pop_heap操作从堆顶提取元素，将该元素放到容器的末尾位置；然后重新调整剩余元素的顺序，使之形成新的堆结构。重复执行pop_heap操作，就可以将堆容器中的所有元素按照递增顺序排序。

底层实现

push_heap算法

实际上，底层会对你的元素，构建如下这样一颗完全二叉树（complete binary tree）也就是说，整棵binary tree 除了最底层的叶节点(s)之外，是填满的，而最底层的叶节点(s)由左至右又不得有空隙。下图列举一个符合sort_heap() 算法的完全二叉树。

比如说，push_heap() 算法，下图列举其实际操演情况。为了满足complete binarytree 的条件，新加人的元素一定要放在最下一层作为叶节点，并填补在由左至右的第一个空格，也就是把新元素插人在底层vector 的end ()处。

新元素是否适合于其现有位置呢?为满足max-heap的条件（每个节点的键值都大于或等于其子节点键值），我们执行一个所谓的 percolate up (上溯）程序: 将新节点拿来与其父节点比较，如果其键值（key)比父节点大，就父子对换位置。如此一直上溯，直到不需对换或直到根节点为止。

等价于说 50节点比24父节点大，所以在节点push到heap中之后，程序又会让50 和24 交换位置，一直到50 终于比68父节点小了，才终止流程。

下面便是 push_heap 算法的实现细节。该函数接受两个迭代器，用来表现一个heap底部容器（vector)的头尾，并且新元素已经插入到底部容器的最尾端。如果不符合这两个条件，push_heap() 的执行结果未可预期。

// 插入节点后向上调整
template <class _RandomAccessIterator, class _Distance, class _Tp>
void __push_heap(_RandomAccessIterator __first,_Distance __holeIndex, _Distance __topIndex, _Tp __value)
{
  // 查父节点
  _Distance __parent = (__holeIndex - 1) / 2;
  // 查节点值是不是比父节点值要大，大则执行上溯(percolate up)


  while (__holeIndex > __topIndex && *(__first + __parent) < __value)  //一直持续到顶端或者说满足了heap次序特性为止
  {
  
    *(__first + __holeIndex) = *(__first + __parent); //将父节点值 赋值给子节点
    __holeIndex = __parent; //将索引值A由指向子节点 更新为指向父节点所在的索引
    __parent = (__holeIndex - 1) / 2; //更新新的父节点索引值
  
  }    
  *(__first + __holeIndex) = __value; //把子节点值 给到索引值A
}

template <class _RandomAccessIterator, class _Distance, class _Tp>
inline void __push_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Distance*, _Tp*)
{
  __push_heap(
      __first, 
      _Distance((__last - __first) - 1), 
      _Distance(0), 
      _Tp(*(__last - 1)));
}

pop _ heap算法

下图所示的是pop_heap()算法的实际操演情况。既然身为max-heap，最大值必然在根节点。pop 操作取走根节点（最终，其实是移至底部容器vector的最后一个元素）之后，为了满足complete binary tree 的条件，必须将最下一层最右边的叶节点拿掉，现在我们的任务是为这个被拿掉的节点找一个适当的位置。

为满足max-heap的条件（每个节点的键值都大于或等于其子节点键值），我们执行一个所谓的 percolate down(下溯）程序:将根节点（最大值被取走后，形成一个"洞"）填入上述那个失去生存空间的叶节点值，再将它拿来和其两个子节点比较键值（key)，并与较大子节点对调位置。如此一直下放，直到这个“洞”的键值大于左右两个子节点，或直到下放至叶节点为止。

等价于说，68被从树被这里拿出来之后，实际是放到原来的vector最后一个元素的位置中去了。导致说空了一个位置，也造成了原来的（线性结构的最后一个元素）24节点值，就要想办法调整树，再重新放到树里面。从而，程序开始做下溯。那65去填空洞，填入空洞，和他的子节点32，26依次比较，当前是32大于24，交换父子节点。交换之后，再进行父子节点比较。32大于26则不变。本次下溯结束。最终要实现的结果是，每次都拿出来最大值，并且重新调整树节点的排布。

下面便是pop_heap算法的实现细节。该函数接受两个迭代器，用来表现一个heap底部容器（vector）的头尾。如果不符合这个条件,pop_heap的执行结果未可预期。

// 取出最大值
template <class _RandomAccessIterator>
inline void pop_heap(_RandomAccessIterator __first, 
                     _RandomAccessIterator __last)
{
  __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,_LessThanComparable);
  __pop_heap_aux(__first, __last, __VALUE_TYPE(__first));
}


template <class _RandomAccessIterator, class _Tp>
inline void  __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*)
{
  __pop_heap(__first, 
             __last - 1,
             __last - 1, 
             _Tp(*(__last - 1)),
             __DISTANCE_TYPE(__first));
  //以上，根据 implicit representation heap的次序特性，pop动作的结果
  //应为底部容器的第一个元素。因此，首先设定欲调整值为尾值，然后将首值调至
  //尾节点（所以以上将迭代器 result设为 last-1）。然后重整 [first, last-1)，
  //使之重新成一个合格的 heap。
}


template <class _RandomAccessIterator, class _Tp, class _Distance>
inline void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
           _RandomAccessIterator __result, _Tp __value, _Distance*)
{
  *__result = *__first; // 设置尾值为首值，最终尾值即为欲求结果 后面会有pop_back 取出尾值再赋值给他
  __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
}


template <class _RandomAccessIterator, class _Tp, class _Distance>
inline void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
           _RandomAccessIterator __result, _Tp __value, _Distance*)
{
  // 设置尾值为首值，最终尾值即为欲求结果 后面会有pop_back 取出尾值再赋值给他
  *__result = *__first; 

  //取完最大值（尾值）之后。就再重新调整heap树
  __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
}


template <class _RandomAccessIterator, class _Distance, class _Tp>
void  __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,_Distance __len, _Tp __value)
{
  _Distance __topIndex = __holeIndex;
  _Distance __secondChild = 2 * __holeIndex + 2;//默认洞节点的右节点值 为较大字节点值


  while (__secondChild < __len) 
  {
      //比较洞节点之左右两个子值 然后以 secondChild 代表较大节点值
      if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
      {
          __secondChild--;
      }
      
      //下溯过程：令较大子值为洞值，再令洞号下移至较大节点处
      *(__first + __holeIndex) = *(__first + __secondChild);
      __holeIndex = __secondChild;

      //找出新洞节点的右子节点值
      __secondChild = 2 * (__secondChild + 1);
  }
  
  if (__secondChild == __len) //没有右子节点，只有左子节点
  {
    //下溯：令左子值为洞值，再令洞号下移至左子节点处
    *(__first + __holeIndex) = *(__first + (__secondChild - 1));
    __holeIndex = __secondChild - 1;
  }

  //将预调整值，填入目前的洞号内，这个时候这棵树一定满足max_heap的次序性。
  __push_heap(__first, __holeIndex, __topIndex, __value);
}
   

注意，pop_heap 之后，最大元素只是被置放于底部容器的最尾端，尚未被取走。如果要取其值，可使用底部容器(vector)所提供的 back ()操作函数。如果要移除它，可使用底部容器(vector)所提供的pop_back ()操作函数。

sort_heap算法

既然每次 pop_heap可获得heap中键值最大的元素，如果持续对整个heap做pop_heap操作，每次将操作范围从后向前缩减一个元素（因为pop_heap会把键值最大的元素放在底部容器的最尾端)，当整个程序执行完毕时，我们便有了一个递增序列。下图所示的是sort_heap的实际操演情况。

sort heap算法:不断对heap进行pop操作，便可达到排序效果，也就是我们在基本使用中验证得到的效果。

下面是sort_heap 算法的实现细节。该函数接受两个迭代器，用来表现一个heap底部容器（ vector）的头尾。如果不符合这个条件,sort_heap的执行结果未可预期。注意，排序过后，原来的 heap 就不再是一个合法的max_heap了。

//每执行一次 pop_heap()，极值（在 STL heap㆗为极大值）即被放在尾端。
//扣除尾端再执行一次 pop_heap()，次极值又被放在新尾端。最后即得
//排序结果。
template <class _RandomAccessIterator>
void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
  __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type, _LessThanComparable);
  while (__last - __first > 1)
  {
      pop_heap(__first, __last--); //每执行一次 pop_heap() 操作范围退缩一格
  }
}

make_heap算法

这个算法用来将一段现有的数据转化为一个heap。说白了，就是把vector的元素，依次放到 complete binary tree 中去，满足算法的push_heap pop_heap sort_heap 这些操作的。

template <class _RandomAccessIterator, class _Tp, class _Distance>
void 
__make_heap(_RandomAccessIterator __first,
            _RandomAccessIterator __last, _Tp*, _Distance*)
{
    //长度为0或1不用排列
    if (__last - __first < 2)
    {
        return;
    }
  _Distance __len = __last - __first;

  //找出第一个需要重排的子树头部，以 parent标示出。由于任何叶节点都不需执行下溯,所以有以下计算。
 
  _Distance __parent = (__len - 2)/2;
    
  while (true) 
  {
      //重拍以 parent为首的子树，len是为了让 __adjust_heap 判断操作范围
    __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));

    //走完根节点，就结束
    if (__parent == 0)
    {
        return;
    }

    //即将重排子树的头部向前一个节点
    __parent--;
  }
}

// 建堆
template <class _RandomAccessIterator>
inline void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
  __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
                 _LessThanComparable);
  __make_heap(__first, __last,__VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
}

heap没有迭代器

heap的所有元素都必须遵循特别的（complete binary tree）排列规则，所以heap 不提供遍历功能，也不提供迭代器。

再理解算法之后，再来看看这个测试用例的结果就没有问题了。

// file: 4heap-test.cpp

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

using namespace std;
void MyPrint(int val) { cout << val << "  "; }
int main() {
     {
        // test heap (以vector完成)
        int ia[9] = { 0, 1, 2, 3, 4, 8, 9, 3, 5 };
        vector<int> ivec(ia, ia + 9);


        make_heap(ivec.begin(), ivec.end());
        for_each(ivec.begin(), ivec.end(), MyPrint);
        cout << endl; //9  5  8  3  4  0  2  3  1

        ivec.push_back(7);
        push_heap(ivec.begin(), ivec.end());
        for_each(ivec.begin(), ivec.end(), MyPrint);
        cout << endl; //9  7  8  3  5  0  2  3  1  4

        pop_heap(ivec.begin(), ivec.end());
        cout << ivec.back() << endl;
        ivec.pop_back(); //9

        for_each(ivec.begin(), ivec.end(), MyPrint);
        cout << endl; //8 7 4 3 5 0 2 3 1

        sort_heap(ivec.begin(), ivec.end());
        for_each(ivec.begin(), ivec.end(), MyPrint);
        cout << endl; //0 1 2 3 3 4 5 7 8
    }

    {
        // test heap (以array完成)
        int ia[9] = { 0, 1, 2, 3, 4, 8, 9, 3, 5 };

        make_heap(ia, ia + 9);
        // array无法动态改变大小，因此不可以对满载的 array做 push_heap()动作。
        //因为那得先在 array尾端增加一个元素。

        sort_heap(ia, ia + 9);
        for_each(ia, ia + 9, MyPrint);//0 1 2 3 3 4 5 8 9
        cout << endl;

        make_heap(ia, ia + 9);
        pop_heap(ia, ia + 9);
        cout << ia[8] << endl; // 9
    }

    {
        // test heap (底层以 array完成) 
        int ia[6] = { 4,1,7,6,2,5 };
        make_heap(ia, ia + 6);
        for_each(ia, ia + 6, MyPrint); //7 6 5 1 2 4
        cout << endl;  
    }
}