What is a heap?
- Algorithms course
- Intermediate
- Lesson 9/80
- 4 min
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.
Practice 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])).
Starter code
def is_max_heap(arr):
# Max-heap checkSample 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]))Expected output
True
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 In a max-heap, what is the root?
- The smallest
- The largest element Correct answer
- The median
- Random
Explanation: The largest element
2 Left child
left = 2 * i + ____left = 2 * i + 1Explanation: 1 is right.
3 What is a heap: match the terms
| Term | Meaning |
|---|---|
Max-heap |
Root largest |
Min-heap |
Root smallest |
Left child |
2i+1 |
Parent |
(i-1)//2 |