SimuVedaAlgorithms Lab Open in the lab

Sorting / Advanced

Heap Sort Visualizer

Turn the array into a max-heap so the biggest value sits at index 0. Swap it to the end, shrink the heap by one, and repair it. Repeat.

Start the Heap Sort simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n log n)
Average timeO(n log n)
Worst timeO(n log n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Step 1: build a max-heap, starting from the last parent. [5, 1, 4, 2, 8]
  2. Repair the heap at index 1 (1).
  3. Compare the left child 2 with 1.
  4. Compare the right child 8 with 2.
  5. 8 is bigger, so it moves up. Keep repairing below. [5, 8, 4, 2, 1]
  6. Repair the heap at index 4 (1).
  7. 1 is at least as big as its children. This part is a valid heap.
  8. Repair the heap at index 0 (5).
  9. Compare the left child 8 with 5.
  10. Compare the right child 4 with 8.
  11. 8 is bigger, so it moves up. Keep repairing below. [8, 5, 4, 2, 1]
  12. Repair the heap at index 1 (5).
  13. Compare the left child 2 with 5.
  14. Compare the right child 1 with 5.
  15. 5 is at least as big as its children. This part is a valid heap.
  16. The heap is built. The largest value, 8, is at index 0.
  17. Swap the max 8 to index 4. It is in its final place. [1, 5, 4, 2, 8]
  18. Repair the heap at index 0 (1).
  19. Compare the left child 5 with 1.
  20. Compare the right child 4 with 5.
  21. … 19 more steps …
  22. Swap the max 2 to index 1. It is in its final place. [1, 2, 4, 5, 8]
  23. Repair the heap at index 0 (1).
  24. 1 is at least as big as its children. This part is a valid heap.
  25. Sorted. 12 comparisons and 10 swaps.

Try it with your own input →

Heap sort in Java, Python, C++, C and JavaScript

void heapSort(int[] a) {
  int n = a.length;
  for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i);
  for (int end = n - 1; end > 0; end--) {
    swap(a, 0, end);
    heapify(a, end, 0);
  }
}
void heapify(int[] a, int n, int i) {
  int big = i, l = 2 * i + 1, r = 2 * i + 2;
  if (l < n && a[l] > a[big]) big = l;
  if (r < n && a[r] > a[big]) big = r;
  if (big != i) {
    swap(a, i, big);
    heapify(a, n, big);
  }
}
def heap_sort(a):
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):
        heapify(a, n, i)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        heapify(a, end, 0)

def heapify(a, n, i):
    big, l, r = i, 2 * i + 1, 2 * i + 2
    if l < n and a[l] > a[big]:
        big = l
    if r < n and a[r] > a[big]:
        big = r
    if big != i:
        a[i], a[big] = a[big], a[i]
        heapify(a, n, big)
void heapify(vector<int>& a, int n, int i);

void heapSort(vector<int>& a) {
  int n = a.size();
  for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i);
  for (int end = n - 1; end > 0; end--) {
    swap(a[0], a[end]);
    heapify(a, end, 0);
  }
}
void heapify(vector<int>& a, int n, int i) {
  int big = i, l = 2 * i + 1, r = 2 * i + 2;
  if (l < n && a[l] > a[big]) big = l;
  if (r < n && a[r] > a[big]) big = r;
  if (big != i) {
    swap(a[i], a[big]);
    heapify(a, n, big);
  }
}
void heapify(int a[], int n, int i);

void heapSort(int a[], int n) {
  for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i);
  for (int end = n - 1; end > 0; end--) {
    int t = a[0]; a[0] = a[end]; a[end] = t;
    heapify(a, end, 0);
  }
}
void heapify(int a[], int n, int i) {
  int big = i, l = 2 * i + 1, r = 2 * i + 2;
  if (l < n && a[l] > a[big]) big = l;
  if (r < n && a[r] > a[big]) big = r;
  if (big != i) {
    int t = a[i]; a[i] = a[big]; a[big] = t;
    heapify(a, n, big);
  }
}
function heapSort(a) {
  const n = a.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(a, n, i);
  for (let end = n - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]];
    heapify(a, end, 0);
  }
}
function heapify(a, n, i) {
  let big = i;
  const l = 2 * i + 1, r = 2 * i + 2;
  if (l < n && a[l] > a[big]) big = l;
  if (r < n && a[r] > a[big]) big = r;
  if (big !== i) {
    [a[i], a[big]] = [a[big], a[i]];
    heapify(a, n, big);
  }
}

In an interview

In an array heap the children of index i are 2i + 1 and 2i + 2, and the parent is (i − 1) / 2. Know this by heart.

More sorting