Heapsort

• Heapsort

Heapsort is a sorting algorithm that maintains the O(n lg n) run time (like mergesort) but operates in place (like insertion sort). This sorting algorithm is based on a data structure known as a heap (which is also one way to implement a priority queue).

Heaps
A heap is simply an array viewed as a nearly complete binary tree (meaning a subsequent level is not started until the previous level is completely filled).

Heap values
We define the following values for an array A viewed as a heap
A.length - size of the array
A.heapsize - number of elements in the heap (note A.heapsize ≤ A.length)
height - height of the heap binary tree = Θ(lg n)


Heap operations
A[i] - value at node (element) i
LEFT(i) - index of left child node = 2i
RIGHT(i) - index of right child node = 2i + 1
PARENT(i) - index of parent node = i / 2


Max-heaps
We define a max-heap as a heap that satisfies the property that A[PARENT(i)] ≥ A[i] for all i, i.e. the value of every parent is greater than both children.
Thus for a max-heap, the largest value is stored at the root

Min-heaps
Similarly we define a min-heap as a heap that satisfies the property that A[PARENT(i)] ≤ A[i] for all i, i.e. the value of every parent is less than both children.
Thus for a min-heap, the smallest value is stored at the root.
http://faculty.ycp.edu/~dbabcock/PastCourses/cs360/lecture/lecture07.html