Heapsort is a comparison-based sorting algorithm with $O(n log n)$ running time.

It sorts in place, using only constant extra space.

Heapsort combines:

• the good time complexity of merge sort
• the space efficiency of insertion sort

It is based on a data structure called a heap, which is also widely used to implement priority queues.

6.1 Heaps

A binary heap is an array that represents a nearly complete binary tree:

• All levels are fully filled except possibly the last
• The last level is filled from left to right
• Only elements A[1 .. heap-size] belong to the heap

The root of the heap is at A[1] or A[0] based on your indexing.

Array Representation

For a node at index i:

• PARENT(i) = floor(i / 2) or shift i in binary once to right
• LEFT(i) = 2i or shift i in binary once to left
• RIGHT(i) = 2i + 1 or shift i in binary once to left and plus 1 bit

These operations are very fast and often implemented inline.