Heap Sort Algorithm Analysis

Heap Sort Algorithm Analysis

Heap Sort is a comparison-based sorting algorithm that leverages a binary heap data structure to sort elements efficiently. The algorithm works by first building a heap (either a max-heap or a min-heap) from the input data, and then repeatedly extracting the maximum (for max-heap) or minimum (for min-heap) element from the heap, rebuilding the heap after each extraction.

Heap Sort Algorithm Steps

1. Build a Max-Heap from the input array:

   • Rearrange the elements to satisfy the heap property (for a max-heap, each parent node is greater than or equal to its children).
   • This step ensures that the root of the heap is the maximum element.

2. Swap the root (maximum element) with the last element in the heap.

   • After swapping, the maximum element is placed at its correct position in the sorted array.

3. Reduce the size of the heap by 1 (exclude the last element, which is now sorted).

   • Heapify the root of the heap to restore the heap property.

4. Repeat the process until the heap size becomes 1. By then, the array will be sorted in ascending order.

Detailed Explanation of Heap Sort Steps

1. Building the Max-Heap:

   • The first step in heap sort is to transform the input array into a max-heap. This can be done in O(n) time using the heapify operation. The heapify operation ensures that each node satisfies the max-heap property (i.e., the parent is greater than its children).
   • Starting from the last non-leaf node (index n/2 - 1), we call heapify on each node in reverse order until we reach the root.
   • Heapify takes O(log n) time for each node, but because we only need to heapify nodes that are not leaves, the overall time complexity of building the heap is O(n).

2. Extracting the Maximum Element:

   • The maximum element in a max-heap is always at the root (index 0).
   • After extracting the root, we replace it with the last element in the heap and reduce the heap size by 1.
   • Then we call the heapify operation on the root to restore the max-heap property.
   • Each extraction and heapify operation takes O(log n) time.

3. Repeat Until Sorted:

   • After the first extraction, the largest element is placed in its correct position at the end of the array. Then we repeat the extraction process on the remaining heap.
   • The algorithm continues to extract the root and restore the heap until the heap is reduced to a single element.

Time Complexity of Heap Sort

1. Building the Heap:

   • Building the max-heap takes O(n) time because we perform the heapify operation for each non-leaf node (starting from n/2 - 1 down to the root), which takes O(log n) time. The total cost is dominated by the work on the lower levels of the tree, which is linear in total.

2. Extracting the Maximum Element:

   • Extracting the root (max element) takes O(log n) time, since after each extraction, we need to heapify the root to restore the heap property.
   • Since we perform the extraction operation n times (one for each element), the time complexity for the extraction phase is O(n log n).

3. Total Time Complexity:

   • The overall time complexity of the heap sort algorithm is dominated by the O(n log n) extraction phase, while the heap building phase takes O(n) time. Therefore, the total time complexity of heap sort is O(n log n).

   • Best-case Time Complexity: O(n log n)

   • Average-case Time Complexity: O(n log n)

   • Worst-case Time Complexity: O(n log n)

   Heap sort has the same time complexity in all cases because it always performs O(log n) operations for heapifying after each extraction, regardless of the input data.

Space Complexity of Heap Sort

• Heap sort operates in-place, meaning it does not require extra memory to store a copy of the input array. It rearranges the elements within the input array itself.
• The space complexity of heap sort is O(1) because no extra space is used apart from a constant amount for auxiliary variables like indices and temporary storage during swaps.

Heap Sort Algorithm (Pseudocode)

Here is the pseudocode for heap sort:

def heapify(arr, n, i):
    largest = i       # Initialize largest as root
    left = 2 * i + 1  # Left child
    right = 2 * i + 2 # Right child

    # Check if left child exists and is greater than root
    if left < n and arr[largest] < arr[left]:
        largest = left

    # Check if right child exists and is greater than root
    if right < n and arr[largest] < arr[right]:
        largest = right

    # Change root, if needed
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # Swap
        heapify(arr, n, largest)  # Recursively heapify the affected sub-tree

def heapSort(arr):
    n = len(arr)

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

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

    return arr

Example of Heap Sort

Let's sort an array using heap sort:

Input: [4, 10, 3, 5, 1]

1. Build the Max-Heap:

   • After heapifying the array, we get the following max-heap:

         10
        /  \
       5    3
      / \
     4   1
     

2. First Extraction (Swap root with last element):

   • Swap 10 with 1, resulting in the array [1, 5, 3, 4, 10].
   • Heapify the root (after the swap):
     • The largest child is 5, so swap 1 and 5.
     • Continue heapifying to maintain the heap property.
     • Final heap after heapify: [5, 4, 3, 1, 10].

3. Second Extraction (Swap root with second-last element):

   • Swap 5 with 1, resulting in [1, 4, 3, 5, 10].
   • Heapify the root.
   • Final heap after heapify: [4, 1, 3, 5, 10].

4. Repeat the extraction process for the remaining elements:

   • Swap 4 with 1, resulting in [1, 4, 3].
   • Heapify the root.
   • Continue this process until all elements are sorted.

Final sorted array: [1, 3, 4, 5, 10].

Advantages of Heap Sort

1. Time Complexity:
   Heap sort guarantees O(n log n) time complexity in the worst, average, and best cases. This makes it a reliable sorting algorithm.

2. In-place Sorting:
   Heap sort is an in-place algorithm, meaning it does not require additional space apart from a small constant amount for temporary variables.

3. Non-Recursive Version:
   Although the recursive heapify method can be used, heap sort can also be implemented non-recursively, which may be advantageous in some scenarios.

Disadvantages of Heap Sort

1. Not Stable:
   Heap sort is not a stable sort (i.e., equal elements may not maintain their original relative order).

2. Not Adaptive:
   Unlike algorithms like Insertion Sort, heap sort does not adapt to partially sorted input arrays. It always runs in O(n log n) time.

3. Constant Factors:
   While the time complexity is good, the constant factors involved in heap sort may make it slower in practice than algorithms like Merge Sort or Quick Sort for smaller datasets.

Conclusion

Heap sort is a comparison-based sorting algorithm with O(n log n) time complexity in all cases. It has the advantage of being in-place and guarantees good performance even in the worst case. However, it is not stable and may have slightly worse practical performance due to larger constant factors compared to other algorithms like Quick Sort or Merge Sort.