Heap
A heap is a type of binary tree where all elements must satisfy the heap property
Not to be confused with "the heap" or freestore in C/C++. It's different.
The heap property states that the child nodes must be less than their parent
Operations
See Big O
insert:- Insert a value at the end, and then "heapify" (i.e fix the heap so it satisfies the heap property) by sifting up
- Compare with parent, swap if child is bigger, keep going until no longer necessary
Suppose we wish to insert 72 into the following heap:
We add 72 to the "next slot", which breaks the heap property, so we must sift-up to fix it:
deletethe largest item:- Move the bottommost node to the top, and then "heapity" by sifting down
- Compare with children, swap if a child is bigger, keep going until no longer necessary. If both children are larger, swap with the largest one.
Suppose we wish to remove the top node (420) from the heap
We remove the node, and move the bottommost node (9) to in its place. Now the heap property is broken, and we must sift down to fix it:
General Implementation
A heap is usually implemented with an array (dynamic). The left child is always at index 2 * i + 1, and the right child is always at index 2 * i + 2, and the parent is always at index (i - 1) / 2
The heap above would look like:
[420, 69, 100, 32, 53, 30, 1, 9, 12, 31]