HeapSort

6.1 Heaps

The (binary) heap data structure is an array object. An array A that represents a heap is an object with two attributes: A.length, which (as usual) gives the number of elements in the array, and A.heap-size, which represents how many elements in the heap are stored within array A. That is, although A[1..A.length] may contain numbers, only the elements in A[1..A.heap-size], where 0 $\leqslant$ A.heap-size $\leqslant$ A.length, are valid elements of the heap. The root of the tree is A[1], and given the index i of a node, we can easily compute the indices of its parent, left child, and right child: 

 PARENT(i)

 return [i/2]

LEFT(i)

 return 2i

RIGHT(i)

 return 2i + 1

6.2 Maintaining the heap property

MAX-HEAPIFY(A, i)

 l = LEFT(i)
 r = RIGHT (i)
 if l <= A.heap-size and A[l] > A[i]
     largest = l
 else
     largest = i
 if r <= A.heap-size and A[r] > A[largest]
     largest = r
 if largest != i
     exchange A[i] with A[largest]
     MAX-HEAPIFY(A, largest)

6.3 Building a heap

We can use the procedure MAX-HEAPIFY in a bottom-up manner to convert an array A[1..n], where n = A.length, into a max-heap.
BUILD-MAX-HEAP(A)

 A.heap-size = A.length
 for i = A.length/2 downto 1
     MAX-HEAPIFY(A, i)

6.4 The heapsort algorithm

HEAPSORT(A)

 BUILD-MAX-HEAP(A)
 for i = A.length downto 2
     exchange A[1] with A[i]
     A.heap-size = A.heap-size - 1
     MAX-HEAPIFY(A, 1)

6.5 Priority queues

HEAP-MAXIMUM(A)

 return A[1]

HEAP-EXTRACT-MAX(A)

 if A.heap-size < 1
     error "heap underflow"
 max = A[1]
 A[1] = A[A.heap-size]
 A.heap-size = A.heap-size -1
 MAX-HEAPIFY(A, 1)
 return max

MAX-INCREASE-INSERT(A, key)

 if key < A[i]
     error "new key is smaller than current key"
 A[i] = key
 while i > 1 and A[PARENT(i)] < A[i]
     exchange A[i] with A[PARENT(i)]
     i = PARENT(i)

MAX-HEAP-INSERT(A, key)

 A.heap-size = A.heap-size + 1
 A[A.heap-size] = negative_infinity
 HEAP-INCREASE-KEY(A, A.heap-size, key)