Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Indexed binary heaps: decrease a queued priority

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A binary heap keeps the minimum priority at index zero and each parent no larger than either child. A plain heap does not identify the array position of an arbitrary queued job. An indexed heap adds a map from job ID to array position; every swap updates both entries in that map. Decreasing one job's priority can then find its current index and rise it toward the root instead of scanning the entire heap. This program uses a pair of priority and job ID to break equal-priority ties consistently. It rejects duplicate IDs and increases through the decrease operation. It does not implement cancellation, an arbitrary priority increase, worker execution, or persistence.

Operational case

A dispatch queue starts with J-47 at priority 9, J-52 at 6, J-61 at 12, and J-83 at 7. A control-plane update changes J-61 to priority 3. The map finds J-61 directly; swaps move it above its parent while keeping all recorded positions current. The first removal therefore returns J-61 at 3, followed by J-52 at 6. A stale position map is a latent fault: a later decrease may edit a different job even when the heap's root happened to look correct just after one operation. Tests should inspect the map and heap invariant after every mutation.

Working Python program

python
class DispatchHeap:
    def __init__(self):
        self.items = []
        self.position = {}

    def swap(self, left, right):
        self.items[left], self.items[right] = self.items[right], self.items[left]
        self.position[self.items[left][1]] = left
        self.position[self.items[right][1]] = right

    def rise(self, index):
        while index:
            parent = (index - 1) // 2
            if self.items[parent] <= self.items[index]:
                break
            self.swap(parent, index)
            index = parent

    def sink(self, index):
        size = len(self.items)
        while 2 * index + 1 < size:
            child = 2 * index + 1
            if child + 1 < size and self.items[child + 1] < self.items[child]:
                child += 1
            if self.items[index] <= self.items[child]:
                break
            self.swap(index, child)
            index = child

    def add(self, job_id, priority):
        if job_id in self.position:
            raise ValueError("job already queued")
        self.position[job_id] = len(self.items)
        self.items.append((priority, job_id))
        self.rise(len(self.items) - 1)

    def decrease(self, job_id, priority):
        index = self.position[job_id]
        old_priority = self.items[index][0]
        if priority > old_priority:
            raise ValueError("priority increased")
        self.items[index] = (priority, job_id)
        self.rise(index)

    def pop(self):
        if not self.items:
            raise IndexError("dispatch heap is empty")
        result = self.items[0]
        last = self.items.pop()
        del self.position[result[1]]
        if self.items:
            self.items[0] = last
            self.position[last[1]] = 0
            self.sink(0)
        return result


dispatch = DispatchHeap()
for job_id, priority in (("J-47", 9), ("J-52", 6), ("J-61", 12), ("J-83", 7)):
    dispatch.add(job_id, priority)
dispatch.decrease("J-61", 3)
print(dispatch.pop())
print(dispatch.pop())

Output

Output
(3, 'J-61')
(6, 'J-52')

Time, space, and tradeoff

With n queued jobs, add, decrease, and pop move along at most O(log n) heap levels. Position lookup is expected O(1) for a well-behaved hash map, so decrease is expected O(log n) time; pathological hash collisions can change that assumption. Reading the minimum is O(1) if the heap is nonempty. The array and position map each use O(n) space. Equal priorities are ordered by job ID in this example, which is not submission order. If stable arrival order matters, store a monotonic sequence number as a separate tie-break field and keep its value unchanged across decreases.

Common Mistakes

  • Do not swap heap entries without updating both job positions.
  • Do not assume equal priorities preserve arrival order when job IDs break ties.
  • Do not call a higher numeric priority a decrease in this min-heap.
  • Do not claim the queue executes, acknowledges, or durably stores jobs.

Connected lessons

Apply this operation in the warehouse release project, then check the deletion and dependency quiz.

Shortest routes: skip stale min-heap entries extends this operation.

D-ary heaps: trade shallower ascent for wider extraction adds a related lifecycle choice.

Fibonacci heaps: cut on decrease and consolidate on removal adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details