Heap Sort

A Heap where value of $i\le$ value of parent. Often used as a Sorting Algorithm

Algorithm

Assumes input is a unsorted array. Uses algorithms:

• build-max-heap : create Max-Heap from unsorted array
• heapify : create Max-Heap, assuming part of array is sorted Algorithm is:

1. Create max heap with build-max-heap
2. Until list is sorted:
   1. Swap item at the start of heap list with item at end
   2. Run heapify to convert back to max-heap form