Priority queue (or min-heap) with O(log n) deletion of arbitrary node

Question

I've got a bunch of items I'm storing in a min-heap (via PriorityQueue), and I have a need to efficiently delete arbitrary items. I know that in a standard min-heap implementation, deleting an arbitrary element (given that you know the position of that element in the heap) takes O(log n) time, while finding the position is O(n). So, basically, I need to keep a separate data structure which holds each item's position in the heap.

I more-or-less know how I'd implement this from scratch, but I'm wondering if there's a smart way to utilize/subclass PriorityQueue (which has other useful features) to accomplish this.

To clarify, I need the O(1) peek-min that a PQ/Min-Heap affords.

Answer 1

Have you thought about using a TreeMap. It is like a PriorityQueue with Map like features.

TreeMap does not support O(1) for deletion, however, it performs deletion operation in O(logN). Far better than O(N) support by PriorityQueue. It also returns the head of the collection ( min or max element depending on the comparator just like PriorityQueue ). Along with that it also returns the tail of the collection ( max or min ). Tail functionality is not supported by PriorityQueue and hence you sometimes end up keeping two queues to track both head and tail.

• Head Element -> TreeMap#firstKey
• Tail Element -> TreeMap#lastKey

Definitions

• TreeMap

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

• Red-Black tree

A red–black tree is a kind of self-balancing binary search tree in computer science. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.

Reference to Red-Black Trees algorithm in Introduction to Algorithms

Runtimes:

+----------------+-----------------+----------------------------------------------+
|   Operation    |     TreeMap     |                PriorityQueue                 |
+----------------+-----------------+----------------------------------------------+
| Insert(Object) | O(logN)[put]    | O(logN)[add]                                 |
| Get(Object)    | O(logN)[get]    | O(N)+ O(N)+O(logN) [contains + remove + add] |
| Delete(Object) | O(logN)[remove] | O(N)[remove]                                 |
| Head           |O(logN)[firstKey]| O(1)(peek)                                   |
| Tail           | O(logN)(lastKey)| -                                            |
+----------------+-----------------+----------------------------------------------+

Answer 2

I also needed fast (log N) heap deletion for timeout handling. Java's standard PriorityQueue is pretty ineffective when you have tens of thousands of elements in the queue which you have to delete very often.

So here's a heap implementation I've created: fast-delete-heap

So basically it maintains an extra hash map with element-to-heap index which allows fast O(log N) deletion. It comes with a cost of slower insertion though.