Heap Sort

Use a Binary Heap to sort an array

Out of Place

• How
  1. Insert n items into heap ($O(n\log n)$ + extra space)
  2. Extract n items from heap and place in array ($O(n\log n)$)
• Performance: $O(n\log n)$

In Place

• How
  1. Sort array in place ($O(n)$)
  2. Extract n items from heap and place in array ($O(n\log n)$)

for (int i = size / 2; i>= 0; i--)
	heapifyDown(i)

• Performance: $O(n\log n)$