堆排序算法 [英] Heap sort algorithm

问题描述

我已经做了一个二叉树的堆。它不是一个数组。我不知道我将如何去有关排序此。我知道我需要的最后一个节点，并将其放置在根，并做了下来一堆泡沫。这部分我有。我遇到的问题是要知道如何获得新的最后一个节点。是否有一个算法来找到最后一个节点？我是否需要跟踪每个父节点中的每个节点上？

I have a heap made of a binary tree. Its not an array. I was wondering how would i go about sorting this. I know i need to take the last node and place it at the root and do a down heap bubble. This part i have. The problem I am having is knowing how to get the new last node. Is there an algorithm to find the last node? Do i need to keep track of each of the parent nodes on each node?

感谢。

推荐答案

假设你开始是一个完整的树的树，我会看，如果你能保持每个节点的高度的轨道上。

Assuming the tree you start with is a full tree, I would see if you can keep track of the height of each node.

然后，当你在树遍历寻找下一个孩子删除您做一次检查在每一个节点。如果L.H> R.H向左走，否则向右走。 唯一需要注意的我有这样的想法是不是就意味着，当你把你需要更新所有的高峰节点。其中添加邻成本（log n）的。但是，因为你穿越下降，这是THETA树（log n）的，这不是太重要的事渐近。

Then, when you iterate through the tree looking for the next child to remove you do a check at each node. If L.h > R.h go left, else go right. The only caveat I have on this idea is it means when you take that node you need to update all the heights. Which add a cost of O(log n). But since you're traversing down the tree which is theta(log n) it's not too big a deal asymptotically.

这篇关于堆排序算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！