A node can either have: no children; a left child; two children
Min-heap: a node is always smaller than its children
Complete binary tree: every level, except possibly the last level is completely filled; all vertices in the last level are as far left as possible
Array representation:
Root is at 0 OR 1
Left child at 2i+1 OR 2i
Right child at 2i+2 OR 2i+1
Parent at ⌊(i−1)/2⌋ OR ⌊i/2⌋
Operations
Create:
O(N logN): In the input array, take one element at a time, and call insert() to add it to the new heap
O(N)
Take the input array as a heap array
Go through non-leaf nodes, starting from the bottom:
For each node, do shiftDown(): swap it with its smallest children until the heap property is satisfied i.e. make each node the root of a subtree that is a valid heap
This is O(N) because for a tree, the first node processed only needs to shift max once, next level max twice etc.
Insert
Add the node in the leftmost free space in the last level
Do shiftUp(): repeatedly compare the node with its parent, swap them if parent is greater, until parent is not greater
ExtractMax
Remove root node
Take the rightmost element in the last level, move it to the root
Do shiftDown(): repeatedly swap the element with its smallest child, until it is smaller than both children
UpdateKey
Change the key at index i in the array
Update the value, then call both shiftUp() and shiftDown() on it (only one will actually do anything)
shiftUp() if new value < parent, shiftDown() if new value > than children
O(log n)
Delete
Delete the item at index i in the array
Set the element to be bigger than the root, then call shiftUp()
Call extractMax() to remove the element
This is O(log N)
HeapSort
A sorting algorithm
Create heap in O(N) time
call extractMax() n times, so total O(n log n)
PartialSort
To get the first k elements after sorting
Create heap in O(N) time, call extractMax() k times, so total O(n + k log n)
