c - 如何在作为二叉堆实现的优先级队列中保留相同优先级元素的顺序？

Question

我创建了一个二叉堆，代表一个优先级队列。这只是经典的众所周知的算法。这个堆安排了不同事件的时间顺序(排序键是时间)。

它支持 2 种操作:插入和删除。堆的每个节点的键都大于或等于它的每个子节点。但是，添加具有相同键的事件并不会保留它们的添加顺序，因为每次调用 Remove 或 Insert 之后，heap-up 和 heap-down 过程都会打乱顺序。

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

Answer 1

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