Binary Heap

A BST orders values by comparing a node against its left and right subtrees, which supports efficient search for any value. A binary heap instead orders values only between a node and its immediate children, from the root down. This weaker ordering rule gives up general search, but makes finding the smallest or largest element in the tree an O(1) operation. This will become clearer once we look at what the ordering rule actually looks like, so let's see it below.

Binary Heap

Max heap (parent >= children): the maximum sits at the root.

Min heap (parent <= children): the minimum sits at the root.

Why heaps are complete, and array-backed

Because a heap is always a complete binary tree by definition, it can be stored compactly in an array without gaps. The parent and child positions can then be calculated directly from array indices, which is why binary heaps are typically implemented using arrays rather than linked nodes. The same heap, shown both ways: the tree is the conceptual shape, the array is how it is represented in code.

left(i)   = 2i + 1
right(i)  = 2i + 2
parent(i) = (i - 1) / 2      (integer division)

Heap insertion (bubble-up)

New elements always enter at the next available position, keeping the tree complete, then get moved upward until the heap property holds again.

INSERT_MAX_HEAP(A, N, ITEM)
// A is the heap array
// N is the current number of elements in the heap
// ITEM is the value to insert
 
1. A[N] = ITEM
2. i = N
3. N = N + 1
 
4. While i > 0:
       parent = (i - 1) / 2      (integer division)
 
       If A[parent] >= A[i]:
           Break
 
       Swap A[parent] and A[i]
       i = parent
 
5. Return

Example: building a max heap from empty, inserting 70, 50, 80, 40, 90, 85 one at a time. Every step below shows the array and its equivalent tree side by side, since the two are just two views of the same heap.

Insert 70. (Steps 1-3) It is placed at index 0. (Step 4) Since i = 0, the While loop condition is immediately false, so there is no parent to compare against:

Insert 50. (Steps 1-3) It is placed at index 1. (Step 4) i = 1 > 0, so the loop runs: parent = (1-1)/2 = 0, whose value is 70. Since A[parent] = 70 >= A[i] = 50, the If condition holds and the loop breaks: no swap is needed.

Insert 80. (Steps 1-3) It is placed at index 2. (Step 4) i = 2 > 0, so the loop runs: parent = (2-1)/2 = 0, whose value is 70. A[parent] = 70 >= A[i] = 80 is false, so the If does not break, and the loop swaps A[0] and A[2]:

Insert 40. (Steps 1-3) It is placed at index 3. (Step 4) i = 3 > 0, so the loop runs: parent = (3-1)/2 = 1, whose value is 50. Since A[parent] = 50 >= A[i] = 40, the If condition holds and the loop breaks: no swap is needed.

Insert 90. (Steps 1-3) It is placed at index 4. (Step 4, first pass) i = 4 > 0, so the loop runs: parent = (4-1)/2 = 1, whose value is 50. A[parent] = 50 >= A[i] = 90 is false, so the loop swaps A[1] and A[4], then sets i = parent = 1:

(Step 4, second pass) i = 1 > 0, so the loop runs again: parent = (1-1)/2 = 0, whose value is 80. A[parent] = 80 >= A[i] = 90 is false, so the loop swaps A[0] and A[1], then sets i = parent = 0:

(Step 4, third pass) i = 0, so the While condition is false and the loop stops. The value has now reached the root. This process, repeatedly moving a value up while it is larger than its parent, is called up-heap, bubble-up, or heapify-up, named for the way the inserted value rises through the tree level by level, the way a bubble rises through water. It can ripple more than one level, as it just did.

Insert 85. (Steps 1-3) It is placed at the next available slot, index 5. (Step 4, first pass) i = 5 > 0, so the loop runs: parent = (5-1)/2 = 2, whose value is 70. A[parent] = 70 >= A[i] = 85 is false, so the loop swaps A[2] and A[5], then sets i = parent = 2:

(Step 4, second pass) i = 2 > 0, so the loop runs again: parent = (2-1)/2 = 0, whose value is 90. Since A[parent] = 90 >= A[i] = 85, the If condition holds and the loop breaks: the process stops.

Insertion runs in O(log n). The bound follows from the heap's height: a complete tree of n nodes has height O(log n), and bubble-up moves at most one level per comparison.

Heap root deletion (heapify-down)

For a max heap, "deletion" almost always means removing the maximum, which sits at the root.

DELETE_MAX(A, N)
// A is the heap array
// N is the current heap size
 
1. If N == 0:
       PRINT "UNDERFLOW"
       Return
2. MAX = A[0]
3. A[0] = A[N-1]
4. N = N - 1
5. HEAPIFY_DOWN(A, N, 0)
6. Return MAX

HEAPIFY_DOWN(A, N, i)
// A is the heap array
// N is the current heap size
// i is the index to fix
 
1. LEFT = 2i + 1
2. RIGHT = 2i + 2
3. LARGEST = i
4. If LEFT < N AND A[LEFT] > A[LARGEST]:
       LARGEST = LEFT
5. If RIGHT < N AND A[RIGHT] > A[LARGEST]:
       LARGEST = RIGHT
6. If LARGEST == i:
       Return
