Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. It involves building a heap from the input data and then repeatedly extracting the maximum element from the heap and rebuilding the heap until all elements are sorted. Heap sort has a time complexity of O(n log n) and is considered an efficient and reliable sorting algorithm.
Consider an array with the following elements:
[4, 10, 3, 5, 1]
To sort this array using heap sort, follow these steps:
Let's apply these steps to the example array:
Below is the pseudo code for the heap sort algorithm:
function heapSort(array)
n = length(array)
for i = n / 2 - 1 to 0 do
heapify(array, n, i)
end for
for i = n - 1 to 0 do
swap(array[0], array[i])
heapify(array, i, 0)
end for
end function
function heapify(array, n, i)
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and array[left] > array[largest] then
largest = left
end if
if right < n and array[right] > array[largest] then
largest = right
end if
if largest != i then
swap(array[i], array[largest])
heapify(array, n, largest)
end if
end function
Explanation:
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[largest] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
# Example usage:
array = [4, 10, 3, 5, 1]
print("Original array:", array)
heap_sort(array)
print("Sorted array:", array) # Output: [1, 3, 4, 5, 10]
This Python program defines functions to perform heap sort on an array. The heapify function maintains the max heap property, and the heap_sort function builds the heap and extracts elements to sort the array.