我创建了一个二进制堆,它表示一个优先级队列。这只是经典的众所周知的算法。该堆安排了不同事件的时间顺序(排序键是time)。
它支持2种操作:插入和删除。堆中每个节点的密钥都大于或等于其每个子节点。但是,使用相同的键添加事件不会保留添加顺序,因为每次调用Remove或Insert之后,堆向上和堆向下过程都会破坏该顺序。
我的问题是:在经典算法中应更改哪些内容以保留具有相同优先级的节点的顺序?
一种解决方案是将插入时间属性添加到插入的元素。每次将新元素插入堆时,这可能只是一个简单的计数器增加。然后,当两个元素的优先级相等时,比较插入时间。