Day 28
Day 28: Heapsort Algorithm
28/60 Days
Heapsort Algorithm #
Welcome to Day 28 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore the Heapsort algorithm, an efficient, comparison-based sorting algorithm that leverages the properties of a heap data structure.
Introduction to Heapsort #
Heapsort is a sorting algorithm that uses a binary heap data structure to sort elements. It’s an in-place algorithm with an O(n log n) time complexity, making it optimal for large datasets.
How Heapsort Works #
Heapsort works in two main steps:
- Build a max heap from the input array.
- Repeatedly extract the maximum element from the heap and place it at the end of the array.
Implementing Heapsort #
Let’s implement the Heapsort algorithm:
1def heapify(arr, n, i):
2 largest = i
3 left = 2 * i + 1
4 right = 2 * i + 2
5
6 if left < n and arr[left] > arr[largest]:
7 largest = left
8
9 if right < n and arr[right] > arr[largest]:
10 largest = right
11
12 if largest != i:
13 arr[i], arr[largest] = arr[largest], arr[i]
14 heapify(arr, n, largest)
15
16def heapsort(arr):
17 n = len(arr)
18
19 # Build a max-heap
20 …
Continue Reading
Sign up or log in to access the full lesson and all 60 days of algorithm content.