# Understanding Heap-Based Algorithms with Swift

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.

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 + 1right= 2i + 2parent= 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:*

**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.

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

}

# Get the free iOS Interview Worksheet

Need to prepare for your next technical interview? We’re offering a free 5-page download of tips and tricks to help you be successful. When you sign up using **this link**, we’ll send you the worksheet in PDF format.