Heap Sort Basics

Heap Sort Basics

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It is an in-place sorting algorithm, meaning it does not require any extra space for a new array to hold the sorted elements. Heap Sort is an efficient sorting algorithm with a time complexity of O(n log n), where n is the number of elements in the input array.

What is a Heap?

A heap is a complete binary tree with two important properties:

1. Shape Property: A heap is a complete binary tree, meaning every level of the tree is completely filled except possibly for the last level, which is filled from left to right.

2. Heap Property: The key value of each node must satisfy the heap property:

   • Max-Heap: In a max-heap, the key value of each node must be greater than or equal to the key values of its children. This ensures that the maximum element is always at the root of the tree.
   • Min-Heap: In a min-heap, the key value of each node must be smaller than or equal to the key values of its children, ensuring that the minimum element is at the root of the tree.

For Heap Sort, we typically use a max-heap, as the largest element will be placed at the root, which makes it easy to extract the largest element and move it to its correct position in the sorted array.

How Heap Sort Works

Heap Sort works by first building a max-heap from the input array, then repeatedly extracting the largest element (the root of the heap) and placing it at the end of the array. After each extraction, the heap property is restored.

Steps of Heap Sort

1. Build a Max-Heap: Convert the input array into a max-heap. This is done by starting from the last non-leaf node and applying the heapify process to ensure that the max-heap property is maintained.

2. Extract Elements from the Heap: The root element (which is the maximum in a max-heap) is swapped with the last element in the heap. The heap size is then reduced by one, and the heap property is restored by applying the heapify process.

3. Repeat Extraction: Repeat the extraction and heapify process until the heap is empty, at which point the array is fully sorted.

Heapify Process

The heapify process is the key operation that ensures the heap property is maintained. It is a recursive function that moves down the tree, comparing a node with its children and swapping them if necessary to maintain the heap property. If a swap occurs, heapify is called again on the subtree where the swap happened.

Heap Sort Algorithm

Let’s break down the Heap Sort algorithm with an example.

Pseudocode for Heap Sort

// Function to perform heapify
void heapify(int arr[], int n, int i) {
    int largest = i;        // Initialize largest as root
    int left = 2 * i + 1;   // left child
    int right = 2 * i + 2;  // right child

    // 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 largest is not root
    if (largest != i) {
        swap(arr[i], arr[largest]);

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

// Main function to implement Heap Sort
void heapSort(int arr[], int n) {
    // Step 1: Build a max-heap
    // Start from the last non-leaf node and apply heapify
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Step 2: Extract elements one by one
    for (int i = n - 1; i >= 1; i--) {
        // Move current root to the end
        swap(arr[0], arr[i]);

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

Example of Heap Sort

Consider the array:

arr = [4, 10, 3, 5, 1]

Step 1: Build a Max-Heap

We start by building a max-heap. The last non-leaf node is at index n/2 - 1, which is 1 (for an array of length 5).

• First heapify call: We start with the root 4 at index 0 and apply heapify.

  The largest element among 4, 10, and 3 (children of root 4) is 10. So, we swap 4 with 10:

  arr = [10, 4, 3, 5, 1]
  

  Now we heapify the subtree rooted at index 1.

• Second heapify call: Now, the subtree rooted at 4 (index 1). Among 4, 5, and 1, the largest element is 5. So, we swap 4 with 5:

  arr = [10, 5, 3, 4, 1]
  

  After heapifying both subtrees, the array becomes a max-heap.

Step 2: Extract Elements from the Heap

Now, we extract the maximum element (the root) and swap it with the last element. We then heapify the reduced heap.

• Swap the root 10 with the last element 1:

  arr = [1, 5, 3, 4, 10]
  

  The heap size is reduced to 4, and we call heapify on the root.

  After applying heapify, the array becomes:

  arr = [5, 4, 3, 1, 10]
  

• Swap the root 5 with the last element 1:

  arr = [1, 4, 3, 5, 10]
  

  After heapifying, the array becomes:

  arr = [4, 1, 3, 5, 10]
  

• Swap the root 4 with the last element 1:

  arr = [1, 4, 3, 5, 10]
  

After further heapifying, the array will finally be sorted as:

arr = [1, 3, 4, 5, 10]

Time Complexity of Heap Sort

1. Building the Heap: Building the max-heap requires O(n) time because we perform a heapify operation on each non-leaf node, and the total number of operations for building the heap is proportional to n.

2. Extracting Elements: Each extraction of the root element takes O(log n) time because after extracting the root, we need to restore the heap property by performing a heapify operation, which takes O(log n) time. Since there are n extractions, this step takes O(n log n) time.

Thus, the overall time complexity of Heap Sort is:

• O(n log n) in the worst, best, and average cases.

Space Complexity of Heap Sort

Heap Sort is an in-place sorting algorithm, which means it does not require any extra space (other than the space used by the input array). The space complexity is:

• O(1) auxiliary space, since we only use a constant amount of extra space for the heapify process.

Advantages of Heap Sort

1. Time Complexity: Heap Sort guarantees O(n log n) time complexity, which is better than algorithms like Bubble Sort or Insertion Sort, which have O(n²) time complexity.

2. In-Place Sorting: Heap Sort is an in-place sorting algorithm, meaning it doesn't require extra space for another array (other than the input array itself).

3. Efficient for Large Data: Since Heap Sort has a guaranteed time complexity of O(n log n), it is a good option for sorting large datasets.

Disadvantages of Heap Sort

1. Not Stable: Heap Sort is not a stable sorting algorithm, meaning that it does not preserve the relative order of equal elements. For example, if two elements are equal, their order in the sorted array might not be the same as in the input array.

2. Not Adaptive: Heap Sort does not take advantage of existing order in the array. Unlike algorithms like Quick Sort or Merge Sort, which can be optimized for nearly sorted data, Heap Sort always runs in O(n log n) time.

Conclusion

Heap Sort is an efficient, comparison-based sorting algorithm that works by using a max-heap to repeatedly extract the largest element and place it in the correct position. With a time complexity of O(n log n) and O(1) space complexity, Heap Sort is well-suited for large datasets where