Root is the smallest for a min-heap and largest element for a max-heap
Only the root can be removed
Heaps can have duplicate nodes
Representation
Infrequent: Linked nodes (like a tree normally is)
Frequent: Array (because it is a complete tree there is not much wasted memory)
For a node at position p
Left child: 2p+1
Right child: 2p+2
A node at position c can find its parent using ⌊(c−1)/2⌋
(for 0 indexed arrays)
Operations
Insertion
Action:
insert new item in the position in the bottom of the heap
while new item is not at the root and new item is smaller than its parent (called: heapify up)
swap the new item with its parent moving the new item up the heap
How:
insert the new element at the end of the array and set child to arr.size() - 1
Set the parent to (child - 1) / 2
while parent >= 0 and arr[parent] > arr[child]
Swap arr[parent] and arr[child]
Set child equal to parent
Set parent equal to (child - 1) / 2
Extract Min
Replace the top with the most right element on the right node
While that moved node is greater than it’s children (for min heap) (called: heapify down)
Swap with smallest child
Heapify
Operation that rearranges a heap to maintain the heap property
3 Variants
Heapify Up
Done after insert
Corrects the path between the inserted node and root
Heapify Down
Done after delete
Moves the last element to root
Corrects a path from the new root to a leaf
Heapify
Turns any tree/array into a heap
void heapifyUp(int index) {
}
void heapifyDown(int index) {
1. if index is a leaf -> stop
2. Find the smallest child of node at index
3. Swap node at index with smallest_child_index
4. heapifyDown(smallest_child_index)
}
void heapify() {
}