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 = tempExplanation
- The
heapSortfunction takes an array as input. - The
buildMaxHeapfunction builds a max-heap from the array, ensuring the element at the root is always the largest. - The
maxHeapifyfunction maintains the heap property by comparing the root element with its children and swapping if necessary. - The main loop of
heapSortrepeatedly extracts the root (largest element) and swaps it with the last element, reducing the heap size by 1 in each iteration. - The
maxHeapifyfunction is called again after each swap to maintain the heap property for the remaining elements. - The
swapfunction simply exchanges the values of two elements.