algorithm - 堆排序算法

Question

我有一个由二叉树组成的堆。它不是一个数组。我想知道我将如何进行排序。我知道我需要获取最后一个节点并将其放置在根并进行向下堆气泡。这部分我有。我遇到的问题是知道如何获取新的最后一个节点。有没有找到最后一个节点的算法？我是否需要跟踪每个节点上的每个父节点？

谢谢。

Answer 1

假设您开始的树是一棵完整的树，我会看看您是否可以跟踪每个节点的高度。

然后，当您遍历树以查找下一个要删除的子节点时，请检查每个节点。如果 Lh > Rh 向左走，否则向右走。我对这个想法的唯一警告是，当您使用该节点时，您需要更新所有高度。这增加了 O(log n) 的成本。但是，由于您正在遍历 theta(log n) 的树，因此渐近地并不是什么大问题。