Binary Heap: The Engine Behind Priority Queues

A binary heap is a tree-shaped data structure designed to make one particular question very efficient: which item should be processed next? That question appears whenever items have priorities, deadlines, costs, or scores. A task scheduler, for example, may need to select the most urgent task from a collection that is constantly changing.

A heap is the usual foundation of a priority queue. It does not keep every item fully sorted. Instead, it maintains just enough order to guarantee that the most important item is always at the root. New items are added with sift-up, and the root is removed with sift-down. These operations take logarithmic time because the heap is kept compact as a complete binary tree.

This article explains the heap invariant, the complete-tree structure, array representation, insertion, extraction, heapify, and the distinction between min-heaps and max-heaps. The examples use task priorities so that each structural change has a practical purpose.

A Priority Queue Example​

Imagine a task scheduler that assigns smaller numbers to more urgent work:

• Emergency backup: priority 1
• Customer report: priority 3
• Routine cleanup: priority 5
• Optional statistics: priority 8

If the scheduler must always process the smallest priority number first, it needs quick access to the minimum. A min-heap is a natural fit because the smallest value is always stored at the root.

If the meaning of the priorities is reversed and larger numbers represent more important work, the scheduler can use a max-heap. In that case, the largest value is always at the root.

The priority queue is an abstract interface. It describes operations such as adding an item, inspecting the next item, and removing the next item. A binary heap is one practical way to implement that interface.

The Two Rules That Define a Binary Heap​

A binary heap follows two separate rules. Keeping them separate makes heap algorithms much easier to understand.

1. The shape rule: complete binary tree​

The nodes must form a complete binary tree. Every level is full except possibly the final level, and nodes on the final level are placed from left to right with no gaps.

2. The ordering rule: heap property​

Each parent must be correctly ordered relative to its children.

For a min-heap:

Every parent is less than or equal to each of its children.

For a max-heap:

Every parent is greater than or equal to each of its children.

Both rules are necessary. A tree could satisfy the parent-child comparisons but have an irregular shape, or it could be complete but violate the comparisons. Only a complete tree that also satisfies the heap property is a binary heap.

The Heap Property in a Min-Heap​

In a min-heap, the smallest value is at the root. Consider this structure:

        2
      /   \\
     5     7
    / \\   / \\
   9   6 8  10

The root, 2, is no greater than 5 and 7. The node 5 is no greater than 9 and 6. The node 7 is no greater than 8 and 10. Therefore, the heap property is satisfied everywhere.

Notice what the heap property does not say. It does not require the values to be sorted from left to right. The value 9 appears before 6 in a level-order listing, and that is perfectly acceptable. A heap compares each parent with its children; it does not compare every item with every other item.

This weaker ordering is intentional. A fully sorted structure would require more work to maintain. A heap maintains only the relationship needed to expose the minimum efficiently.

The Heap Property in a Max-Heap​

A max-heap reverses the comparison. Every parent is at least as large as its children:

        10
      /    \\
     8      9
    / \\    / \\
   3   6  2   7

The root is 10, the largest value. The node 8 is greater than 3 and 6, and the node 9 is greater than 2 and 7. This is a valid max-heap even though the remaining values are not globally sorted.

A useful memory aid is simple:

• A min-heap puts the minimum item at the top.
• A max-heap puts the maximum item at the top.

Most algorithms are identical for both variants. The main difference is the comparison used when deciding whether a parent and child are in the correct order.

Why Completeness Matters​

The complete-binary-tree rule keeps the height small. A complete tree grows by filling each level before starting the next one, so its height is proportional to log n, where n is the number of nodes.

For example, a complete tree may look like this:

        A
      /   \\
     B     C
    / \\   /
   D   E F

The last level contains D, E, and F, occupying the leftmost positions. This is complete.

By contrast, the following shape is not complete:

        A
      /   \\
     B     C
      \\   /
       E F

There is an empty position before E. The last level is not filled from left to right, so this shape is not allowed for a binary heap.

Completeness has two important consequences. First, it limits the number of levels that sift-up or sift-down may traverse. Second, it allows the tree to be stored compactly in an array. No explicit left-child, right-child, or parent pointers are required.

Array Representation​

A binary heap is normally stored in level order. The root comes first, followed by its children from left to right, then the next level from left to right, and so on.

