Heapsort

Introduction:

In the world of computer science and programming, sorting algorithms play a crucial role in efficiently organizing data. One such algorithm is Heapsort, which can be seen as an improved version of the selection sort algorithm. By leveraging a heap data structure, Heapsort divides data into sorted and unsorted regions, iteratively extracting the largest element and moving it to the sorted region. In this article, we will delve into the inner workings of Heapsort and explore its implementation in C#, JavaScript, Python, and PHP.

Understanding Heapsort:

Heapsort is a comparison-based sorting algorithm that operates by dividing the input array into two regions: a sorted region and an unsorted region. Initially, the entire array is considered unsorted. The algorithm then builds a max heap, a complete binary tree where each parent node is greater than or equal to its children.
To build the max heap, Heapsort uses a heapify operation. This operation ensures that every parent node is greater than or equal to its children. Once the max heap is constructed, the largest element, located at the root of the heap, is swapped with the last element in the unsorted region. This step effectively moves the largest element to the sorted region.
The algorithm then shrinks the unsorted region by one element and repeats the heapify operation on the reduced heap. This process continues until the entire array is sorted.

Links

Code Examples

C#
using System;

public class Heapsort
{
    public static void Sort(int[] arr)
    {
        int n = arr.Length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--)
            Heapify(arr, n, i);

        // Extract elements from the heap
        for (int i = n - 1; i > 0; i--)
        {
            // Swap root with the last element
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Heapify the reduced heap
            Heapify(arr, i, 0);
        }
    }

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

    // Example usage
    public static void Main()
    {
        int[] arr = { 12, 11, 13, 5, 6, 7 };
        Sort(arr);

        Console.WriteLine("Sorted array:");
        foreach (var element in arr)
            Console.Write(element + " ");
    }
}

JavaScript
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) {
        const temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        heapify(arr, n, largest);
    }
}

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 from the heap
    for (let i = n - 1; i > 0; i--) {
        // Swap root with the last element
        const temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // Heapify the reduced heap
        heapify(arr, i, 0);
    }

    return arr;
}

// Example usage
const arr = [12, 11, 13, 5, 6, 7];
const sortedarray = heapsort(arr);
console.log("Sorted array:", sortedArray.join(" "));

Python
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)

    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Extract elements from the heap
    for i in range(n - 1, 0, -1):
        # Swap root with the last element
        arr[0], arr[i] = arr[i], arr[0]

        # Heapify the reduced heap
        heapify(arr, i, 0)

    return arr

# Example usage
arr = [12, 11, 13, 5, 6, 7]
sorted_array = heapsort(arr)
print("Sorted array:", end=" ")
print(*sorted_array)

PHP
function heapify(&$arr, $n, $i)
{
    $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) {
        $temp = $arr[$i];
        $arr[$i] = $arr[$largest];
        $arr[$largest] = $temp;

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

function heapsort(&$arr)
{
    $n = count($arr);

    // Build max heap
    for ($i = (int)($n / 2) - 1; $i >= 0; $i--)
        heapify($arr, $n, $i);

    // Extract elements from the heap
    for ($i = $n - 1; $i > 0; $i--) {
        // Swap root with the last element
        $temp = $arr[0];
        $arr[0] = $arr[$i];
        $arr[$i] = $temp;

        // Heapify the reduced heap
        heapify($arr, $i, 0);
    }
}

// Example usage
$arr = [12, 11, 13, 5, 6, 7];
heapsort($arr);

echo "Sorted array: ";
foreach ($arr as $element)
    echo $element . " ";

Conclusion