# 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 integerslet 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   //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 //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 processingenum 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.

Written by

## 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