The min-heap from earlier becomes:

[2, 5, 7, 9, 6, 8, 10]

The array indexes map to the tree as follows:

        2                 index 0
      /   \\
     5     7             indexes 1 and 2
    / \\   / \\
   9   6 8  10          indexes 3, 4, 5, and 6

With zero-based indexing, the formulas are:

parent(i) = floor((i - 1) / 2), for i > 0
left(i)   = 2i + 1
right(i)  = 2i + 2

For example, the value at index 1 is 5. Its left child is at index 3, containing 9, and its right child is at index 4, containing 6. The value at index 2 is 7, with children at indexes 5 and 6.

With one-based indexing, the formulas become:

parent(i) = floor(i / 2)
left(i)   = 2i
right(i)  = 2i + 1

Either convention is valid. The important requirement is consistency. Mixing zero-based and one-based formulas is a common source of bugs.

The array representation offers several practical advantages:

• It uses compact contiguous storage.
• It avoids a separate object and pointer for every node.
• Parent and child positions are calculated with simple arithmetic.
• Adding a position at the end automatically preserves the complete-tree shape.
• Removing the final position also preserves that shape.

The array is not sorted. In a min-heap, only index 0 is guaranteed to contain the minimum. The other entries are arranged to satisfy parent-child relationships.

Heap Versus Binary Search Tree​

A binary heap and a binary search tree are both binary tree structures, but their ordering rules and use cases are different.

A binary search tree generally follows this rule:

• Values in the left subtree are smaller than the node.
• Values in the right subtree are larger than the node.

That rule applies to entire subtrees. If a node contains 10, every value in its left subtree should be smaller than 10, and every value in its right subtree should be larger, according to the tree's policy for duplicates.

A heap uses a local rule instead. A min-heap only requires a parent to be no greater than its children. A value in the left subtree may be larger than a value in the right subtree. The heap therefore does not support ordinary sorted traversal in the way a binary search tree does.

A heap is a strong choice when an application repeatedly asks for the next highest-priority item. A search tree is more appropriate when the application must search for arbitrary keys, perform ordered traversal, or locate predecessor and successor values.

Insertion: Append First, Then Sift Up​

Insertion must preserve both heap invariants. The standard method has two steps:

1. Append the new item at the end of the array.
2. Sift it upward until the heap property is restored.

Appending at the end is what preserves completeness. The new item occupies the next open position in level order.

Start with this min-heap:

[2, 5, 7, 9, 6, 8, 10]

Suppose a task with priority 3 arrives. Append it:

[2, 5, 7, 9, 6, 8, 10, 3]

The new value is the left child of 9. The shape is still complete, but the ordering rule is broken because 3 is smaller than its parent, 9.

Swap 3 with 9:

[2, 5, 7, 3, 6, 8, 10, 9]

Now 3 is a child of 5, and it is still smaller than its parent. Swap again:

[2, 3, 7, 5, 6, 8, 10, 9]

The new value is now a child of 2. Because 2 is smaller than 3, the min-heap property is restored.

The new item may move several levels, but it stops as soon as its parent is correctly ordered. This process is called sift-up, bubble-up, or percolate-up.

Sift-Up Pseudocode​

For a min-heap with zero-based indexing:

insert(value):
    append value to heap
    index = last index

    while index > 0:
        parent = floor((index - 1) / 2)

        if heap[parent] <= heap[index]:
            break

        swap heap[parent] and heap[index]
        index = parent

For a max-heap, stop when the parent is greater than or equal to the child. Equivalently, swap while the child is greater than the parent.

Why Sift-Up Works​

Before insertion, assume the heap is valid. Appending a new value does not change any relationship among existing nodes. The only potentially invalid relationship is between the new node and its parent.

Each swap moves the new value one level closer to the root. The possible violation moves upward with it, while the rest of the heap remains unchanged. Once the value reaches the root or is correctly ordered relative to its parent, there is no remaining violation on that path.

The shape invariant is preserved throughout because sift-up swaps values between already occupied positions. It does not add, remove, or move tree positions.

Insertion Complexity​

A complete binary tree with n nodes has height O(log n). The new item can move up at most that many levels. Therefore:

