我已经创建了一个二进制堆，它表示一个优先级队列。这只是经典的众所周知的算法。该堆计划按时间顺序排列的不同事件（排序键是时间）。如何在优先级队列中实现二进制堆的同一优先级元素的顺序？
它支持2种操作：插入和删除。每个节点的堆密钥大于或等于其每个子节点。但是，使用相同密钥添加事件不会保留它们添加的顺序，因为每次调用Remove或Insert后，堆积和堆积过程都会中断顺序。
我的问题是：经典算法中应该改变什么以保持具有相同优先级的节点的顺序？
一种解决方法是将插入时间的属性添加到插入的元素。每次将新元素插入堆时，这可能只是一个简单的计数器递增。然后当两个元素的优先级相同时，比较插入的时间。
是的，这是如何完成的。 – bestsss
“然后，当两个元素的优先级相同时，比较插入的时间。” ---但我可以有更多，只有两个相同的密钥元素。比较它们将需要遍历二叉树！ – psihodelia
@psihodelia：否。在您的实施中，插入或移除元素时必须对优先级进行比较。只要比较优先级和时间戳，扩展这一比较。 –
如果按时间顺序插入元素并保持此顺序（例如通过“追加”而不是“插入”和“remove_and_pack”而不是“删除”），则可以使用内存地址（cast to作为最后的比较步骤，取决于环境的无符号32或64位整数）。早期元素的数字地址要低于后者。
据我所知，堆是从来没有建立，以维持秩序（这就是为什么“堆排序”是值得注意的而不是是一个稳定的排序）。
我明白你在问什么是一个小的算法技巧是否可以改变这个（这不是一个好的旧的可靠的“时间戳”解决方案）。我不认为这是可能的。
我会建议一些版本的这个：
保持相同的“插入”;
修改“删除”，以确保某个给定优先级的元素具有某种顺序。
要做到这一点，在堆下来，而不是交换的元素，直到订单保留：交换的元素，直到它的值相同的元素的树状结束，总是选择走如果可以的话。
不幸的是，这个问题是，你不知道插入哪里会添加一个给定优先级的元素：它可能会在树中的任何地方结束。我相信，改变这一点不仅仅是对结构的调整。
这是一个有趣的问题，值得多看一些（我会）。 –
其实，这已经被问及回答了：http://cstheory.stackexchange.com/questions/593/is-there-a-stable-heap –
谢谢你的链接！ – psihodelia
假设你添加一个已经存在的优先级的新元素..什么是顺序？ –
添加另一个称为插入顺序的字段（long long），并且在插入时它总是递增。所以你最终会带着最后一个键：优先级+插入顺序 – bestsss