一尘不染

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

algorithm

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

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

我的问题是:在经典算法中应更改哪些内容以保留具有相同优先级的节点的顺序?


阅读 254

收藏
2020-07-28

共1个答案

一尘不染

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

2020-07-28