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

Question

我创建了一个二叉堆，表示优先队列。这是一个经典的众所周知的算法。该堆调度不同事件的时间排序（排序关键字为时间）。

它支持两个操作：插入和移除。堆中每个节点的键大于或等于其子节点的键。但是，在添加具有相同键的事件时，由于在调用插入或移除之后，堆向上和堆向下过程会破坏顺序，所以它们并不保留它们被添加的顺序。

我的问题是：要如何修改这个经典的算法以保留具有相同优先级的节点的顺序？

- psihodelia

---

假设您添加了一个具有已存在优先级的新元素，那么它的顺序会是什么？ - Karoly Horvath

添加另一个字段称为插入顺序（long long），并且在插入时始终递增。因此，您最终会得到键对：优先级+插入顺序。 - bestsss

Answer 1

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

- Juraj Blaho

---

然后，当两个元素的优先级相等时，比较插入时间。但是，如果我有多个具有相同键的元素，比较它们将需要遍历二叉树！ - psihodelia

在您的实现中，插入或删除元素时必须比较优先级。只需通过扩展此比较来比较时间戳和优先级即可。 - Juraj Blaho

Answer 2

据我所知，堆不会被构建来维护顺序（这就是为什么“堆排序”以不稳定排序而闻名）。

我理解你的问题是是否有一种小的算法技巧可以改变这一点（这不是老式可靠的“时间戳”解决方案）。我认为这是不可能的。

我的建议是以下版本：

- 保持相同的“插入”； - 修改“删除”，使其确保给定优先级元素的某种顺序。

为了做到这一点，在堆下降时，不是交换元素直到保持顺序：而是交换一个元素直到它成为相同值元素树的末端，总是在可以时选择向右走。

不幸的是，这个问题在于你不知道插入将添加一个给定优先级的元素的位置：它可能出现在树的任何地方。我认为更改这个会不止是对结构的微调。

- Jérémie

---

这是一个有趣的问题，值得更深入地研究一下（我会去做的）。 - Jérémie

实际上，这个问题已经被提出并回答了：http://cstheory.stackexchange.com/questions/593/is-there-a-stable-heap - Jérémie

Answer 3

如果元素按照时间顺序插入并且保持这个顺序（例如使用“append”而不是“insert”，使用“remove_and_pack”而不仅仅是“remove”），您可以使用元素的内存地址（根据环境转换为无符号32位或64位整数）作为最终比较步骤。早期元素的地址将比后来的元素具有更低的数字地址。

- Olof Forshell