遍历完整的二叉最小堆

Question

我不确定如何遍历下面的树形结构，以使节点始终按升序排列。对数组[9 8 7 6 5 4 3 2 1 0]进行堆操作得到数组[0 1 3 2 5 4 7 9 6 8]，我认为它对应于此表示：

想要保留数组（因为我希望以后能够高效地插入），如何有效地按升序遍历它呢？（即按[0 1 2 3 4 5 6 7 8 9]的顺序访问节点）

- Inuart

---

如果你想要一个排序过的列表，那么堆并不是合适的数据结构。有许多数据结构可以有效地维护一个排序过的列表。我个人在使用跳表（skip lists）时非常成功，你可以参考一下 skip lists。 - Jim Mischel

跳表能否使用连续内存？ - Inuart

你可以在数组中构建一个跳表，但这样做会很麻烦。我想我理解了你的问题。你想要一种类似于二叉堆的隐式有序数据结构，但是你希望能够高效地按升序（即顺序）遍历它。如果这样的东西存在，我不知道它的存在。 - Jim Mischel

Answer 1

只需对数组进行排序。排序后仍将保持最小堆性质，没有其他算法在渐近意义下更加高效。

- David Eisenstat

---

我每次遍历它都需要进行排序吗？如果是这样的话，那么拥有堆的意义就不存在了，我想。 - Inuart

@Inuart 这是一个更有趣的问题，因为有一些顺序可以利用。我建议使用智能排序算法来检测运行（例如timsort），并具有O(n)时间复杂度的最佳情况。 - David Eisenstat

Answer 2

您无法像遍历BST一样遍历堆。@Dukeling关于BST是更好的选择如果排序遍历是一个重要的操作是正确的。但是，您可以使用以下算法，它需要O(1)额外的空间。

假设您有通常的数组形式的堆。

1. 按排序顺序逐个删除项目以"访问"它们进行遍历。 2. 访问第i个项目后，将其放回堆数组中的位置n-i，该位置当前未被堆使用（假设基于零的数组索引）。 3. 遍历后，反转数组以创建新的堆。

删除项目需要O(n log n)的时间。反转另外需要O(n)的时间。

如果您不需要完全遍历，可以随时停止并通过运行O(n)堆化操作来“修复”数组。例如，请参见此处的伪代码。

- Gene

Answer 3

我实际上更愿意建议在这里使用自平衡二叉搜索树（BST）：

self-balancing binary search tree (BST)

二叉搜索树（BST）是一种基于节点的二叉树数据结构，具有以下特性：

• 一个节点的左子树只包含键值小于该节点的键的节点。
• 一个节点的右子树只包含键值大于该节点的键的节点。
• 左右子树都必须是二叉搜索树。
• 不能有重复的节点。

使用BST以排序的方式遍历（称为中序遍历）比使用堆更简单且更节省空间。

BST将支持O(log n)插入和O(n)遍历。

如果您要在再次进行遍历之前进行大量插入，则将其排序为数组可能更有效 - 相关的运行时间为O(1)插入和O(n log n)获取排序顺序 - 此选项比使用BST更有效的确切点需要进行基准测试。

---

出于好奇，以下是如何按排序顺序遍历堆的方法（如果您不想只是不断从堆中移除最小值直到它为空，这可能是更简单的选择，因为移除最小值是堆的标准操作）。

从堆的属性来看，有些元素可能在左子树中，其后面的元素在右子树中，再之后的在左子树中等等。这意味着你不能完全完成左子树然后开始右子树 - 在执行此操作时，你可能需要将堆的大部分保留在内存中。

主要思想基于一个事实：一个元素始终比它的两个子元素都小。

基于此，我们可以构建以下算法：

- 创建一个新的堆 - 将原始堆的根插入新堆中 - 当新堆有元素时： - 从堆中移除最小值 - 输出该元素 - 如果该元素有子元素，则将其添加到原始堆中的新堆中

这需要 O(n log n) 的时间和 O(n) 的空间（参考下，BST 遍历需要 O(log n) 的空间），更不用说增加的代码复杂度了。

- Bernhard Barker

---

你知道有没有使用连续内存的二叉搜索树实现吗？ - Inuart

你可以使用类似堆的表示方法，其中使用一个数组，根位于第一个索引（为了简单起见，从1开始索引），任何给定索引i的节点的左右子节点分别在2i和2i+1处。我不知道是否有任何库执行此操作，可能是因为调整大小的成本很大。 - Bernhard Barker

Answer 4

如果您不需要重复项，可以使用std::set。 std::set迭代器将按顺序遍历并根据默认比较器维护排序。对于int类型，默认比较器是<，但如果您使用rbegin()以相反的顺序遍历，则可以从最高到最低遍历。或者您可以添加自定义比较器。前者如下所示：

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main() {

  vector<int> data{ 5, 2, 1, 9, 10, 3, 4, 7, 6, 8 };

  set<int> ordered;
  for (auto n : data) {
    ordered.insert(n);

    // print in order
    for (auto it = ordered.rbegin(); it != ordered.rend(); it++) {
      cout << *it << " ";
    }
    cout << endl;
  }

  return 0;
}

Output:
5 
5 2 
5 2 1 
9 5 2 1 
10 9 5 2 1 
10 9 5 3 2 1 
10 9 5 4 3 2 1 
10 9 7 5 4 3 2 1 
10 9 7 6 5 4 3 2 1 
10 9 8 7 6 5 4 3 2 1 

- Nick Codignotto

---

看起来也是个不错的解决方案，谢谢！你知道有没有什么好的方法可以允许重复吗？ - Inuart