• Appending takes O(1) time.
• Sift-up takes O(log n) time in the worst case.
• Insertion takes O(log n) time overall.
• The extra working space is O(1) for an iterative implementation.

An item that is already near its correct position may require less work, but the worst-case bound remains logarithmic.

Extraction: Replace the Root, Then Sift Down​

The main removal operation is called extract-min for a min-heap and extract-max for a max-heap. It removes and returns the root.

For a min-heap, the root is the smallest value. For a max-heap, it is the largest. Removing it creates an empty position at the top, so the algorithm uses the last array element as a replacement:

1. Save the root.
2. Move the final element to index 0.
3. Remove the final array slot.
4. Sift the replacement downward.

Start with this min-heap:

[2, 3, 7, 5, 6, 8, 10, 9]

The root 2 is the minimum. Move the final value, 9, to index 0 and remove its old position:

[9, 3, 7, 5, 6, 8, 10]

The shape is complete again, but 9 is larger than both children. For a min-heap, compare it with the smaller child, 3, and swap:

[3, 9, 7, 5, 6, 8, 10]

The value 9 now has children 5 and 6. The smaller child is 5, so swap again:

[3, 5, 7, 9, 6, 8, 10]

The replacement is now a leaf, so the heap property has been restored. This downward repair is called sift-down, bubble-down, or percolate-down.

Choosing the Correct Child​

The child-selection step is crucial. In a min-heap, when both children are smaller than the current value, swap with the smaller child. Suppose the current value is 10 and the children are 4 and 7. Swapping with 7 would leave 10 above 4, so the heap would still be invalid. Swapping with 4 is required.

In a max-heap, select the larger child instead. If the current value is 3 and the children are 8 and 6, swap with 8. Otherwise, 3 could remain below a child that is larger than it.

Sift-Down Pseudocode​

For a min-heap with zero-based indexing:

extract-min():
    if heap is empty:
        report that no item is available

    result = heap[0]
    heap[0] = heap[last index]
    remove the last element
    index = 0

    while the node has at least one child:
        left = 2 * index + 1
        right = 2 * index + 2
        smaller = left

        if right exists and heap[right] < heap[left]:
            smaller = right

        if heap[index] <= heap[smaller]:
            break

        swap heap[index] and heap[smaller]
        index = smaller

    return result

For a max-heap, select the larger child and swap while the current value is smaller than that child.

Why Sift-Down Works​

Before extraction, the heap is valid. Moving the last item to the root restores the complete-tree shape because the final position is then removed and all earlier positions remain occupied.

The replacement may violate the heap property with its children, but the subtrees below those children were valid before the operation. Sift-down follows one path from the root toward the leaves. At each step, it exchanges the replacement with the child that should be above it. The possible violation moves downward until the replacement is correctly positioned or reaches a leaf.

The rest of the tree remains valid because only the path containing the replacement changes. When the replacement is ordered relative to both children, the complete heap is valid again.

Extraction Complexity​

The replacement can descend at most the height of the complete tree. Therefore:

• Reading the root takes O(1) time.
• Moving the last element takes O(1) time.
• Sift-down takes O(log n) time in the worst case.
• Extract-min or extract-max takes O(log n) time overall.
• An iterative implementation uses O(1) extra working space.

A root can also be inspected without removal. This operation is usually called peek, minimum, or maximum, and it takes O(1) time because the root is at array index 0.

Building a Heap with Heapify​

Sometimes all input values are already available in an array. In that case, the goal is to transform the array into a heap. This operation is called heapify or build-heap.

One simple approach is to begin with an empty heap and insert every value. Since each insertion uses sift-up, building a heap this way takes O(n log n) time in the worst case.

A more efficient bottom-up method runs in O(n) time. Leaves already satisfy the heap property because they have no children. The algorithm therefore starts with the last internal node and applies sift-down while moving toward the root.

With zero-based indexing, the last internal node is at:

floor(n / 2) - 1

The procedure for a min-heap is:

build-min-heap(array):
    start = floor(length(array) / 2) - 1

    for index from start down to 0:
        sift-down(array, index)

Consider this array:

[9, 4, 7, 1, 3, 8, 2]

The leaves are the values at indexes 3 through 6. They are already valid one-node heaps. Process index 2 first. Its value is 7 and its children are 8 and 2. The smaller child is 2, so swap:

