Heapsort

Performance Profile

• Running time of O(n lg n)
• Sorts in place

Heap Array

• As complete as possible binary tree
• Root node at A[0]
• Parent of node i = floor[i / 2]
• Left child of node i = 2i
• Right child of node i = 2i + 1
• Max Heap = Root node is maximum value
• Min Heap = Root node is minimum value
• Height of binary tree = Theta(lg n)

Sub-routines - Max-Heapify

• Maintains sorted state when item is added/removed
• Running time of O(lg n)
• Recurrence relationship: T(n) <= T(2n/3) + Theta(1)

Sub-routines - Build-Max-Heap

• Produces max-heap from an unordered collection
• Builds the heap by iteratively applying max-heapify from the bottom up
• Leaf nodes are sub-tree of height 1 so max-heapify need not be applied
• Running time of O(n)