Tag: heap-sort

Heap Sort

Think of building a sandcastle and carefully placing each handful of sand to get the highest, perfect cone. Heap Sort works similarly, arranging data like a pyramid, ensuring the “biggest” (or “smallest”, depending on sorting order) element is always on top.

Process

Heap Sort, as the name suggests, involves creating and manipulating a special data structure called a heap to achieve sorted results. But don’t worry, you don’t need actual shovels and sandcastles for this! Let’s delve into the steps:

1. Heapify the Data: Imagine your data as a pile of pebbles. Heap Sort starts by transforming this pile into a “heap,” which resembles a pyramid-like structure. In this pyramid, the element at the top (the “root”) is always the “biggest” (or “smallest,” depending on the sorting order). Elements are carefully arranged based on their values to maintain this property.

2. Extract the “Biggest” Pebble: Just like picking the biggest pebble for your sandcastle, Heap Sort removes the element at the root (the “biggest” in this case) and places it aside. Remember, the heap property ensures this is indeed the largest element!

3. Maintain the Heap: But removing the top pebble disrupts the heap’s structure. Fear not! Heap Sort employs a clever technique called sifting. It replaces the empty root position with another element from the heap and “sifts” it down until the heap property is restored, ensuring the new root is indeed the “biggest.”

4. Repeat and Conquer: This process of extracting the “biggest” element, sifting, and restoring the heap continues until all elements are processed. By the end, the extracted elements, placed in the order they were removed, form the sorted list!

Pseudo Code

Code
function heapSort(array):
  # Build a max-heap from the input array
  buildMaxHeap(array)

  # Repeatedly extract the root (largest element) and swap it with the last element
  for i in range(len(array) - 1, 0, -1):
    swap(array[0], array[i])
    # Maintain the heap property for the remaining elements
    maxHeapify(array, 0, i)

# Functions for building and maintaining the max-heap

function buildMaxHeap(array):
  # Start from the last non-leaf node and sift downwards
  for i in range(len(array) // 2 - 1, -1, -1):
    maxHeapify(array, i, len(array))

function maxHeapify(array, root, heapSize):
  # Compare the root with its children and swap if necessary
  largest = root
  leftChild = 2 * root + 1
  rightChild = 2 * root + 2

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

  # Swap the root with the largest element if necessary
  if largest != root:
    swap(array[largest], array[root])
    # Recursively heapify the affected sub-tree
    maxHeapify(array, largest, heapSize)

# Swapping function
function swap(a, b):
  temp = a
  a = b
  b = temp
Explanation
  • The heapSort function takes an array as input.
  • The buildMaxHeap function builds a max-heap from the array, ensuring the element at the root is always the largest.
  • The maxHeapify function maintains the heap property by comparing the root element with its children and swapping if necessary.
  • The main loop of heapSort repeatedly extracts the root (largest element) and swaps it with the last element, reducing the heap size by 1 in each iteration.
  • The maxHeapify function is called again after each swap to maintain the heap property for the remaining elements.
  • The swap function simply exchanges the values of two elements.

Implementation

Kotlin

Golang