最小堆是否按“默认”排序

Question

我刚拿起“算法简介”，我开始在 c# 中实现堆和堆排序算法。

实现一个从双精度数组构造最小/最大堆的函数，我注意到构造的堆有一些有趣的属性。

可以从左到右，从上到下（从根到叶，按级别）读取构建的最小堆，并将对其进行排序。

这是 minheap 的属性，还是我只是无法获得此属性不适用的情况。最大堆不能这样工作，至少我在这里得到了什么。

输出：

2345 7 34 6 3 5 4 5 1 2 3 2 1 3 1 3 2 1 (maxheap)

1 1 1 1 2 2 2 3 3 3 3 4 5 5 6 7 34 2345 (minheap)

感谢您提前回复！

Answer 1

堆只在父节点和它们各自的子节点之间有关系。同一级别的节点之间没有关系。

For Min Heaps: Value of Parent node <= Value of its child nodes
For Max Heaps: Value of Parent node >= Value of its child nodes

所以当从上到下，从左到右移动时，没有必要对最小堆进行排序。在你的情况下，这只是一个巧合。
例如：考虑这个序列：1, 3, 2, 5, 4, 10, 9
这些是按 MinHeapify 顺序排列的，但显然 不是按排序顺序排列的。
访问此交互式堆链接或此链接以正确可视化堆的构建方式。