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

Question

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

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

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

Answer 1

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

Answer 2

据我所知，堆从来都不是为了保持顺序而构建的（这就是为什么“堆排序”以不是一种稳定的排序而著称）。

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

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

• 保持相同的“插入”；

• 修改“删除”，以确保给定优先级元素的特定顺序。

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

不幸的是，这样做的问题是您不知道 insert 将在哪里添加给定优先级的元素：它可能最终出现在树中的任何位置。我相信，改变这一点不仅仅是对结构的调整。

Answer 3

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