Heap Sort

# Heapsort: A Detailed Explanation with Dry Runs and C Code

Heapsort is a popular and efficient sorting algorithm that uses the data structure known as a binary heap to sort elements in an array. It is a comparison-based sorting algorithm with an average and worst-case time complexity of O(n log n), making it suitable for sorting large datasets. In this article, we will provide a comprehensive explanation of heapsort, accompanied by dry runs and C code examples to help you understand its inner workings.

## Understanding Heaps

Before we dive into the details of heapsort, let's briefly discuss binary heaps, which are the foundation of this algorithm.

### Binary Heaps

A binary heap is a binary tree with two key properties:

1. **Heap Property:** In a max heap, for any given node I, the value of I is greater than or equal to the values of its children. In a min heap, it is the opposite, where the value of I is less than or equal to the values of its children.

2. **Shape Property:** A binary heap is a complete binary tree, which means that all levels of the tree are fully filled except possibly for the last level, which is filled from left to right.

Here's an example of a max heap:

```

/ \

7 5

/ \ / \

6 4 3 2

```

### Heapsort Overview

Heapsort works by using the binary heap data structure to build a heap from the unsorted array and then repeatedly removing the maximum (in a max heap) or minimum (in a min heap) element and placing it at the end of the array. This process continues until the entire array is sorted.

Now, let's walk through the heapsort algorithm with a step-by-step dry run using a max heap and provide C code to implement it.

## Heapsort Dry Run

Let's say we have an unsorted array: `[4, 10, 3, 5, 1]`.

### Step 1: Build a Max Heap

1. Convert the array into a max heap.

```

Initial Array: [4, 10, 3, 5, 1]

Max Heap: [10, 5, 3, 4, 1]

```

### Step 2: Heapify and Swap

2. Swap the root (maximum element) with the last element and reduce the heap size.

```

Max Heap: [1, 5, 3, 4, 10]

```

3. Heapify the root node to maintain the max heap property.

```

Max Heap: [5, 4, 3, 1, 10]

```

### Step 3: Repeat Steps 2 for the Remaining Elements

4. Repeat steps 2 and 3 for the remaining elements.

```

Max Heap: [4, 1, 3, 5, 10]

Max Heap: [3, 1, 4, 5, 10]

Max Heap: [1, 3, 4, 5, 10]

```

### Step 4: Sorted Array

5. The array is now sorted in ascending order.

```

Sorted Array: [1, 3, 4, 5, 10]

```

## Heapsort C Code

Now, let's implement heapsort in C.

```c

#include <stdio.h>

// Function to heapify a subtree rooted at node i.

void heapify(int arr[], int n, int i) {

int largest = i; // Initialize largest as root

int left = 2 * i + 1;

int right = 2 * i + 2;

// If left child is larger than root

if (left < n && arr[left] > arr[largest])

largest = left;

// If right child is larger than largest so far

if (right < n && arr[right] > arr[largest])

largest = right;

// If the largest is not the root

if (largest != i) {

// Swap the root and the largest element

int temp = arr[i];

arr[i] = arr[largest];

arr[largest] = temp;

// Recursively heapify the affected sub-tree

heapify(arr, n, largest);

}

// Main function to perform heapsort

void heapSort(int arr[], int n) {

// Build a max heap

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i);

// Extract elements from the heap one by one

for (int i = n - 1; i > 0; i--) {

// Move the current root to the end

int temp = arr[0];

arr[0] = arr[i];

arr[i] = temp;

// Call max heapify on the reduced heap

heapify(arr, i, 0);

}

int main() {

int arr[] = {4, 10, 3, 5, 1};

int n = sizeof(arr) / sizeof(arr[0]);

printf("Unsorted Array: ");

for (int i = 0; i < n; i++)

printf("%d ", arr[i]);

heapSort(arr, n);

printf("\nSorted Array: ");

for (int i = 0; i < n; i++)

printf("%d ", arr[i]);

return 0;

}

```

This C code demonstrates the heapsort algorithm by sorting an array in ascending order.

## Conclusion

Heapsort is a powerful sorting algorithm that leverages binary heaps to efficiently sort data. We've provided a detailed explanation of the algorithm, accompanied by a step-by-step dry run and C code for implementation. Understanding heapsort and its inner workings can be valuable in various computer science and programming contexts.