Min and max heap

Difference between min-heap and max-heap.

Min and max heap

In a min-heap each node is smaller than or equal to its children; the root is the smallest. In a max-heap each node is larger than or equal to its children; the root is the largest.

A heap is stored as a complete binary tree in an array. Parent (i-1)//2, left child 2i+1, right child 2i+2.

Min-heap is used to get the smallest element quickly in a priority queue; max-heap for the largest.

Parent-child

In the array representation, the parent of node at index i is (i-1)//2, left child 2i+1, right child 2i+2.

The root is arr[0] and has no parent. Leaves are in the second half of the array (i ≥ n//2).

These formulas give parent-child relations in O(1); no pointers needed.

Exercise Check min-heap

Write is_min_heap(arr). Each child must be >= parent. Print True with print(is_min_heap([1, 3, 2, 5, 4])).

Show example solution

def is_min_heap(arr):
    # Check min-heap
    for i in range(1, len(arr)):
        if arr[(i - 1) // 2] > arr[i]:
            return False
    return True
print(is_min_heap([1, 3, 2, 5, 4]))

Test yourself

What is the root in a min-heap?
- The largest
- The smallest element
- The median
- Random
Show answer

The smallest element — The smallest element

Parent

parent = (i - 1) // ____

Show answer

parent = (i - 1) // 2

Min and max heap: match the terms

Min-heap

Root smallest
Max-heap

Root largest
Parent

(i-1)//2
Left child

2i+1

Next lesson: Insert

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies