Constructing a Binary Heap
A binary heap can be constructed in O ( n ) time
-
Create an array and store the n elements in arbitrary order
-
"Heapify" the array
start at vertex i = |_ n / 2_|, the left most vertex in the the
next to last level
for each vertex from i up to the root, shift down
Example
Construct a binary heap from the values
{18, 2, 13, 10, 15, 3, 7, 16, 8}