How to implement O(logn) decrease-key operation for min-heap based Priority Queue?
You can do following: store a hashmap inside your heap that maps your heap values to heap indexes. Then you should extend your usual heap-logic just a bit: on Swap(i, j): map[value[i]] = j; map[value[j]] = i; on Insert(key, value): map.Add(value, heapSize) in the beginning; on ExtractMin: map.Remove(extractedValue) in the end; on UpdateKey(value, newKey): index … Read more