0

我正在解决一个需要使用堆数据结构解决的问题。尽管操作将由 insert 和 extract-min 主导，但在某些情况下，我需要替换项​​目的键（增加或减少）或完全删除项目，键。由于该heapq模块不提供这些操作并且在堆中搜索一个项目O(n)，因此使用 dict 进行簿记然后仅使用它来查找项目的位置、删除或替换它并调用heapify恢复会更聪明堆属性——所有这些操作都将在O(logn). 不过，问题是我无法实现这样的字典。

h, bkp = [], {}
heappush(h, (5, 'a'))
bkp['a'] = # index of 'a' in heap
heappush(h, (7, 'b'))
bkp['b'] = # index of 'b' in heap
heappush(h, (1, 'c'))
bkp['c'] = # index of 'c' in heap

# deleting 'a'
h[bkp['a']], h[-1] = h[-1], h[bkp['a']]
h.pop()
heapify(h) 

#update indices in bkp

问题 - 如何找到堆中新插入的索引，以及在删除或推送操作之后，如何重新计算堆中现有项的索引？

4

1 回答 1

0

有几种方法可以做到这一点。

一种选择是通过将每个对象的位置存储在对象本身中来使您的堆具有侵入性。这样，每当您想查找对象的位置时，只需查找对象内的位置字段即可在 O(1) 中执行此操作。

您还可以将辅助哈希表或 BST 与将堆中的每个值映射到其在堆中的位置的堆一起存储。这类似于第一种方法，但有一个额外的间接层。

希望这可以帮助！

于 2012-12-11T17:20:40.353 回答