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 repeated call delete to remove the smallest value and put it back into the array.