[9, 4, 2, 1, 3, 8, 7]

Next process index 1. Its value is 4 and its children are 1 and 3. Swap with 1:

[9, 1, 2, 4, 3, 8, 7]

Finally process the root, 9. Its children are 1 and 2, so swap with 1:

[1, 9, 2, 4, 3, 8, 7]

The value 9 now has children 4 and 3. Swap with the smaller child, 3:

[1, 3, 2, 4, 9, 8, 7]

The result is a valid min-heap.

Why Bottom-Up Heapify Is Linear​

It may initially seem that running sift-down on many nodes must cost O(n log n). The key observation is that most nodes are close to the leaves and can move only a short distance.

About half of the nodes are leaves and require no sift-down work. Roughly a quarter are one level above the leaves and can move at most one level. Only a small number of nodes are near the root and can move many levels. When all possible movements are added together, the total work is O(n).

Thus, there is an important distinction:

• Building by repeated insertion: O(n log n) worst-case time.
• Building bottom-up with heapify: O(n) time.

Both methods produce a valid heap, but bottom-up heapify is generally the better choice when the complete input array is available at once.

Task Scheduling with a Priority Queue​

A priority queue typically supports three central actions:

• Add a task with a priority.
• Inspect the most urgent task.
• Remove the most urgent task.

Suppose a scheduler uses smaller values for greater urgency and receives these tasks:

(task A, 5)
(task B, 2)
(task C, 4)
(task D, 1)

Each task is inserted at the end of the heap and may move upward. The internal arrangement can change after every insertion, but the smallest priority remains at the root. Repeated extraction returns the tasks in priority order:

(task D, 1)
(task B, 2)
(task C, 4)
(task A, 5)

The heap does not need to sort the entire collection after every new task. It only preserves the information necessary to identify the next task efficiently. This is the central reason a heap is useful for priority queues.

A task record can contain more than a numeric priority:

priority
name
creation time
payload

When two heap entries are swapped, the complete task records move together. The comparison normally uses the priority field.

If equal-priority tasks must be processed in arrival order, the heap property alone is not enough to guarantee that behavior. A scheduler can add a sequence number and compare entries by (priority, sequence number). The priority remains the primary key, while the sequence number breaks ties consistently.

Complexity of Common Heap Operations​

For a binary heap containing n items, the standard bounds are:

The logarithmic bounds come from the height of a complete binary tree. The constant-time peek operation is especially valuable because it provides immediate access to the next priority item without changing the heap.

Common Invariant Mistakes​

Heap implementations are compact, but a small comparison or indexing error can invalidate the structure.

Treating a heap as a sorted array​

A min-heap is not required to be in ascending order. For example:

[1, 4, 2, 9, 7, 8, 3]

This can be a valid min-heap because each parent is no greater than its children. The value 3 appearing after 8 does not matter. Validation must check every parent against its existing children, not whether the entire array is sorted.

For a min-heap, check:

heap[i] <= heap[2i + 1]    when the left child exists
heap[i] <= heap[2i + 2]    when the right child exists

For a max-heap, reverse the comparisons.

Choosing an arbitrary child during sift-down​

The correct child must be selected before a swap. Choose the smaller child in a min-heap and the larger child in a max-heap. Choosing the wrong child can leave another parent-child violation behind.

Removing the root without using the last element​

The standard extraction operation replaces the root with the last array element and then removes the final slot. This preserves the complete-tree shape with a constant number of positional changes before sift-down.

Mixing indexing conventions​

With zero-based storage, the left child is 2i + 1. With one-based storage, it is 2i. Using the formula from one convention with an array from the other can produce incorrect parent and child relationships.

Ignoring empty and one-element heaps​

Extraction from an empty heap needs defined behavior, such as returning an error or an empty result. For a one-element heap, extraction should leave an empty array and should not attempt to inspect children afterward.

Updating a Task's Priority​

A scheduler may need to change the priority of a task that is already in the heap. The direction of repair depends on the heap type and the direction of the change.

In a min-heap:

• If a task's priority decreases, it may need to move upward because it has become more urgent.
• If a task's priority increases, it may need to move downward because it has become less urgent.

In a max-heap, these directions are reversed:

• Increasing a value may require sift-up.
• Decreasing a value may require sift-down.

