如何使用二进制堆来实现优先级队列？

Question

尽管我已经获得了计算机科学学士学位(这在大学里有所涉及),但我从来没有能够理解二进制堆和优先级队列之间的关系.它只是...没有点击.我完全理解二进制堆是什么,我知道如何在数组中实现一个.我也知道优先队列是什么.但是他们两个如何结合在一起呢？

一个快速的谷歌查询显示了很多像这样的文章.哪种解释,但我还有更多问题:

优先级队列需要确保如果添加了两个具有相同优先级的项目,则它们将按照添加它们的顺序删除.二进制堆如何确保这一点？(事实上,如果我没有弄错的话,那么所有项目具有相同优先级的边界情况会产生违反此规则的堆).
当您从堆中删除根,然后放入最后一个元素代替根,然后需要将其与其中一个子项交换时会发生什么 - 但两个子节点具有相同的值.你如何选择与哪一个交换？(记住相同优先级项目的FIFO规则)

我在这里错过了什么？

Answer 1

优先级队列是抽象数据类型,如"堆栈"或"关联数组".可以有许多不同的方法来实现优先级队列 - 您可以使用二进制堆,二项式堆,Fibonacci堆,配对堆等.

我不认为有任何内在要求优先级队列是"稳定的"并且要求具有相同优先级的元素以相同的相对相对顺序出列,这与没有内在要求的方式相同.排序算法是稳定的(虽然很多).这是一个不错的财产,但通常不保证.这就是为什么,例如,标准的heapsort不是一个稳定的类型.

幸运的是,调整二进制堆以保持稳定并不太难.保持与二进制堆相关联的计数器.每当向堆中添加元素时,使用计数器的当前值标记它并递增计数器.在执行堆操作时,使用计数器作为仲裁器,以确定如果两个值比较相等则哪个值更小.从本质上讲,这会将比较更改为首先对实际值进行词典对比,然后再对插入顺序进行比较.

希望这可以帮助!