对于一项任务，我们被指示创建一个通过二叉堆实现的优先级队列，而不使用任何内置类，我通过使用数组存储排队的对象成功地做到了这一点。但是，我有兴趣学习如何使用实际的树结构来实现另一个队列，但在这样做时我遇到了一些问题。
我如何跟踪要执行插入和删除操作的节点？我尝试过使用链表，它会在插入每个节点时追加它 - 从开始添加新的子节点第一个列表节点，并从另一端删除。然而，当元素在树中重新排列时，这会分崩离析，因为 child 被添加到错误的位置。
编辑:也许我应该澄清一下——我不确定如何才能找到最后一个被占用的和第一个未被占用的叶子。例如，我总能知道最后插入的叶子，但如果我要删除它，我怎么知道下次删除该项目时要删除哪个叶子？插入也是如此——在当前叶子包含两个子元素后，我怎么知道要跳到下一个叶子？
最佳答案
二叉堆的树实现使用 complete tree [或几乎满树:除了最深的一层外，每一层都满了]。
你总是“知道”哪个是最后一个被占用的叶子——你从哪里删除[并在它改变后修改它是 O(logn) 所以这不是问题]，你总是“知道”哪个是第一个未占用的叶子，您可以在其中添加元素 [并且再次修改它也是 O(logn) 在它改变之后]。
算法思路很简单:
insert:插入元素到第一个未被占用的叶子，使用heapify [筛选] 将该元素放到堆中的正确位置。
delete_min:用最后一个被占用的叶子替换第一个元素，并移除最后一个被占用的叶子。然后，heapify [筛选] 堆。
编辑:请注意，delete() 可以对任何元素执行，但不仅限于头部 - 找到要用最后一片叶子替换的元素将是 O(n)，这将使该操作变得昂贵。出于这个原因，delete() 方法 [除了头部] 通常不是堆数据结构的一部分。
关于java - 通过二叉树结构实现的二叉堆，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7609047/