Sorting is an essential part of programming that helps us organize data efficiently. Among the many sorting algorithms, Heap Sort stands out because it uses a data structure called a heap to sort elements. A heap is a specialized tree-based structure that allows easy access to the largest (or smallest) element. Heap Sort works by first building a heap from the array, and then repeatedly extracting the largest element and placing it at the end of the array. This approach ensures that the array is sorted step by step in a predictable and efficient manner.
with hands-on learning.
get the skills and confidence to land your next move.
Heap Sort is widely used in applications where performance and memory efficiency are important. It is faster than simple algorithms like Bubble Sort and Insertion Sort for large datasets because it consistently runs in O(n log n) time. Learning Heap Sort in Ruby introduces beginners to both sorting logic and tree-based structures, helping them understand how algorithms can be designed for efficiency. In this article, we will explore multiple ways to implement Heap Sort in Ruby, including loops, recursion, and different variations for ascending and descending order.
Program 1: Heap Sort Using Max Heap
This first program demonstrates Heap Sort using a max heap to sort a predefined array in ascending order.
# Program 1: Heap Sort using max heap
def heapify(array, n, i)
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n && array[left] > array[largest]
largest = left
end
if right < n && array[right] > array[largest]
largest = right
end
if largest != i
array[i], array[largest] = array[largest], array[i]
heapify(array, n, largest)
end
end
def heap_sort(array)
n = array.length
(n / 2 - 1).downto(0) do |i|
heapify(array, n, i)
end
(n - 1).downto(0) do |i|
array[0], array[i] = array[i], array[0]
heapify(array, i, 0)
end
array
end
numbers = [12, 11, 13, 5, 6, 7]
sorted_array = heap_sort(numbers)
puts "Sorted array: #{sorted_array}"In this program, the heapify function ensures that the subtree rooted at a given index satisfies the max heap property. The heap_sort function first builds a max heap and then repeatedly swaps the root with the last element, reducing the heap size each time. Beginners can see how the largest element “bubbles” to the correct position during each iteration. This approach is both efficient and visually clear for understanding the heap concept.
Program 2: Heap Sort in Descending Order
Heap Sort can be easily modified to sort in descending order by using a min heap instead of a max heap.
# Program 2: Heap Sort in descending order using min heap
def heapify_min(array, n, i)
smallest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n && array[left] < array[smallest]
smallest = left
end
if right < n && array[right] < array[smallest]
smallest = right
end
if smallest != i
array[i], array[smallest] = array[smallest], array[i]
heapify_min(array, n, smallest)
end
end
def heap_sort_desc(array)
n = array.length
(n / 2 - 1).downto(0) do |i|
heapify_min(array, n, i)
end
(n - 1).downto(0) do |i|
array[0], array[i] = array[i], array[0]
heapify_min(array, i, 0)
end
array
end
numbers = [20, 15, 30, 10, 5]
sorted_array = heap_sort_desc(numbers)
puts "Sorted array (descending): #{sorted_array}"In this variation, the heap property is reversed to form a min heap. The smallest element moves to the correct position during each iteration. Beginners can understand that changing the heap property allows Heap Sort to sort in either ascending or descending order without changing the overall logic.
Program 3: Heap Sort Using While Loops
This approach demonstrates Heap Sort using loops instead of recursion for heapification. It can help beginners visualize the iterative process.
# Program 3: Heap Sort using iterative heapify
def heapify_iterative(array, n, i)
largest = i
loop do
left = 2 * i + 1
right = 2 * i + 2
largest = i
largest = left if left < n && array[left] > array[largest]
largest = right if right < n && array[right] > array[largest]
break if largest == i
array[i], array[largest] = array[largest], array[i]
i = largest
end
end
def heap_sort_iterative(array)
n = array.length
(n / 2 - 1).downto(0) { |i| heapify_iterative(array, n, i) }
(n - 1).downto(0) do |i|
array[0], array[i] = array[i], array[0]
heapify_iterative(array, i, 0)
end
array
end
numbers = [9, 4, 7, 1, 3, 6]
sorted_array = heap_sort_iterative(numbers)
puts "Sorted array: #{sorted_array}"This program replaces recursive calls with a loop inside heapify_iterative. Beginners will find it useful because it shows the same heap-building process without recursion, making it easier to trace element movement. It also introduces the concept of using loops for tasks usually handled recursively.
Program 4: Heap Sort with Strings
Heap Sort can also sort strings alphabetically. This example demonstrates sorting a predefined array of strings.
# Program 4: Heap Sort for strings
def heapify_string(array, n, i)
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n && array[left] > array[largest]
largest = left
end
if right < n && array[right] > array[largest]
largest = right
end
if largest != i
array[i], array[largest] = array[largest], array[i]
heapify_string(array, n, largest)
end
end
def heap_sort_string(array)
n = array.length
(n / 2 - 1).downto(0) { |i| heapify_string(array, n, i) }
(n - 1).downto(0) do |i|
array[0], array[i] = array[i], array[0]
heapify_string(array, i, 0)
end
array
end
words = ["mango", "apple", "banana", "cherry", "kiwi"]
sorted_words = heap_sort_string(words)
puts "Sorted words: #{sorted_words}"This example is particularly helpful for beginners working with text data. By comparing strings alphabetically and applying the same heap-building logic, Heap Sort demonstrates its versatility. It shows that the algorithm is not limited to numbers and can handle different types of data efficiently.
Program 5: Optimized Heap Sort
This version improves the standard Heap Sort by minimizing swaps. Instead of swapping at every step during heapification, it temporarily stores the element and shifts others, placing it only once in its correct position.
# Program 5: Optimized Heap Sort
def heapify_optimized(array, n, i)
temp = array[i]
while 2 * i + 1 < n
child = 2 * i + 1
if child + 1 < n && array[child + 1] > array[child]
child += 1
end
break if temp >= array[child]
array[i] = array[child]
i = child
end
array[i] = temp
end
def heap_sort_optimized(array)
n = array.length
# Build max heap
(n / 2 - 1).downto(0) { |i| heapify_optimized(array, n, i) }
# Extract elements from heap
(n - 1).downto(1) do |i|
array[0], array[i] = array[i], array[0]
heapify_optimized(array, i, 0)
end
array
end
numbers = [20, 15, 30, 10, 5, 25]
sorted_array = heap_sort_optimized(numbers)
puts "Optimized sorted array: #{sorted_array}"In this optimized approach, the heapify_optimized function stores the value of the current node in a temporary variable (temp). Instead of swapping repeatedly while moving down the heap, it shifts children up until the correct position for temp is found, and then places it there. This reduces the total number of swaps and slightly improves performance for larger arrays. Beginners will notice that the logic of heap building and extraction remains the same, but the process becomes more efficient.
This optimized version is a practical enhancement over the standard Heap Sort, and understanding it gives beginners insight into performance improvements without changing the core algorithm. It also demonstrates that small changes in implementation can lead to better efficiency.
Frequently Asked Questions (FAQ)
Heap Sort often raises questions among beginners. Here are some common queries:
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 consistently efficient compared to simpler algorithms.
Q2: Is Heap Sort stable?
No, Heap Sort is not stable by default because the relative order of equal elements may change during heapification.
Q3: Can Heap Sort handle large datasets?
Yes, Heap Sort is efficient and works well for large datasets because of its predictable O(n log n) performance.
Q4: When should I use Heap Sort?
Heap Sort is ideal when you need a reliable, efficient, and memory-friendly sorting algorithm. It is widely used in real-world applications like priority queues and scheduling.
Conclusion
In this article, we explored how to implement Heap Sort in Ruby using max heaps, min heaps for descending order, iterative heapification, and sorting strings. Heap Sort is a powerful algorithm that teaches beginners about tree-based data structures, recursion, and array manipulation. By practicing these examples, you will gain a strong understanding of both the algorithm and its practical applications. Heap Sort is efficient, versatile, and a valuable tool for any programmer looking to work with large datasets or complex sorting tasks. Experimenting with it in Ruby will help you build confidence in sorting logic and algorithm design.
