Heap and Heap Sort

Heap Sort is a sort based on the building and destroying of a binary heap. The binary heap is an implementation of a Priority Queue. Normally, when you have a queue, the first value in is the first value out. However with a priority Queue the value that comes out of the queue next depends on the priority of that value.

Basic operations on the binary Heap include:

• insert - add an item to the binary heap
• delete - removes the item with the highest priority in the binary heap.

The idea for the Heap sort is this: put every value in the array into the binary heap using its value as the priority, then repeatedly call delete to remove the smallest/largest value and put it back into the array.