什么是堆的tree-structure？

Question

我正在阅读 Nicolai M. Josuttis 的 "The C++ standard library, a tutorial and reference"，第 2 版。

他在第 607 页解释了堆数据结构和相关的 STL 函数：

The program has the following output:

on entry: 3 4 5 6 7 5 6 7 8 9 1 2 3 4
after make_heap(): 9 8 6 7 7 5 5 3 6 4 1 2 3 4
after pop_heap(): 8 7 6 7 4 5 5 3 6 4 1 2 3
after push_heap(): 17 7 8 7 4 5 6 3 6 4 1 2 3 5
after sort_heap(): 1 2 3 3 4 4 5 5 6 6 7 7 8 17

我想知道这是怎么弄清楚的？例如，为什么路径 9-6-5-4 下的叶子“4”是节点“5”的左侧子节点，而不是右侧节点？在 pop_heap 之后，树结构是什么？在IDE调试模式下我只能看到向量的内容，有没有办法弄清楚树结构？

Answer 1

向量中的第一个元素是索引 0 处的根。它的左侧 child 位于索引 1 处，右侧 child 位于索引 2 处。一般来说：left_child(i) = 2 * i + 1 和right_child(i) = 2 * i + 2 和 parent(i) = floor((i - 1) / 2)

另一种思考方式是堆从左到右填充树中的每一层。在向量中的元素之后，第一级是 9（1 个值），第二级是 8 6（2 个值），第三级是 7 7 5 5（4 个值），依此类推。这两种方式都将帮助您在给定向量时以树结构绘制堆。

Answer 2

why the leaf "4" under path 9-6-5-4 is the left side child of node "5", not the right side one?

因为如果它在右侧，则意味着基础向量中存在间隙。树结构仅用于说明目的。它不是堆实际存储方式的表示。树结构通过一个简单的数学公式映射到底层向量上。

树的根节点是向量的第一个元素（索引 0）。节点左侧 child 的索引是通过简单公式从其 parent 的索引中获得的：i * 2 + 1。而右边的索引child是通过i * 2 + 2.

得到的

And after pop_heap what's the tree structure then?

根节点与它的两个children¹中的较大者交换，重复此操作直到它位于那个树。然后它与最后一个元素交换。然后将该元素推 up 树，如有必要，通过与它的 parent 交换（如果它更大）。

根节点与堆的最后一个元素交换。然后，通过与它的两个 children¹ 中的较大者交换，将这个元素向下推到堆中。重复此操作，直到它处于正确的位置（即它不小于其 children 中的任何一个）。

所以在 pop_heap 之后，你的树看起来像这样：

     ----- 8 -----
     |           |
  ---7---     ---6---
  |     |     |     |
 -7-   -4-   -5-   x5
 | |   | |   | |   x
 3 6   4 1   2 3   9

9 实际上不再是堆的一部分，但它仍然是向量的一部分，直到您通过调用 pop_back 或类似方法将其擦除。

_{1.如果 children 相等，就像您示例中树中相邻的 7 的情况一样，它可以任意选择。我相信 std::pop_heap 将它发送到右边，但我不确定这是否是实现定义的}

什么是堆的tree-structure？

What is the tree-structure of a heap?

c++

heap