STL 中的 heap

前言

源码来自 SIGSTL3.0

在看之前默认你已经拥有了关于 堆, 大小根堆, 堆排序 等前置知识. heap 严格来说并不属于容器, 它只是实现关于对操作的一些模板函数, 故没有迭代器和遍历等操作

heap 作用描述

将一段序列转换为满足堆的性质(大根堆或者小根堆)
进行堆排序
向上维护堆的性质
取出堆顶元素

heap 分析

push 插入元素

插入函数为 push_heap 由于堆排序是不稳定的以及可能需要交换两个不连续位置的值所以 heap 只接受 RandomAccessIterator 类型的迭代器

template <class RandomAccessIterator>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) {
  __push_heap_aux(first, last, distance_type(first), value_type(first));
}

template <class RandomAccessIterator, class Distance, class T>
inline void __push_heap_aux(RandomAccessIterator first, RandomAccessIterator last, Distance*, T*) 
{
    // 这里传入的是两个迭代器的长度, 0, 还有最后一个数据
  __push_heap(first, Distance((last - first) - 1), Distance(0),  T(*(last - 1)));
}

可以看到 push_heap 作为接口函数调用了 __push_heap_aux 而它又作为接口函数封装了__push_heap 不难发现 __push_heap 就是 push 操作的核心代码

template <class RandomAccessIterator, class Distance, class T>
void __push_heap(RandomAccessIterator first, Distance holeIndex,Distance topIndex, T value) 
{
  //取得要调整的叶子节点的上级节点
  Distance parent = (holeIndex - 1) / 2;
    // 这里判断的是当前没有达到堆顶并且传入的值大于根节点的值, 那就将根节点下移
  while (holeIndex > topIndex && *(first + parent) < value) {
      // 将根节点下移
    *(first + holeIndex) = *(first + parent);
    holeIndex = parent;
    parent = (holeIndex - 1) / 2;
  }    
    
    // 将数组插入到合适的位置, 可能是根也可能是叶
  *(first + holeIndex) = value;
}

这里的插入和一般上看到的入堆是有一些出入的, 我更倾向于把它看作一种自底向上的堆调整方式.
holeIndex 作为的是要新数字的叶子节点位置它可以是任意一个叶子节点, 正如它的名字一样 空洞下标 所以对于 __push_heap 函数要做的就是待这个空出的叶子节点的值确定之后向上调整维护堆的性质即可, 但是在 __push_heap_aux 封装的过程中, 参数默认为该段序列的最后一个位置, 对应到满二叉树上即为最后一个叶子节点

这里可以对照下面的图理解一下

当然也可以令其他叶子节点为空然后向上维护堆的性质如下图

所以 __push_heap 函数的本质就是在一个固定大小的堆里维护某一个叶子节点到堆顶节点的链去保证整个堆的性质

pop 弹出元素

pop 操作用于弹出堆顶元素并继续维护其余元素满足堆的性质但是 pop 操作并没有真正意义上把元素删除掉，而是将顶部元素覆盖掉, 将多出的 (按照弹出前后逻辑上的元素数量比较) 放置在最后并不指向该元素 pop 的实现有两种, 一种是按照标准库默认的优先级判断实现, 另一种则是按照用户自己传入的 仿函数中自定义的判断标准, 判断优先级. 这里将两种实现都列举出来, 但只会以第一种方式作为例子进行分析.

template <class RandomAccessIterator, class Compare>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                     Compare comp) {
    __pop_heap_aux(first, last, value_type(first), comp);
}

template <class RandomAccessIterator, class T, class Compare>
inline void __pop_heap_aux(RandomAccessIterator first, 
                  RandomAccessIterator last, T*, Compare comp) {
  __pop_heap(first, last - 1, last - 1, T(*(last - 1)), comp,
             distance_type(first));
}
template <class RandomAccessIterator, class T, 
						class Compare, class Distance>
inline void __pop_heap(RandomAccessIterator first, 										   RandomAccessIterator last,
                       RandomAccessIterator result, T value, 
                       Compare 	comp, Distance*) {
  *result = *first;
  __adjust_heap(first, Distance(0), Distance(last - first), 
                value, comp);
}
template <class RandomAccessIterator, class T, class Distance>
inline void __pop_heap(RandomAccessIterator first, 					            RandomAccessIterator last,
           RandomAccessIterator result, T value, Distance*) {
  *result = *first;	// 因为这里是大根堆, 所以first的值就是最大值, 先将最大值保存.
  __adjust_heap(first, Distance(0), Distance(last - first), value);
}

