c - 在最小堆中插入节点优先考虑左子节点

Question

在获得在最小堆中插入注释的代码后，如果我想在重新排列堆时优先考虑节点的左子节点，我应该做什么更改，我很困惑。输入类似于:

I 5 //insert number 5 in the Min Heap
I 4
I 3
I 2
I 1

输出应该是:

1 2 3 4 5

而不是通常的:

1 2 4 5 3

关于如何获得此输出有什么想法吗？提前致谢。

Answer 1

堆的结构完全取决于插入项目的顺序。原因是，在插入时，您将新节点添加到堆的末尾，然后通过其父节点的指针向上筛选它。规则是:

1. 将项目添加到堆的末尾。
2. 如果该项大于或等于其父项，则完成。
3. 将该项目与其父项交换。
4. 转至2。

根据这些规则，我们来看看按 [5,4,3,2,1] 的顺序插入项目时会发生什么。

[5]
[5,4] // the new item is smaller than its parent, so swap
[4,5]
[4,5,3] // the new item is smaller than its parent, so swap
[3,5,4]
[3,5,4,2] // the new item is smaller than its parent, so swap
[3,2,4,5] // still smaller than its parent
[2,3,4,5]
[2,3,4,5,1] // 1 is smaller than 3, so swap
[2,1,4,5,3] // 1 is smaller than 2, so swap
[1,2,4,5,3]

没有有效的方法来“确定”特定子树的优先级，尤其是在二叉堆中。在只有五个项目的堆中，它看起来很简单，但是添加的每个级别都会增加保持兄弟节点正确顺序的成本。您最好只对节点进行排序并从结果数组中创建一个堆。

排序堆并没有多大帮助。一旦删除第一个项目，重新排列堆将导致它不再排序。