An immutable indexed priority queue ADT backed by BinaryHeap.
Extends the PrioQueue contract with O(log n) decreaseKey and O(1) contains, enabled by a Map[T, Int] index that tracks each element's current position in the heap array.
Unlike PrioQueue, duplicates are not permitted: offer is a no-op if the element is already present. Use decreaseKey to improve an existing entry's priority. This one-entry-per-key invariant is what makes the index meaningful and decreaseKey correct.
The index is rebuilt from heap.data (O(n)) after each structural operation (offer and take). This is acceptable because:
the O(n) rebuild cost is dominated by the O(E log V) traversal cost
the implementation remains simple, correct, and easy to reason about
Replace oldT with newT if newT has strictly lower priority. If oldT is not present, this is a no-op.
Replace oldT with newT if newT has strictly lower priority. If oldT is not present, this is a no-op.
Implemented by removing oldT from the heap array, inserting newT, and rebuilding the heap from scratch. O(n log n) in the worst case, but correct and simple. The index is rebuilt after the operation. O(n).