Implementation

Let’s code heap sort. It has two main phases: build heap, then extract.

Complete Implementation


              function heapSort(arr) {
const n = arr.length;

// Build max heap
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
  heapify(arr, n, i);
}

// Extract elements one by one
for (let i = n - 1; i > 0; i--) {
  // Move root to end
  [arr[0], arr[i]] = [arr[i], arr[0]];
  
  // Heapify reduced heap
  heapify(arr, i, 0);
}

return arr;
}

function heapify(arr, n, i) {
let largest = i;
const left = 2 * i + 1;
const right = 2 * i + 2;

if (left < n && arr[left] > arr[largest]) {
  largest = left;
}

if (right < n && arr[right] > arr[largest]) {
  largest = right;
}

if (largest !== i) {
  [arr[i], arr[largest]] = [arr[largest], arr[i]];
  heapify(arr, n, largest);
}
}


              def heap_sort(arr):
  n = len(arr)
  
  # Build max heap
  for i in range(n // 2 - 1, -1, -1):
      heapify(arr, n, i)
  
  # Extract elements one by one
  for i in range(n - 1, 0, -1):
      # Move root to end
      arr[0], arr[i] = arr[i], arr[0]
      
      # Heapify reduced heap
      heapify(arr, i, 0)
  
  return arr

def heapify(arr, n, i):
  largest = i
  left = 2 * i + 1
  right = 2 * i + 2
  
  if left < n and arr[left] > arr[largest]:
      largest = left
  
  if right < n and arr[right] > arr[largest]:
      largest = right
  
  if largest != i:
      arr[i], arr[largest] = arr[largest], arr[i]
      heapify(arr, n, largest)

Try It Yourself

🟨 JavaScript Heap Sort Implementation

📟 Console Output

Run code to see output...

Code Explanation

Build heap: Convert array to max heap
- Start from last non-leaf node
- Heapify each node bottom-up
Extract and sort: Repeatedly extract maximum
- Swap root with last element
- Reduce heap size
- Heapify root to restore property

Edge Cases

Empty array: Returns empty array
Single element: Already sorted
Already sorted: Still builds heap and extracts

What’s Next?

Now that you can implement it, let’s analyze its performance and complexity.

Progress 71%

Page 5 of 7

← Previous → Next

Sign In