3.9.7 Heap Sort

Knowledge Base > Algorithm > Sorting

Overview

Heap Sort has slower average running time of O(n ⋅ lg n) than Quick Sort, but it has the advantage of O(n ⋅ lg n) running time at worst case. Heap Sort sorts in place, which means no other memory space is required.

Algorithm

Pseudocode

Heap-Sort(A)

1 Build-Heap(A) 2 for i ← length[A] downto 2 3 do swap A[1] ↔ A[i] 4       heap-size[A] ← heap-size[A] - 1 5       Heapify(A,1)

The idea of Heap Sort is to simply keeping the max element at the root, and exchange it with the last element of array. Next, we ’discard’ the last element by subtract the length of heap-size by one, and we observe the heap of A[0…n - 1]. Eventually, every node, except the first node, is discarded, and thus, the elements of the array are sorted.

Time Complexity

The sorting operations takes O(n ⋅ lg n), since we call Heapify(), which runs at O(lg n)) for (n-1) times.

Build-Heap procedure handles data movement of the heap array, which produce O(n ⋅ lg n) of comparisons and swaps.

Space Complexity

Heap sort always work on the heap array. Thus, the space complexity is O(1).

Stability

Heap sort is NOT stable.

Source Code

• Heap Sort (C)
  
  
  

Related Topics

• Tree
• Heap