Heap Sort is one of the classic sorting algorithms that many programmers learn when they begin exploring data structures and algorithms. It works by using a special tree-like structure called a heap, which allows you to pick the largest or smallest element quickly. Even though the idea may sound a bit advanced at first, the steps become much clearer once you understand how the heap structure is built and adjusted. The whole algorithm works in a predictable and reliable way, which makes it a favourite in many practical situations.
with hands-on learning.
get the skills and confidence to land your next move.
A heap is useful because it makes it easy to manage priorities, and that same skill is what allows Heap Sort to organize data efficiently. You will often see heaps used in priority queues, scheduling systems, and anywhere you need to get the highest or lowest value fast. Learning Heap Sort in Swift helps you understand how such systems work under the surface. With Swift’s clean syntax, the logic becomes easier to follow, even for beginners.
Program 1: Basic Max-Heap Sort Using Loops
This first program shows a basic implementation of Heap Sort using a max-heap. It builds a heap from the data and slowly extracts the largest elements one by one. The predefined array makes it easy to run and understand the output.
import Foundation
func heapify(_ array: inout [Int], _ count: Int, _ root: Int) {
var largest = root
let left = 2 * root + 1
let right = 2 * root + 2
if left < count && array[left] > array[largest] {
largest = left
}
if right < count && array[right] > array[largest] {
largest = right
}
if largest != root {
array.swapAt(root, largest)
heapify(&array, count, largest)
}
}
func heapSort(_ array: inout [Int]) {
let count = array.count
for i in stride(from: count / 2 - 1, through: 0, by: -1) {
heapify(&array, count, i)
}
for i in stride(from: count - 1, through: 0, by: -1) {
array.swapAt(0, i)
heapify(&array, i, 0)
}
}
var data = [40, 20, 60, 10, 50, 30]
heapSort(&data)
print("Heap Sort result:", data)This program first builds the heap, then extracts the largest values by swapping the root with the last element. The heapify function keeps the heap valid while shrinking the usable part of the array. Beginners find this approach helpful because the steps are repetitive and easy to follow, making it clearer how the heap structure controls the sorting process.
Program 2: Min-Heap Sort for Ascending Order
This second example uses a min-heap instead of a max-heap. The smallest element rises to the top, and by extracting it repeatedly, the array becomes sorted in ascending order. This approach shows how heap logic can work in reverse.
import Foundation
func minHeapify(_ array: inout [Int], _ count: Int, _ root: Int) {
var smallest = root
let left = 2 * root + 1
let right = 2 * root + 2
if left < count && array[left] < array[smallest] {
smallest = left
}
if right < count && array[right] < array[smallest] {
smallest = right
}
if smallest != root {
array.swapAt(root, smallest)
minHeapify(&array, count, smallest)
}
}
func minHeapSort(_ array: [Int]) -> [Int] {
var arr = array
let count = arr.count
for i in stride(from: count / 2 - 1, through: 0, by: -1) {
minHeapify(&arr, count, i)
}
var result: [Int] = []
for i in stride(from: count - 1, through: 0, by: -1) {
result.append(arr[0])
arr[0] = arr[i]
minHeapify(&arr, i, 0)
}
return result
}
let sample = [12, 3, 19, 7, 5]
let sorted = minHeapSort(sample)
print("Min-heap sorted result:", sorted)This version shows how easily heap behavior can be changed simply by adjusting comparisons. It helps beginners understand that the structure stays the same while the logic adapts to the sorting direction. This flexibility makes heaps useful in many types of algorithms, not just sorting.
Program 3: Heap Sort Using a Recursive Builder
This program introduces a more recursive approach. The heap is built through recursion, making it easier to see how the structure forms naturally from the bottom up.
import Foundation
func heapify(_ array: inout [Int], _ count: Int, _ root: Int) {
var largest = root
let left = 2 * root + 1
let right = 2 * root + 2
if left < count && array[left] > array[largest] {
largest = left
}
if right < count && array[right] > array[largest] {
largest = right
}
if largest != root {
array.swapAt(root, largest)
heapify(&array, count, largest)
}
}
func buildHeapRecursively(_ array: inout [Int], _ index: Int) {
if index < 0 { return }
heapify(&array, array.count, index)
buildHeapRecursively(&array, index - 1)
}
func heapSort(_ array: inout [Int]) {
let count = array.count
for i in stride(from: count / 2 - 1, through: 0, by: -1) {
heapify(&array, count, i)
}
for i in stride(from: count - 1, through: 0, by: -1) {
array.swapAt(0, i)
heapify(&array, i, 0)
}
}
var numbers = [14, 9, 7, 3, 18, 20]
buildHeapRecursively(&numbers, numbers.count / 2 - 1)
heapSort(&numbers)
print("Recursive heap build result:", numbers)This approach focuses on the building stage, showing how recursion can replace looping logic. For beginners who enjoy recursive thinking, this offers a cleaner view of the transformation from an unsorted array into a complete heap. It also helps reinforce how each level of the heap depends on the structure beneath it.
Program 4: Heap Sort Using a Custom Struct
This program uses a custom heap structure. It helps you see how Swift allows grouping functions and data neatly in one place. The custom struct manages its own heap building and sorting logic.
import Foundation
func heapify(_ array: inout [Int], _ count: Int, _ root: Int) {
var largest = root
let left = 2 * root + 1
let right = 2 * root + 2
if left < count && array[left] > array[largest] {
largest = left
}
if right < count && array[right] > array[largest] {
largest = right
}
if largest != root {
array.swapAt(root, largest)
heapify(&array, count, largest)
}
}
struct HeapSorter {
var array: [Int]
mutating func sort() {
let count = array.count
for i in stride(from: count / 2 - 1, through: 0, by: -1) {
heapify(&array, count, i)
}
for i in stride(from: count - 1, through: 0, by: -1) {
array.swapAt(0, i)
heapify(&array, i, 0)
}
}
}
var sorter = HeapSorter(array: [33, 15, 27, 8, 19])
sorter.sort()
print("Struct-based Heap Sort:", sorter.array)By placing the sorting logic inside a struct, the code becomes more organized. Beginners can see how Swift encourages grouping related behavior, making larger programs easier to manage. This method also prepares new programmers to build cleaner and more reusable code structures.
Program 5: Generic Heap Sort Using Comparable Types
This version takes Heap Sort further by making it generic. It allows sorting of any type that follows Swift’s Comparable protocol, including strings or custom objects.
import Foundation
func genericHeapify<T: Comparable>(_ array: inout [T], _ count: Int, _ root: Int) {
var largest = root
let left = 2 * root + 1
let right = 2 * root + 2
if left < count && array[left] > array[largest] {
largest = left
}
if right < count && array[right] > array[largest] {
largest = right
}
if largest != root {
array.swapAt(root, largest)
genericHeapify(&array, count, largest)
}
}
func genericHeapSort<T: Comparable>(_ array: inout [T]) {
let count = array.count
for i in stride(from: count / 2 - 1, through: 0, by: -1) {
genericHeapify(&array, count, i)
}
for i in stride(from: count - 1, through: 0, by: -1) {
array.swapAt(0, i)
genericHeapify(&array, i, 0)
}
}
// I. Sorting Strings
var words = ["leopard", "dog", "cat", "bear", "zebra"]
genericHeapSort(&words)
print("Generic Heap Sort result (STRINGS):", words)
// II. Sorting Numbers
var numbers = [0, -3, 1, 8, 3, 5, 9]
genericHeapSort(&numbers)
print("Generic Heap Sort result (NUMBERS):", numbers)Using generics allows this algorithm to be applied to many different kinds of data. Beginners can see how Swift’s type system makes algorithms more flexible without making the code harder to understand. This version is especially useful if you want to sort more than just numbers.
Frequently Asked Questions (FAQ)
This short FAQ section helps clear up common doubts and gives beginners a simple view of how Heap Sort behaves. The answers are written in plain English so anyone learning Swift can understand them without stress.
Q1: Why do we use a heap for sorting?
A heap gives us a quick way to get the largest or smallest element, which is exactly what we need when sorting. By always pulling the top value and rebuilding the heap, the data slowly falls into the right order. This steady and predictable behavior is what makes heap-based sorting reliable.
Q2: Is Heap Sort faster than Quick Sort?
Heap Sort can be very steady because it always runs in the same time range, even in bad cases. Quick Sort is usually faster when the data is well spread out, but it can slow down in rare situations. Heap Sort remains a safe choice when you need something consistent and dependable.
Q3: Does Heap Sort always use a tree structure?
Even though a heap is a kind of tree, it is stored inside an array. The tree shape exists only in the way the index positions are used, not in an actual tree object. This makes the algorithm efficient while still keeping the tree logic alive inside the array.
Q4: Can Heap Sort work with strings or custom objects?
Yes, Heap Sort works with any type that can be compared. As long as the items know how to compare themselves, Swift can build a heap from them. This makes the algorithm flexible enough to sort words, numbers, or even your own object types.
Q5: Why does Heap Sort often use in-place logic?
Heap Sort is known for saving memory because it organizes the data inside the same array. This in-place style means you don’t need extra storage to finish the job. It is one of the reasons Heap Sort is trusted in systems where memory needs to be managed carefully.
Conclusion
Heap Sort may look complex at first sight, but once you understand how a heap grows and shrinks during the sorting process, the whole picture becomes much clearer. It offers reliable performance and gives you a deeper understanding of how priority-based structures work. Swift makes the process smoother by offering readable syntax and flexible tools, letting you choose between loops, recursion, structs, or generics.
The best way to learn Heap Sort is to experiment with small arrays, change the values, and try different versions of the algorithm. As you practice, the heap idea will feel more natural, and you will become more confident in working with sorting algorithms in general.
