如何在二进制堆实现的优先级队列中保留相同优先级元素的顺序？

我创建了一个二进制堆，它代表一个优先级队列。它只是经典的众所周知的算法。此堆计划不同事件的时间顺序（排序键是时间）。

它支持2种操作：插入和删除。堆的每个节点的密钥大于或等于其每个子节点。但是，使用相同的键添加事件不会保留它们的添加顺序，因为每次调用Remove或Insert之后，堆启动和堆降过程都会破坏顺序。

我的问题是：在经典算法中应该改变什么来保持具有相同优先级的节点的顺序？

一种解决方案是将插入属性的时间添加到插入的元素。每次将新元素插入堆中时，这可能只是一个简单的计数器递增。然后当两个元素优先级相等时，比较插入时间。

据我所知，堆永远不会被建立以保持秩序（这就是为什么“堆排序”值得注意的不是稳定排序）。

我知道你所问的是一个小的算法技巧是否能够改变这一点（这不是一个好的旧的可靠的“时间戳”解决方案）。我不认为这是可能的。

我建议的是这个的一些版本：

要做到这一点，在堆中，而不是交换元素，直到保留顺序：交换元素，直到它作为相同值的元素的树状结束，总是选择在可能的情况下向右移动。

不幸的是，这个问题是你不知道insert将在哪里添加一个给定优先级的元素：它可能最终在树中的任何地方。我认为，改变这种情况不仅仅是对结构的调整。

如果按时间顺序插入元素并保持此顺序（例如通过使用“append”而不是“insert”和“remove_and_pack”而不是“remove”），则可以使用内存地址（强制转换为无符号32-或元素的64位整数（取决于环境）作为最终比较步骤。早期元素的地址数量将低于后者。