依旧可以看出 pop 操作是在 __pop_heap 函数上进行了两次封装. 故只需要去分析 __pop_heap 函数即可

这里重点分析第一个种形式

template <class RandomAccessIterator, class Distance, class T>
void __adjust_heap(RandomAccessIterator first, Distance holeIndex, Distance len, T value) 
{
    // holeIndex传入的是0
  Distance topIndex = holeIndex;
    // secondChild是右孩子的一个节点
  Distance secondChild = 2 * holeIndex + 2;
  while (secondChild < len) {
      // 比较左右节点, 根节点较下就将根节点下移, 比较大的节点上移
    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;
  }
    // 重新调整堆
  __push_heap(first, holeIndex, topIndex, value);
}
// cmpare版本只将比较修改成用户定义的函数
template <class RandomAccessIterator, class Distance, class T, class Compare>
void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
                   Distance len, T value, Compare comp) {
  Distance topIndex = holeIndex;
  Distance secondChild = 2 * holeIndex + 2;
  while (secondChild < len) {
    if (comp(*(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;
  }
  __push_heap(first, holeIndex, topIndex, value, comp);
}

__pop_heap 函数的本质就是在维护堆性质的情况下去把原堆顶进行覆盖, 然后再以覆盖堆顶的某个儿子作为堆顶再重复这个操作, 直到某个叶子节点为空时, 利用 __push_heap 函数将原来堆的最后一个叶子节点补充进这个空叶子节点并向上维护新的堆 即可这时可以发现在堆的最后依旧会留有一个值为操作堆之前的数据, 但是由于弹出了堆顶元素, 所以堆的规模在逻辑上是减小了 1 的, 所以对于最后一个多出的元素无论是什么都是无关紧要的

上面描述的比较绕, 具体可以看下面的图理解一下

有一种特殊情况即为当空洞到达最后一个叶子节点的父节点时, 由于不能比较左右儿子的大小去选择使哪个节点为空, 所以只能选择左儿子为空

在调整完毕后, 调用 __push_heap 函数去把最后一个叶子节点的值放入之前被置空的叶子节点后进行调整使剩下的完全二叉树满足堆的性质

结合上面的图可以发现, 除去置空点为根的子树 , 以置空点左右儿子为根的子树 均满足堆的性质

当置空点为叶子节点时, 其余元素依旧构成了堆(由于该节点只是被逻辑置空所以依旧可以认为当前是一棵完全二叉树) 所以只需要将最后一个叶子节点填入该置空叶子节点并维护其与堆顶的链, 就可以得到一个堆

这时再结合上面的 __push_heap 函数的分析, 其实可以更好的理解它的思想. 从最后插入堆只是前面的 push 的一种情况而已, 而 __push_heap 的设计可以让它不只可以处理入堆操作, 也实现了修改维护堆性质的功能, 从而使用这项功能支持了 pop 操作的实现

分割线 —————————————————————————-

下面的两种操作

建堆
堆排序

它们的实现与日常中见到的实现就基本没有差异了

make_heap函数, 将数组变为堆存放.

template <class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
  __make_heap(first, last, value_type(first), distance_type(first));
}
template <class RandomAccessIterator, class T, class Distance>
void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*,
                 Distance*) {
  if (last - first < 2) return;
    // 计算长度, 并找出中间的根值
  Distance len = last - first;
  Distance parent = (len - 2)/2;
    
  while (true) {
      // 一个个进行调整, 放到后面
    __adjust_heap(first, parent, len, T(*(first + parent)));
    if (parent == 0) return;
    parent--;
  }
}

sort, 堆排序其实就是每次将第一位数据弹出从而实现排序功能.

template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
  while (last - first > 1) pop_heap(first, last--);
}
template <class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
               Compare comp) {
  while (last - first > 1) pop_heap(first, last--, comp);
}

heap 总结

heap 没有自己的迭代器, 甚至它都不能被称作一个容器, 我认为比较合适的说法是将支持 RandomAccessIterator 的容器进行堆的操作. heap 中最重要的就是 pop 和 push 的实现

而且需要注意的是, push 操作在堆的最后进行插入时, 是要容器构建好最后一个位置的空间和值的

push 操作本质还是用于维护插入后堆的性质的