> For the complete documentation index, see [llms.txt](https://cs-notes.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs-notes.gitbook.io/algorithm-notes/outline/overview-2/heap-sort.md).

# Heap Sort

Based on a typical [heap](/algorithm-notes/outline/overview-4/heap.md) data structure, Heap Sort is an [in-place, not stable comparison-baed sorting](broken://pages/-LQpLuf2ZYeNKgv4W400) algorithm and can be thought of as a improved version of [selection sort](/algorithm-notes/outline/overview-2/selection-sort.md) algorithm.

## Fundamental Ideas

Initially, a [BUILD-MAX-HEAP](/algorithm-notes/outline/overview-4/heap.md) is called upon a randomly distributed inputs to setup a [max-heap](/algorithm-notes/outline/overview-4/heap.md). Now that the topmost root key must be the largest among the heap, extract that key to a sorted array and restore the heap property using [MAX-HEAPIFY](/algorithm-notes/outline/overview-4/heap.md) operation. Repeat the procedures of extraction and adjustment till the heap is empty, the sorted array is formed.

In each heap restoration process, instead of [selection sort](/algorithm-notes/outline/overview-2/selection-sort.md) method of locating the maximum or minimum key within the inputs in linear time, Heap Sort uses [MAX-HEAPIFY](/algorithm-notes/outline/overview-4/heap.md) operation to reduce time complexity to logarithmic bound.

## Pseudocode

The following code transforms a randomly distributed array into an ascending entry array.

```
HEAP_SORT(A)
  BUILD_MAX_HEAP(A)
  for i = length(A) to 2
    swap A[1] and A[i]
    A.heap_size = A.heap_size - 1
    MAX_HEAPIFY(A, i)
```

## Algorithm Analysis

Given a n-size inputs, there is a Ο(n) estimate on [BUILD\_MAX\_HEAP](/algorithm-notes/outline/overview-4/heap.md) operation; And for each input entry, a [MAX\_HEAPIFY](/algorithm-notes/outline/overview-4/heap.md) is expected to perform and thus costs Ο(n ⋅ log(n)) in total.

Since the [Heap Sort](/algorithm-notes/outline/overview-2/heap-sort.md#heap-sort) is also a [comparison-based sorting](broken://pages/-LQpLuf2ZYeNKgv4W400) that has proven with a lower bound Ω(n ⋅ log(n)), the more tighter bound for Heap Sort will be Θ(n ⋅ log(n)).

## Additional References

1. Why is Heap Sort used? <https://www.quora.com/Why-is-heap-sort-used>