Back to list

Heap Sort

Comparison-based sorting technique based on Binary Heap data structure.

Initial ArrayHeap Size: 7
Binary Heap View
60
0
95
1
19
2
48
3
36
4
60
5
75
6
60
0
95
1
19
2
48
3
36
4
60
5
75
6
Array Memory View
Speed
Comp
0
Swaps
0
Array Controls

Time Complexity

All Cases
O(n log n)

Heap Sort guarantees O(n log n) because building the heap is O(n) and extracting n elements takes O(log n) each.

Space Complexity

Auxiliary SpaceO(1)

In-place sorting algorithm. No extra array needed.

Algorithm Details

Heap Sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for the remaining elements.

How it works

  1. Build a max heap from the input data.
  2. At this point, the largest item is stored at the root of the heap.
  3. Swap it with the last item of the heap followed by reducing the size of heap by 1.
  4. Heapify the root of the tree.
  5. Repeat steps 3-4 while the size of the heap is greater than 1.

Complexity

  • Time Complexity: O(n log n)
  • Space Complexity: O(1)