堆中的替换和删除操作

Question

我正在解决一个需要使用堆数据结构来解决的问题。虽然操作将由insert和extract min控制，但在某些情况下，我需要替换项的键（增加或减少）或删除项key。由于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

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

Answer 1

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

一种选择是通过将每个对象的位置存储在对象本身中，使堆具有侵入性。这样，当你想查找对象的位置时，你可以在O（1）中通过查找对象内的位置字段来完成。在

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

希望这有帮助！在