7. Swap A[i] and A[LARGEST]
8. HEAPIFY_DOWN(A, N, LARGEST)

Example: continuing with the heap built above, delete the max. (DELETE_MAX, Step 1) N = 6 != 0, so there is no underflow. (Step 2) MAX = A[0] = 90:

(DELETE_MAX, Step 3) Move the last element, A[N-1] = 70, to the root: A[0] = 70. (Step 4) Shrink the heap size by one, N = 5, dropping the old last slot:

(DELETE_MAX, Step 5) Call HEAPIFY_DOWN(A, 5, 0). (HEAPIFY_DOWN, Steps 1-3) i = 0: LEFT = 1, RIGHT = 2, LARGEST = 0. (Step 4) A[1] = 80 > A[LARGEST] = 70, so LARGEST = 1. (Step 5) A[2] = 85 > A[LARGEST] = 80, so LARGEST = 2. (Step 6) LARGEST = 2 != i = 0, so the function does not return yet. (Step 7) Swap A[0] and A[2], putting 85 at the root and 70 at index 2:

(Step 8) Call HEAPIFY_DOWN(A, 5, 2). (Steps 1-3) i = 2: LEFT = 5, RIGHT = 6. Since both are >= N = 5, the comparisons on steps 4 and 5 never trigger, so LARGEST stays 2. (Step 6) LARGEST = 2 == i = 2, so the function returns: 70 has no children within the current heap size, and the process stops. The heap property is restored.

Root deletion also runs in O(log n), for the same reason as insertion: heapify-down moves at most one level per comparison, down a tree of height O(log n).

Heapify and building a heap from scratch

Heapify is the general operation of restoring the heap property at one node by comparing it against its children and swapping downward as needed. This is exactly the HEAPIFY_DOWN step used inside DELETE_MAX.

To build a heap from an arbitrary array bottom-up, repeat this heapify step at every internal node, starting from the last one and working up to the root.

BUILD_HEAP(A, N)
// A is the array to build into a heap
// N is the number of elements in A
 
1. i = floor(N/2) - 1   // last internal node, zero-based
2. While i >= 0:
       root = i
 
       While True:   // heapify-down at root
           LEFT = 2*root + 1
           RIGHT = 2*root + 2
           LARGEST = root
 
           If LEFT < N AND A[LEFT] > A[LARGEST]:
               LARGEST = LEFT
 
           If RIGHT < N AND A[RIGHT] > A[LARGEST]:
               LARGEST = RIGHT
 
           If LARGEST == root:
               Break
 
           Swap A[root] and A[LARGEST]
           root = LARGEST
 
       i = i - 1
3. Return

Working from the bottom means every subtree a node heapifies into is already a valid heap by the time that node is processed, so each heapify call only needs to fix one level.

Example: build a max heap from the unsorted array [4, 10, 3, 5, 1, 8].

(Step 1) N = 6, so the last internal node is i = floor(6/2) - 1 = 2.

(Step 2, i = 2) root = 2, value 3. LEFT = 5 (value 8), RIGHT = 6 (out of range, RIGHT >= N). Since A[5] = 8 > A[root] = 3, LARGEST = 5, which is not equal to root, so swap A[2] and A[5]:

root becomes 5. Its children would be at indices 11 and 12, both >= N, so LARGEST stays 5 and the inner loop stops: node 3 (now at index 5) is heapified.

(Step 2, i = 1) root = 1, value 10. LEFT = 3 (value 5), RIGHT = 4 (value 1). Neither child is greater than 10, so LARGEST stays 1 and the inner loop stops immediately: no swap is needed.

(Step 2, i = 0) root = 0, value 4. LEFT = 1 (value 10), RIGHT = 2 (value 8). A[1] = 10 > A[root] = 4, so LARGEST = 1; A[2] = 8 is not greater than A[LARGEST] = 10, so LARGEST stays 1, which is not equal to root, so swap A[0] and A[1]:

root becomes 1, value 4. LEFT = 3 (value 5), RIGHT = 4 (value 1). A[3] = 5 > A[root] = 4, so LARGEST = 3; A[4] = 1 is not greater than A[LARGEST] = 5, so LARGEST stays 3, which is not equal to root, so swap A[1] and A[3]:

root becomes 3. Its children would be at indices 7 and 8, both >= N, so LARGEST stays 3 and the inner loop stops. i is now -1, so the outer loop in Step 2 ends: every parent is greater than or equal to its children, so this is a valid max heap.

Building a heap this way runs in O(n), compared to O(n log n) for inserting the same n elements one at a time.

Time complexity summary

Quick recall

• Max heap: parent >= children, max at root. Min heap: parent <= children, min at root.
• No left-right ordering rule like a BST, only parent-vs-child, at every level.
• Always a complete tree, so always array-backed: left = 2i+1, right = 2i+2, parent = (i-1)/2.
• Insertion: place at the next open slot, bubble up while larger (max heap) than its parent. O(log n).
• Root deletion: move the last element to the root, heapify down by swapping with the larger child. O(log n).
• Bottom-up heap construction from an unordered array is O(n), faster than n individual insertions (O(n log n)).