Indexed Priority Queue Decrease-Key

Problem

Simulate an indexed priority queue with a decrease-key operation.

operations contains "insert" (ids[i] with priority values[i]), "decrease" (lower the priority of ids[i] to values[i]), "pop_min" (return the id with the smallest priority or None), or "get" (return the priority of ids[i] or None). A position map keeps every id's index in the heap so decrease-key can sift up directly.

Return the list of recorded results (None for insert and decrease).

Hint

The position map turns decrease-key into a sift-up from a known index.

Test cases

case 1

in: [["insert","insert","insert","pop_min","decrease","pop_min","pop_min"],[1,2,3,0,1,0,0],[5,3,4,0,1,0,0]]

expected: [null,null,null,2,null,1,3]

case 2

in: [["pop_min"],[0],[0]]

expected: [null]

case 3

in: [["insert","get","decrease","get"],[7,7,7,7],[9,0,2,0]]

expected: [null,9,null,2]

case 4

in: [["insert","insert","decrease","pop_min"],[1,2,1,0],[10,20,5,0]]

expected: [null,null,null,1]

Starter codePython

def indexed_pq_ops(operations, ids, values):
    # Your code here
    pass

4 test cases · run your code against them in the editor