4

因此，假设我有一个包含 N 个具有优先级的项目的优先级队列，其中 N 是数千个，使用一个使用二叉堆实现的优先级队列。我了解EXTRACT-MINandINSERT原语（请参阅Cormen、Leiserson、Rivest使用-MAX而不是-MIN）。

但是DELETE，DECREASE-KEY两者似乎都要求优先级队列能够在给定项目本身的情况下在堆中找到项目的索引（或者，该索引需要由优先级队列的消费者提供，但这似乎违反了抽象）.. ..这看起来像是一个疏忽。有没有一种方法可以有效地做到这一点，而不必在堆顶部添加哈希表？

4

6 回答 6

1

FWIW，如果有人还在寻找类似的东西——我最近在做 Coursera 算法课程之一时偶然发现了一个索引优先级队列的实现。

基本要点是使用 2 个数组合并反向查找以支持 OP 所述的操作。

这是Min Ordered Indexed Priority Queue的明确实现。

于 2013-04-09T13:33:02.927 回答
1

对，我认为这里的重点是，对于优先级队列的实现，您可以使用二进制堆，其 API 为其 HEAP-INCREASE-KEY(A, i, key) 获取索引 (i)，但与可以允许优先级队列采用任意键。您可以自由地让优先级队列封装 key->index 映射的详细信息。如果你需要你的 PQ-INCREASE-KEY(A, old, new) 在 O(log n) 中工作，那么你最好有一个 O(log n) 或更好的索引查找键来保持最新。这可能是一个哈希表或其他快速查找结构。

所以，回答你的问题：我认为数据结构不可避免地会以某种方式增加。

于 2009-09-24T09:06:08.607 回答
0

但是 DELETE 和 DECREASE-KEY 似乎都要求优先级队列能够在给定项目本身的情况下在堆中找到项目的索引

事实上，这不是真的。您可以通过拥有前任和后继指针在未索引的图、链表和“传统”搜索树中实现这些操作。

于 2013-01-05T09:43:58.077 回答
0

“但 DELETE 和 DECREASE-KEY 似乎都要求优先级队列能够在给定项目本身的情况下在堆中找到项目的索引”——从代码中可以清楚地看出，这些方法中至少有一些方法使用索引进入堆而不是项目的优先级。显然，i 是 HEAP-INCREASE-KEY 中的一个索引：

HEAP-INCREASE-KEY(A, i, key)
    if key < A[i]
        then error 'new key is smaller than current key"
    A[i] <-- key
    ...

因此，如果那是 API，请使用它。

于 2009-08-17T23:21:35.843 回答
0

我修改了我的节点类以添加一个 heapIndex 成员。这由堆维护，因为在插入、删除、减少等期间交换节点。

这打破了封装（我的节点现在绑定到堆上），但它运行得很快，这在我的情况下更为重要。

于 2010-02-08T05:21:38.150 回答
0

一种方法是将堆拆分为一侧的元素和另一侧的组织。

对于完整的功能，您需要两个关系： a) 给定一个堆位置（例如 Root），找到坐在那里的元素。b) 给定一个元素，找到它的堆位置。

第二个非常简单：添加一个值“位置”（很可能是基于数组的堆中的索引），每次在堆中移动元素时都会更新该值。

第一个也很简单：您只需保留一堆指向元素（或数组索引）的指针，而不是存储元素。现在，给定一个位置（例如根），您可以通过取消引用它（或访问向量）找到坐在那里的元素。

于 2012-08-23T15:24:29.623 回答