堆排序 - acgtyrant/Algorithm-and-Data-Structure GitHub Wiki

我不是 C 死忠,是 C++ 死忠才对,毕竟我把迭代器运用得出神入化了!在写二分查找快速排序时,掌握了左闭右开思想,后者能非常出色地处理一维空间上的数据。

然而如今在写堆排序 HeapSort, 却遇到了相当棘手的问题:既然用一维数据结构储存「二叉堆」,那么得凭着一对迭代器 [first, last), 找出其间任意迭代器的「父节点」以及「子节点」!而且 Algorithm, Part 1 里的二叉堆实现基于一个相当诡异的数组,因为后者的索引居然是从 1 开始的

我曾经想过放弃接收迭代器,直接构造一个「假装索引值从一开始」的数据结构对象并排序算了。

不过话说回来,我到底为什么一定要追求只接收一对迭代器参数呢?迁思回虑,我终于总结出了迭代器相对于索引值的优越性:

  1. 不用接收从零到 size - 1 的整个数据结构,而只接受一对迭代器并进行「局部上的算法处理」,灵活无比。
  2. 迭代器更为抽象,大部分 STL 容器与算法都能用,又彼此独立。
  3. 比起从零开始的索引值范围,还是贯彻左闭右开思想的迭代器范围更为人性化。

固然,硬要处理一对迭代器,又要从零开始索引,这样的堆排序写起来确实相当困难,好在我整理出了从零开始索引的堆索引规律:

首先,假设索引从一开始,那么一个索引值为 n 的节点 a 为父节点时,它的左子节点 b 索引值为 2n, 右子节点索引值 c 当然就是 2n + 1 了。这可以用数学归纳法证明:

根节点索引值是 1, 显然它的左子节点索引值是 2, 即 1 的两倍。

假设一个节点 a 索引值是 n, 它的左子节点 b 索引值是 2n, 掐指一算, 从 a 到 b 之间有 n 个节点,即 [a, b) 区间有 n 个节点,这些节点又有 2n 个子节点,且正好在 b 与 b 的左子节点 d 之间,即 [b, d)! 于是 d 的索引值为 4n. 归纳成立,证毕。

那么,索引从零开始呢?那么上文提到的节点 a 索引值就递减一了,即变成 n - 1, 同理,b 递减为 2n - 1. 显然 b = 2 * a + 1; a 的右子节点 c = b + 1 = 2 * a + 1 + 1 = 2 * (a + 1).

同理,当索引值从一开始,那么一个索引值为 n 且大于 1 的节点 a 的父节点索引值是 n/2; 不论前者是左子节点还是右子节点,因为奇数被二除时会被四舍五入。

然而当索引值从零开始,就不一样了:当某节点的索引值为偶数 n 时,则父节点索引值为 n/2 - 1, 否则是 n/2. 过程略。

迭代器到索引值也好办,iterator - first 即可;同理,索引值到迭代器,直接加到 first 上。

最后,原本想像 Algorithm, Part 1 那样实现个堆类,不过想了想,堆也就只是一个内部结构比较特殊的东西而已,大部分容器对象应该都可以被排成堆,于是我只写了 HeapSort 实现,毕竟我还不清楚堆除了排序还能干什么。HeapSort() 可以接收一对迭代器并用 BuildHeap() 构造成堆,最后 Sink() 一一排序。

注意别把 Sink 里错写成:

template <typename RandomIterator>
void Sink(RandomIterator iterator, RandomIterator first, RandomIterator last) {
  auto left_child = first + (iterator - first) * 2 + 1;
  auto right_child = left_child + 1;
  while (left_child < last && *left_child > *iterator) {
    if (right_child < last && *right_child > *left_child) {
      std::iter_swap(iterator, right_child);
      iterator = right_child;
    } else {
      std::iter_swap(iterator, left_child);
      iterator = left_child;
    }
    left_child = first + (iterator - first) * 2 + 1;
    right_child = left_child + 1;
  }
}

毕竟 *left_child < *iterator*right_child > *iterator 的情况有可能会发生,总之两个子节点都要判断,说实话我当时重构了好久,才写出自己比较满意的代码。

此外,我还实现了 SwimParent, 但后来发现 HeapSort 用不上,就放到这里吧:

template <typename RandomIterator>
RandomIterator Parent(RandomIterator iterator, RandomIterator first) {
  RandomIterator parent;
  if ((iterator - first) % 2 == 0) {
    parent = first + (iterator - first) / 2 - 1;
  } else {
    parent = first + (iterator - first) / 2;
  }
  return parent;
}

template <typename RandomIterator>
void Swim(RandomIterator iterator, RandomIterator first) {
  auto parent = Parent(iterator, first);
  while (iterator > first && *parent < *iterator) {
    std::iter_swap(iterator, parent);
    iterator = parent;
    parent = Parent(iterator, first);
  }
}