我有一堆项目存储在一个小根堆中(通过
我大概知道如何从头开始实现这个功能,但我想知道是否有一种聪明的方法利用/子类化
为了澄清,我需要PQ /小根堆提供的O(1)peek-min。
PriorityQueue
实现),我需要高效地删除任意项目。我知道在标准的小根堆实现中,删除任意元素(假设你知道该元素在堆中的位置)需要O(log n)时间,而查找位置需要O(n)时间。所以,基本上,我需要保持一个单独的数据结构来保存每个项目在堆中的位置。我大概知道如何从头开始实现这个功能,但我想知道是否有一种聪明的方法利用/子类化
PriorityQueue
(具有其他有用的特性)来实现这一点。为了澄清,我需要PQ /小根堆提供的O(1)peek-min。