What is a heap?

A complete binary tree stored as an array.

What is a heap?

A heap is a complete binary tree stored as an array and satisfying the heap property. In a max-heap each node is greater than or equal to its children; in a min-heap, less than or equal.

Stored as an array: root at arr[0], a node's children at 2i+1 and 2i+2, parent at (i-1)//2.

Heap sort first builds a max-heap, then moves the root to the end and re-heapifies. This yields a sorted array.

Array representation

Because the heap is a complete binary tree, it can be stored in an array without gaps, level by level, left to right.

For index i: left child 2i+1, right child 2i+2, parent (i-1)//2. These formulas give parent-child relations in O(1).

No pointers are used; this makes the heap memory-efficient.

Exercise Check heap property

Write is_max_heap(arr). Check whether the array is a max-heap. Print True with print(is_max_heap([9, 5, 8, 1, 3])).

Show example solution

def is_max_heap(arr):
    # Max-heap check
    for i in range(1, len(arr)):
        if arr[(i - 1) // 2] < arr[i]:
            return False
    return True
print(is_max_heap([9, 5, 8, 1, 3]))

Test yourself

In a max-heap, what is the root?
- The smallest
- The largest element
- The median
- Random
Show answer

The largest element — The largest element
Left child
```
left = 2 * i + ____
```
Show answer
```
left = 2 * i + 1
```
What is a heap: match the terms

Max-heap

Root largest
Min-heap

Root smallest
Left child

2i+1
Parent

(i-1)//2

Next lesson: Heapify

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies