Understanding Heap-Based Algorithms with Swift

Wayne Bishop
Dec 15, 2018 · 5 min read

In the previous chapter in our series, we reviewed Dijkstra’s algorithm for searching a graph. Originally published in 1959, this popular technique for finding the shortest path is an elegant solution to a complex problem. The design involved many parts including graph traversal, custom data structures and the greedy approach.

When designing programs, it’s great to see them work. With Dijkstra, the algorithm did allow us to find the shortest path between a source Vertex and Destination. However, our approach could be refined to be more efficient. In this essay, we’ll enhance the algorithm with the addition of binary heaps.

HOW IT WORKS

In its basic form, the data structure for a heap is just an Array. However, unlike an Array, we visualize it as a tree. The term visualize implies we use processing techniques normally associated with recursive data structures. This shift in thinking has numerous advantages. Consider the following:

//a simple array of unsorted integers
let numberList : Array<Int> = [8, 2, 10, 9, 11, 7]

As shown, numberList can be easily represented as a Heap. Starting at index 0, items fill a corresponding spot as a parent or child node. Each parent also has two children with the exception of index 2.

An array visualized as a “nearly complete” tree.

Since the arrangement of values is sequential, a simple pattern emerges. For any node, we can accurately predict its position using these formulas:

//formulas for heap indiciesleft = 2i + 1
right = 2i + 2
parent = floor(i - 1 / 2)

SORTING HEAPS

An interesting feature of heaps is their ability to sort data. As we’ve seen, many algorithms are designed to sort sequences of data. When sorting Heaps, nodes can be arranged so each parent contains a lesser value than its children. In computer science, this is called a min-heap:

A heap structure that maintains the min-heap property.

EXPLORING THE FRONTIER

With Dijkstra, we used a concept called the frontier. Coded as a simple array, we compared the total weight of each path to find the shortest path:

...

//construct the best path
var bestPath: Path = Path()

while frontier.count != 0 {

//support path changes using the greedy approach
var pathIndex: Int = 0

for x in 0..<frontier.count {

let itemPath: Path = frontier[x]

if (bestPath.total == 0) || (itemPath.total < bestPath.total) {
bestPath = itemPath
pathIndex = x
}
}
...

While it accomplished our goal, we applied a brute force technique. In other words, we examined every potential Path to find the shortest path. As shown, this code segment executes in linear time — O(n). If the frontier contained a million rows, how would this impact the algorithm’s overall performance?

THE HEAP STRUCTURE

Let’s create a more efficient frontier. Named PathHeap, the data structure will extend the functionality of an array:

public class PathHeap {

private var heap: Array<Path>

init() {
heap = Array<Path>()
}

//the number of frontier items
var count: Int {
return self.heap.count
}
}

The PathHeap class includes two properties. To support good design, Heap has been declared a private property. To track the number of items, count is declared as a computed property.

BUILDING THE QUEUE

Searching the frontier more efficiently than O(n) will require a new way of thinking. We can improve our performance to O(1) with a Heap. Using heapsort formulas, our new approach will involve arranging index values so the smallest item is positioned at the root.

//sort shortest paths into a min-heap (heapify)func enQueue(_ key: Path) {

heap.append(key)

var childIndex: Float = Float(heap.count) - 1
var parentIndex: Int = 0


//calculate parent index
if childIndex != 0 {
parentIndex = Int(floorf((childIndex - 1) / 2))
}
var childToUse: Path
var parentToUse: Path
//use the bottom-up approach
while childIndex != 0 {

childToUse = heap[Int(childIndex)]
parentToUse = heap[parentIndex]


//swap child and parent positions
if childToUse.total < parentToUse.total {
heap.swapAt(parentIndex, Int(childIndex))
}

//reset indices
childIndex = Float(parentIndex)
if childIndex != 0 {
parentIndex = Int(floorf((childIndex - 1) / 2))
}


} //end while


} //end function

The enQueue method accepts a single Path as a parameter. Unlike other sorting algorithms, our primary goal isn’t to sort each item but to find the smallest value. This means we can increase our efficiency by comparing a subset of values.

The enQueue process compares a newly added value.
The process continues until the smallest value is positioned at the root.

Since the enQueue method maintains the min-heap property, we eliminate the additional task of finding the shortest path. As a result, we increase the algorithm’s efficiency to constant time — O(1). Here, we implement a basic peek method to retrieve the root-level item.

//obtain the minimum pathfunc peek() -> Path? {

if heap.count > 0 {
return heap[0] //the shortest path
}
else {
return nil
}
}

HEAPS & GENERICS

It’s great seeing how a heap can be used to improve the time complexity of a solution. To extend our model for general use, we can also create a more generalized algorithm:

//a generic heap structureclass Heap<T: Comparable> {

private var items: Array<T>
private var heapType: HeapType

//min-heap default initialization
init(type: HeapType = .Min) {

items = Array<T>()
heapType = type
}


//the min or max value
func peek() -> T? {

if items.count > 0 {
return items[0] //the min or max value
}
else {
return nil
}
}


//addition of new items
func enQueue(_ key: T) {

items.append(key)

var childIndex: Float = Float(items.count) - 1
var parentIndex: Int = 0


//calculate parent index
if childIndex != 0 {
parentIndex = Int(floorf((childIndex - 1) / 2))
}


var childToUse: T
var parentToUse: T


//use the bottom-up approach
while childIndex != 0 {


childToUse = items[Int(childIndex)]
parentToUse = items[parentIndex]


//heapify depending on type
switch heapType {

case .Min:

//swap child and parent positions
if childToUse <= parentToUse {
items.swapAt(parentIndex, Int(childIndex))
}

case .Max:

//swap child and parent positions
if childToUse >= parentToUse {
items.swapAt(parentIndex, Int(childIndex))
}
}

//reset indices
childIndex = Float(parentIndex)

if childIndex != 0 {
parentIndex = Int(floorf((childIndex - 1) / 2))
}

} //end while
} //end function
}
//used for generic heap data structure processing
enum HeapType {

case Min
case Max
}

Liked this essay? Read and discover my other content on Medium or get the complete book in EPUB, PDF or Kindle format.

Swift Algorithms & Data Structures

A book on modern code, illustrations & computer science

Wayne Bishop

Written by

I write about Swift Development & Computer Science. Get more tips on technical interview preparation at — www.waynewbishop.com

Swift Algorithms & Data Structures

A book on modern code, illustrations & computer science

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade