Max Heap
- Tags
- comp-sci
A heap with the max-heap property:
For every node \( n \) (other than the root) the value of that node is no-greater than its parent. \[ \forall i \in N A[\text{Parent}(n)] \geq A[n] \]
From this it follows that the root-node of a max-heap is the largest element of the heap.
def max_heapify(arr, i):
l = left(i)
r = right(i)
# Pick the larger of the current node
# or left and right sub-node.
largest = i
if l <= len(arr) and arr[l] > a[i]:
largest = l
if r <= len(arr) and arr[r] > a[largest]:
largest = r
if largest != i:
swap(arr, i, largest)
max_heapify(arr, largest)Code Snippet 1:
An algorithm to recursively assert the max-heap property on a sub-tree. It compares the current node with its left and right sub-tree, when the max-heap property isn't satisfied it swaps the largest of the sub-nodes with the current node and then max-heapifys the swapped sub-tree. alg:max_heapify
To [see page 12, build] a max-heap we apply alg:max_heapify to the tree bottom-up. Because max-heapify assumes the left and right sub-trees are valid heaps we can't do so top-down. This approach can be seen in alg:build_max_heap. We loop from \( \lfloor \frac{n}{2} \rfloor \) down because the values from \( \lfloor \frac{n}{2} \rfloor + 1, \ldots, n \) are all leaf nodes and leaves are already heaps (trivially).
def build_max_heap(arr):
for i in reversed(range(len(arr) // 2)):
max_heapify(arr, i)Code Snippet 2:
An algorithm to build a max-heap from a regular array (see algorithm correctness see page 13, [here]). alg:build_max_heap