The heap must know where the task is located. If the implementation stores only an array and has no auxiliary index map, locating an arbitrary task may require a linear scan. Once the task is found, the repair takes at most O(log n) time.

This illustrates an important practical point: the complexity of a complete feature depends not only on the heap's repair operation but also on how items are located and identified.

Heap Sort​

A heap can also be used to sort an array. The general process is:

1. Build a heap.
2. Move the root to its final sorted position.
3. Reduce the active heap boundary.
4. Restore the heap property in the remaining active portion.

For ascending order, a max-heap is commonly used. The maximum value is at the root, so it can be moved to the end of the array. The remaining prefix is then repaired as a max-heap. Repeating this process places values in ascending order.

For descending order, the corresponding approach uses a min-heap.

Heap sort takes O(n log n) time in the worst case. Building the heap takes O(n), and the repeated root placements and repairs contribute O(n log n) overall. Heap sort can be performed in place using the input array apart from constant extra working space. It is not generally stable, so equal values do not automatically retain their original relative order.

Heap sort also shows why a heap should not be confused with a sorted array. During sorting, one region of the array is an active heap and another region contains values already placed in their final positions. The active region is only partially ordered according to the heap property.

Reasoning About Correctness with Invariants​

The most useful way to reason about heap algorithms is to state the invariants explicitly.

For a min-heap, the ordering invariant is:

Every node has a value no greater than either of its children, whenever those children exist.

For a max-heap, replace no greater with no smaller. The structural invariant for both types is:

The occupied array positions describe a complete binary tree, with the final level filled from left to right.

Insertion preserves structure by appending one value at the next available position. It preserves ordering by moving the new value upward until its parent is correctly ordered.

Extraction preserves structure by moving the final value to the root and deleting the final position. It preserves ordering by moving the replacement downward and choosing the child that should become the parent.

Bottom-up heapify preserves structure because it rearranges values within an existing complete-tree layout. It preserves ordering by processing internal nodes from the bottom toward the root, ensuring that the subtrees below a node are already valid when that node is repaired.

After any operation, two practical validation questions are useful:

1. Do the occupied positions still form a complete binary tree?
2. Does every parent satisfy the min-heap or max-heap comparison with its children?

If both answers are yes, the heap invariant is intact.

When a Heap Is the Right Tool​

A heap is particularly useful when priorities arrive over time and the application repeatedly selects the next item. Task scheduling is a direct example: new tasks can be inserted, and the most urgent task can be removed without sorting the entire collection after every change.

A min-heap is appropriate when smaller comparison values should be selected first. This might mean that priority 1 is more urgent than priority 5, or that an earlier deadline has a smaller timestamp. A max-heap is appropriate when larger scores or values should be selected first.

A heap may not be the simplest choice for every problem. If a collection never changes and the program only needs one minimum, a linear scan may be sufficient. If all values must be ordered once, a sorting algorithm may be more direct. If the application needs arbitrary-key searching and ordered traversal, a binary search tree or another ordered structure may be a better fit.

The heap becomes compelling when the workload is a continuing stream of insertions, peeks, and root extractions.

Practical Takeaways​

A binary heap combines a compact shape with a local ordering rule:

1. A min-heap keeps the smallest value at the root.
2. A max-heap keeps the largest value at the root.
3. The heap property compares parents with children; it does not fully sort the array.
4. Completeness keeps the tree height logarithmic.
5. An array represents the tree using arithmetic parent and child indexes.
6. Insertion appends at the end and uses sift-up.
7. Extraction replaces the root with the last element and uses sift-down.
8. Sift-down must choose the appropriate child: the smaller one for a min-heap and the larger one for a max-heap.
9. Bottom-up heapify builds a heap in O(n) time.
10. Peek is O(1), while insertion and extraction are O(log n).
11. A heap is not a binary search tree and does not provide full sorted order.
12. A priority queue is a natural practical use because it needs efficient access to the next most important item.

For task scheduling, the heap acts as the engine behind the priority queue. New tasks enter at the next available array position and sift toward the location required by their priorities. When the scheduler requests the next task, the root is removed, the final task takes its place, and sift-down restores the invariant. The complete shape and the heap property work together so that the most urgent task remains immediately available without maintaining a fully sorted collection.