Sorting algorithms are a fundamental part of programming, and understanding them can significantly improve how you handle data. Heap Sort is a popular and efficient algorithm that organizes data in a specific order, usually ascending or descending. It is widely used in real-world applications, such as scheduling tasks, handling priority queues, and managing large datasets in memory. For beginners, learning Heap Sort is not only about sorting but also about understanding data structures like heaps.
with hands-on learning.
get the skills and confidence to land your next move.
Heap Sort is based on a binary heap data structure. It works by first building a max heap (for ascending order) or min heap (for descending order) from the data, and then repeatedly removing the root of the heap to build a sorted array. This algorithm is particularly useful because it guarantees O(n log n) performance in all cases, making it reliable for large datasets. In this article, we will explore multiple implementations of Heap Sort in Dart, helping beginners understand both the concept and practical coding techniques.
Program 1: Basic Heap Sort Using Max Heap
This first program demonstrates the classic Heap Sort approach using a max heap. It builds a max heap from the input array and then repeatedly extracts the maximum element to sort the array.
void heapSort(List<int> arr) {
int n = arr.length;
// Build max heap
for (int i = n ~/ 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements from heap
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
void heapify(List<int> arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
void main() {
List<int> numbers = [12, 11, 13, 5, 6, 7];
print("Original List: $numbers");
heapSort(numbers);
print("Sorted List: $numbers");
}In this program, the heapify function ensures that the heap property is maintained. Beginners can understand how a max heap helps move the largest element to the top, and how repeatedly removing it builds a sorted array. This approach introduces both recursion and array manipulation in a structured way.
Program 2: Heap Sort in Descending Order
Heap Sort can also sort arrays in descending order by building a min heap instead of a max heap. This program demonstrates that modification.
void heapSortDescending(List<int> arr) {
int n = arr.length;
// Build min heap
for (int i = n ~/ 2 - 1; i >= 0; i--) {
minHeapify(arr, n, i);
}
// Extract elements from heap
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
minHeapify(arr, i, 0);
}
}
void minHeapify(List<int> arr, int n, int i) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] < arr[smallest]) smallest = left;
if (right < n && arr[right] < arr[smallest]) smallest = right;
if (smallest != i) {
int swap = arr[i];
arr[i] = arr[smallest];
arr[smallest] = swap;
minHeapify(arr, n, smallest);
}
}
void main() {
List<int> numbers = [4, 10, 3, 5, 1];
print("Original List: $numbers");
heapSortDescending(numbers);
print("Sorted List in Descending Order: $numbers");
}By using a min heap and adjusting the comparison logic, the array is sorted in descending order. Beginners can see how small changes in the heap property can reverse the sorting order while keeping the algorithm’s efficiency.
Program 3: Heap Sort Without Recursion
Heapify can also be implemented iteratively, avoiding recursion. This is useful when working with very large arrays to prevent stack overflow.
void heapSortIterative(List<int> arr) {
int n = arr.length;
// Build max heap iteratively
for (int i = n ~/ 2 - 1; i >= 0; i--) {
heapifyIterative(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapifyIterative(arr, i, 0);
}
}
void heapifyIterative(List<int> arr, int n, int i) {
while (true) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
i = largest;
} else {
break;
}
}
}
void main() {
List<int> numbers = [15, 3, 17, 10, 84, 19];
print("Original List: $numbers");
heapSortIterative(numbers);
print("Sorted List: $numbers");
}The iterative heapify function eliminates recursion by using a loop to maintain the heap property. Beginners can learn alternative implementations and understand how recursion can be replaced with loops when needed.
Program 4: Heap Sort Using Generic Lists
Dart allows Heap Sort to work with generic lists, making it flexible for different data types such as doubles or strings. This program demonstrates a generic approach.
void heapSortGeneric<T extends Comparable>(List<T> arr) {
int n = arr.length;
for (int i = n ~/ 2 - 1; i >= 0; i--) {
heapifyGeneric(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
T temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapifyGeneric(arr, i, 0);
}
}
void heapifyGeneric<T extends Comparable>(List<T> arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left].compareTo(arr[largest]) > 0) largest = left;
if (right < n && arr[right].compareTo(arr[largest]) > 0) largest = right;
if (largest != i) {
T swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapifyGeneric(arr, n, largest);
}
}
void main() {
List<String> words = ['banana', 'apple', 'cherry', 'date'];
print("Original List: $words");
heapSortGeneric(words);
print("Sorted List: $words");
}This generic implementation allows Heap Sort to handle multiple data types, making the algorithm versatile. Beginners can see how type flexibility in Dart enables sorting of numbers, strings, and other comparable objects without rewriting the algorithm.
Program 5: Heap Sort Using a Priority Queue (Ascending Order)
Heap Sort can be implemented using a Priority Queue, which internally uses a heap structure.
This program sorts a list of numbers from smallest to largest.
// Custom Priority Queue implementation (Min-Heap)
class PriorityQueue<T extends Comparable> {
final List<T> _heap = [];
void add(T value) {
_heap.add(value);
_heapifyUp(_heap.length - 1);
}
T removeFirst() {
if (_heap.isEmpty) {
throw StateError('PriorityQueue is empty');
}
final first = _heap.first;
final last = _heap.removeLast();
if (_heap.isNotEmpty) {
_heap[0] = last;
_heapifyDown(0);
}
return first;
}
bool get isEmpty => _heap.isEmpty;
void _heapifyUp(int index) {
while (index > 0) {
final parent = (index - 1) ~/ 2;
if (_heap[index].compareTo(_heap[parent]) < 0) {
_swap(index, parent);
index = parent;
} else {
break;
}
}
}
void _heapifyDown(int index) {
final lastIndex = _heap.length - 1;
while (true) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int smallest = index;
if (left <= lastIndex && _heap[left].compareTo(_heap[smallest]) < 0) {
smallest = left;
}
if (right <= lastIndex && _heap[right].compareTo(_heap[smallest]) < 0) {
smallest = right;
}
if (smallest == index) break;
_swap(index, smallest);
index = smallest;
}
}
void _swap(int i, int j) {
final temp = _heap[i];
_heap[i] = _heap[j];
_heap[j] = temp;
}
}
// Heap Sort using the custom Priority Queue (ascending)
void heapSortAscending(List<int> arr) {
final pq = PriorityQueue<int>();
for (var num in arr) {
pq.add(num);
}
for (int i = 0; i < arr.length; i++) {
arr[i] = pq.removeFirst();
}
}
void main() {
List<int> numbers = [20, 3, 15, 7, 9];
print("Original List: $numbers");
heapSortAscending(numbers);
print("Sorted List (Ascending): $numbers");
}Using a Priority Queue, elements are organized in a heap, which ensures that the smallest element is always removed first.
This makes sorting efficient and straightforward.
Program 6: Heap Sort Using a Priority Queue (Descending Order)
Sorting in descending order is similar, but we organize the heap so that the largest element is removed first.
// Custom Priority Queue implementation (Max-Heap)
class PriorityQueueDesc<T extends Comparable> {
final List<T> _heap = [];
void add(T value) {
_heap.add(value);
_heapifyUp(_heap.length - 1);
}
T removeFirst() {
if (_heap.isEmpty) {
throw StateError('PriorityQueue is empty');
}
final first = _heap.first;
final last = _heap.removeLast();
if (_heap.isNotEmpty) {
_heap[0] = last;
_heapifyDown(0);
}
return first;
}
bool get isEmpty => _heap.isEmpty;
void _heapifyUp(int index) {
while (index > 0) {
final parent = (index - 1) ~/ 2;
if (_heap[index].compareTo(_heap[parent]) > 0) {
_swap(index, parent);
index = parent;
} else {
break;
}
}
}
void _heapifyDown(int index) {
final lastIndex = _heap.length - 1;
while (true) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int largest = index;
if (left <= lastIndex && _heap[left].compareTo(_heap[largest]) > 0) {
largest = left;
}
if (right <= lastIndex && _heap[right].compareTo(_heap[largest]) > 0) {
largest = right;
}
if (largest == index) break;
_swap(index, largest);
index = largest;
}
}
void _swap(int i, int j) {
final temp = _heap[i];
_heap[i] = _heap[j];
_heap[j] = temp;
}
}
// Heap Sort using the custom Priority Queue (descending)
void heapSortDescending(List<int> arr) {
final pq = PriorityQueueDesc<int>();
for (var num in arr) {
pq.add(num);
}
for (int i = 0; i < arr.length; i++) {
arr[i] = pq.removeFirst();
}
}
void main() {
List<int> numbers = [20, 3, 15, 7, 9];
print("Original List: $numbers");
heapSortDescending(numbers);
print("Sorted List (Descending): $numbers");
}With this Max-Heap Priority Queue, the largest element is always on top, so the array is sorted from largest to smallest.
Both program 5 and 6 show how a heap structure in a Priority Queue allows for efficient sorting with O(n log n) complexity, whether in ascending or descending order.
Frequently Asked Questions (FAQ)
Heap Sort is widely used in programming, but beginners often have questions about it. Here are some helpful answers.
Q1: What is the time complexity of Heap Sort?
Heap Sort has a time complexity of O(n log n) for all cases, making it reliable for large datasets.
Q2: Is Heap Sort stable?
No, Heap Sort is not stable by default. Equal elements may change their relative order during sorting.
Q3: Can Heap Sort be implemented iteratively?
Yes, iterative heapify eliminates recursion and is useful for very large arrays.
Q4: When should Heap Sort be used?
Heap Sort is ideal for applications that need guaranteed O(n log n) performance and when memory usage must be controlled.
Q5: Can Heap Sort work with different data types?
Yes, by using generics or Dart’s PriorityQueue, Heap Sort can handle integers, doubles, strings, or any comparable objects.
Conclusion
Heap Sort is a powerful and efficient algorithm that every Dart programmer should learn. It introduces concepts like heaps, recursion, iterative processing, and generic programming. In this article, we explored multiple Heap Sort implementations, including recursive, descending order, iterative, generic, and PriorityQueue-based approaches.
For beginners, practicing Heap Sort and experimenting with different data types and heap structures will strengthen problem-solving skills and algorithmic thinking. Mastering Heap Sort provides a strong foundation for handling complex sorting and priority-based tasks in Dart.
