Heap Sort

Definition

Definition

Heap Sort is a comparison-based sorting algorithm that operates by converting the array into a binary heap structure, then repeatedly removing the maximum element from the heap and rebuilding the heap

Explanation

To initiate Heap Sort, first, convert the given array into a max heap, ensuring each parent node is greater than or equal to its children. Then, proceed to repeatedly remove the maximum element, which is the root of the heap, while preserving the heap property through heapify operations. This process continues until the heap is empty, ultimately yielding a sorted array

Guidance

• Build Max Heap
  • Start from the last non-leaf node (index n/2 - 1) to the root (index 0)
  • For each node, compare it with its children and swap if necessary to maintain the heap property
  • Continue this process until the entire array satisfies the heap property
• Heapify
  • Remove the root element (maximum value) from the heap and replace it with the last element of the heap
  • Reduce the size of the heap by one
  • Heapify the remaining elements to maintain the heap property
  • Repeat steps until the heap size becomes 1, resulting in a sorted array

Tips

• ensure you understand the heap data structure and its properties before implementing Heap Sort
• efficiently utilize the heapify process to maintain the heap property after each removal of the maximum element
• be mindful of the array indexing, especially when dealing with parent-child relationships in the heap

Practice

Practice

procedure heapSort(array)
    n := length(array)

    // Build Max Heap
    for i from n/2 - 1 down to 0 do
        heapify(array, n, i)

    // Heapify and Extract Maximum
    for i from n - 1 down to 0 do
        swap(array[0], array[i])   // Move current root to end
        heapify(array, i, 0)       // Heapify the reduced heap

procedure heapify(array, heapSize, index)
    largest := index
    leftChild := 2 * index + 1
    rightChild := 2 * index + 2

    // Find the largest element among root, left child, and right child
    if heapSize > leftChild and array[leftChild] > array[largest] then
        largest := leftChild
    if heapSize > rightChild and array[rightChild] > array[largest] then
        largest := rightChild

    // Swap and continue heapifying if necessary
    if largest != index then
        swap(array[index], array[largest])
        heapify(array, heapSize, largest)

Solution

package main

func heapify(arr []int, n, i int) {
    largest := i
    left := 2*i + 1
    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)
    }
}

func heapSort(arr []int) {
    n := len(arr)

    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }

    for i := n - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    }
}

public class HeapSort {

  public void sort(int arr[]) {
    int n = arr.length;

    for (int i = n / 2 - 1; i >= 0; i--) {
      heapify(arr, n, i);
    }

    for (int i = n - 1; i > 0; i--) {
      int temp = arr[0];
      arr[0] = arr[i];
      arr[i] = temp;

      heapify(arr, i, 0);
    }
  }

  void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int 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) {
      int swap = arr[i];
      arr[i] = arr[largest];
      arr[largest] = swap;

      heapify(arr, n, largest);
    }
  }
}

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);
  }
}

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

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

  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }
  return arr;
}

fun heapify(arr: IntArray, n: Int, i: Int) {
    var largest = i
    val left = 2 * i + 1
    val 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].also { arr[largest] = arr[i] }
        heapify(arr, n, largest)
    }
}

fun heapSort(arr: IntArray) {
    val n = arr.size

    for (i in n / 2 - 1 downTo 0) {
        heapify(arr, n, i)
    }

    for (i in n - 1 downTo 1) {
        arr[0] = arr[i].also { arr[i] = arr[0] }
        heapify(arr, i, 0)
    }
}

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)

def heapSort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

fn heapify(arr: &mut [i32], n: usize, i: usize) {
    let mut largest = i;
    let left = 2 * i + 1;
    let 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.swap(i, largest);
        heapify(arr, n, largest);
    }
}

fn heap_sort(arr: &mut [i32]) {
    let n = arr.len();

    for i in (0..=n / 2).rev() {
        heapify(arr, n, i);
    }

    for i in (1..n).rev() {
        arr.swap(0, i);
        heapify(arr, i, 0);
    }
}

function heapify(arr: number[], n: number, i: number): void {
  let largest: number = i;
  const left: number = 2 * i + 1;
  const right: number = 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);
  }
}

function heapSort(arr: number[]): void {
  const n: number = arr.length;

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

  for (let i: number = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }
}