Learning Heaps and Priority Queues
Efficiently finding the next important item
Introduction
Many algorithms do not need the entire collection to be sorted. They only need quick access to the item with the highest or lowest priority. A heap is designed for exactly that situation. It stores elements in a partially ordered tree so the smallest item in a min-heap or the largest item in a max-heap is always available at the root. Priority queues commonly use heaps because insertion and removal can stay efficient even when the collection grows. This makes heaps useful in scheduling, graph algorithms, simulations, operating systems, and any workflow where the next most important item must be selected repeatedly.
Heap Structure and the Heap Property
A binary heap is a complete binary tree: every level is full except possibly the last, and the final level is filled from left to right. The completeness rule keeps the tree compact, while the heap property controls priority. In a min-heap, every parent is less than or equal to its children. In a max-heap, every parent is greater than or equal to its children. This does not mean the entire structure is globally sorted.
Array Representation
Because the tree is complete, a heap fits naturally into an array. With zero-based indexing, the children of position i are 2i+1 and 2i+2, and the parent is floor((i-1)/2). The array representation avoids pointer objects and makes navigation arithmetic simple.
Insertion: Add, Then Bubble Up
To insert a value, place it at the next free position so the tree remains complete. Then compare it with its parent. If the heap property is violated, swap the value upward until the correct order is restored.
INSERT_MIN_HEAP(heap, value)
append value to heap
i <- last index
while i > 0
parent <- floor((i - 1) / 2)
if heap[parent] <= heap[i]
break
swap heap[parent], heap[i]
i <- parentGet Bishal Goutam’s stories in your inbox
Join Medium for free to get updates from this writer.
The height of a complete binary heap is O(log n), so insertion takes O(log n) time in the worst case.
Removing the Highest-Priority Item
In a min-heap, the root is the smallest value. Removing it creates a gap at the top. The standard approach moves the last element to the root, removes the final array slot, and then pushes the new root downward by repeatedly swapping it with the smaller child.
EXTRACT_MIN(heap)
if heap is empty
error
minimum <- heap[0]
heap[0] <- heap[last]
remove last element
i <- 0
while i has a child
smaller <- index of smaller child
if heap[i] <= heap[smaller]
break
swap heap[i], heap[smaller]
i <- smaller
return minimum
Heapify and Building a Heap
Heapify means restoring the heap property around a position, usually by pushing a value downward. A heap can be built by inserting elements one at a time in O(n log n), but a bottom-up build starts at the last internal node and heapifies backward. That method builds the whole heap in O(n) time.
BUILD_MIN_HEAP(array)
for i <- floor(n/2) - 1 down to 0
MIN_HEAPIFY(array, i)Priority Queue Operations
A priority queue is an abstract data type, while a heap is one common implementation. Typical operations are insert, peek at the highest-priority item, and remove that item. With a binary heap, peek is O(1), while insert and extract are O(log n).
Scheduling Example
Imagine a job scheduler where each task has a next-run timestamp. A min-heap can store the timestamp as the priority. The task at the root is the one that should run next. After it executes, the scheduler removes it, calculates its next run time if it repeats, and inserts it again. The system never needs to fully sort all scheduled tasks after every change.
Min-Heap vs Max-Heap
Use a min-heap when the smallest key represents highest priority, such as earliest deadline, lowest cost, or shortest tentative distance. Use a max-heap when the largest key should come first, such as highest score or largest available item. The mechanics are the same; only the comparison direction changes.
