Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. It divides the input array into a sorted region and an unsorted region, and repeatedly extracts the maximum element from the unsorted region and inserts it into the sorted region.

Here's the step-by-step process of performing heap sort:

1. Build a max heap: Convert the input array into a max heap, where the value of each node is greater than or equal to the values of its children. Starting from the last non-leaf node (index n/2-1), where n is the size of the array, heapify the nodes in reverse order until the root.

2. Extract the maximum element: Swap the first element (root) with the last element of the unsorted region. Decrease the size of the unsorted region by one. Heapify the root to maintain the max heap property.

3. Repeat step 2: Repeat the extraction step until the unsorted region has only one element left. After each extraction, the sorted region grows from the end of the array.

4. Final sorted array: The array is now sorted in ascending order. The sorted region contains all the elements in the correct order.

Here's an example implementation of heap sort in 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 a max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

# Usage example
arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
print("Sorted array is:", arr)

This implementation uses a recursive `heapify` function to maintain the max heap property and performs the sorting in-place. The time complexity of heap sort is O(n log n), where n is the number of elements in the array.

Algorithm

Heap sort is a comparison-based sorting algorithm that operates by transforming an array into a binary heap structure, then repeatedly extracting the maximum element from the heap and placing it at the end of the sorted array. The steps involved in the Heap sort algorithm are as follows:

1. Build Max Heap: Convert the input array into a max heap. This is done by starting from the last non-leaf node (n/2 - 1) and performing the max heapify operation on each node in reverse order up to the root. Max heapify ensures that the property of the heap is maintained, with each node being greater than or equal to its children.

2. Extract Maximum and Heapify: Extract the maximum element from the heap and swap it with the last element in the heap. Reduce the heap size by 1 and then perform max heapify on the root to restore the heap property. Repeat this step until all elements are extracted.

The steps above can be summarized in the following pseudocode for the Heap sort algorithm:

heapSort(arr):
    n = length of arr

// Build Max Heap
for i from (n/2 - 1) down to 0:
    maxHeapify(arr, n, i)

// Extract maximum element and heapify
for i from n-1 down to 1:
    swap(arr[0], arr[i])
    maxHeapify(arr, i, 0)

maxHeapify(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:
    swap(arr[i], arr[largest])
    maxHeapify(arr, n, largest)

The time complexity of the Heap sort algorithm is O(n log n) in all cases, where n is the number of elements in the array. This is because the build max heap operation takes O(n) time, and the extract maximum and heapify operation is performed n-1 times, each taking O(log n) time. The space complexity is O(1) as it only requires a constant amount of extra space for swapping elements.

Program

Here's an example implementation of the Heap sort algorithm in Python:

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

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

# Check if the right child of the root exists and is greater than the largest element so far
if right < n and arr[right] > arr[largest]:
    largest = right

# If the largest element is not the root, swap them
if largest != i:
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, largest)

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 from the heap one by one
for i in range(n - 1, 0, -1):
    arr[i], arr[0] = arr[0], arr[i] # Swap the current root (maximum) with the last element
    heapify(arr, i, 0) # Call heapify on the reduced heap

return arr

# Example usage:
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = heapSort(arr)
print("Sorted array:", sorted_arr)

This implementation uses the `heapify()` function to maintain the max heap property and the `heapSort()` function to perform the heap sort algorithm. The `heapify()` function is called to build the initial max heap, and then the largest element is extracted and swapped with the last element in each iteration of the `heapSort()` function. Finally, the sorted array is returned.

You can replace the `arr` variable with your own list of elements to sort. Running the code will print the sorted array.

Time Complexity

The time complexity of the Heap sort algorithm in the context of Design and Analysis of Algorithms (DAA) is O(n log n) in all cases, where n is the number of elements in the array being sorted.

The Heap sort algorithm consists of two main operations:

1. Building the Max Heap: This operation takes O(n) time complexity. It involves iterating over the elements of the array from the last non-leaf node down to the root and calling the `heapify()` function. The `heapify()` function maintains the max heap property by recursively adjusting the elements. Since there are n/2 non-leaf nodes in a complete binary tree, the time complexity for building the max heap is O(n).

2. Extracting Maximum and Heapifying: This operation is performed n-1 times, as each iteration involves extracting the maximum element from the root of the max heap and heapifying the remaining elements. The `heapify()` function takes O(log n) time complexity as it adjusts the heap and maintains the heap property. Therefore, performing this operation n-1 times results in a time complexity of O((n-1) log n), which is asymptotically equivalent to O(n log n).

Hence, the overall time complexity of Heap sort is O(n log n). It is worth noting that Heap sort has a consistent time complexity regardless of the input order, making it suitable for large datasets where a stable sorting algorithm is not required.

Space Complexity

The space complexity of the Heap sort algorithm in the context of Design and Analysis of Algorithms (DAA) is O(1), meaning it requires a constant amount of extra space.

Heap sort is an in-place sorting algorithm, which means it doesn't require additional memory proportional to the input size. The sorting is performed directly on the input array itself, without the need for any auxiliary data structures.

The only additional space used in the Heap sort algorithm is for variables used during the sorting process, such as loop counters, indices, and temporary variables for swapping elements. These variables require a constant amount of memory that does not depend on the input size.

Therefore, the space complexity of Heap sort is O(1), making it an efficient sorting algorithm in terms of space utilization.

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc