Heaps

In the previous essay, 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 our algorithm with the addition of binary heaps.

How it works

In its basic form, 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.

The array visualized as a "nearly complete" binary tree.

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

Sorting Heaps

An interesting feature of heaps is their ability to sort data. As we've seen, many algorithms are designed to sort entire datasets. 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.

Fig. 2. 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.

//obtain the best path
var bestPath: Path = Path()
while(frontier.count != 0) {
    //support path changes using the greedy approach
    bestPath = Path()

    var x: Int = 0
    var pathIndex: Int = 0

    for (x = 0; x < frontier.count; x++) {
        var itemPath: Path = frontier[x]

        if (bestPath.total == nil) || (itemPath.total < bestPath.total) {
            bestPath = itemPath
            pathIndex = x
        }
    } //end for

While it accomplished our goal, we applied a brute force technique. In other words, we examined every path to find the shortest path. This code is said to run in linear time or O(n). If the frontier contained a million rows, how would this impact the algorthim's overall performance?

The Heap Structure

Let's create a more efficient frontier. Named PathHeap, the class will extend the functionality of an Array.

//a basic min-heap data strcture
public class PathHeap {
    private var heap: Array

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

    init() {
        heap = Array()
    }
}

PathHeap includes two properties - Array and Int. To support good design (e.g., encapsulation), the heap has been declared a private property. To track the number of items, the count has also been declared as a computed property.

Building the Queue

Finding the best path more efficiently than O(n) will require a new way of thinking. We can improve our algorithm's performance to O(1) through a "bubble-up" approach. Using our heapsort formulas, this involves "swapping" 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))
    }

    //use the bottom-up approach
    while (childIndex != 0) {
        var childToUse: Path = heap[Int(childIndex)]
        var parentToUse: Path = heap[parentIndex]

        //swap child and parent positions
        if (childToUse.total < parentToUse.total) {
            heap.insert(childToUse, atIndex: parentIndex)
            heap.removeAtIndex(Int(childIndex) + 1)

            heap.insert(parentToUse, atIndex: Int(childIndex))
            heap.removeAtIndex(parentIndex + 1)
        }

        //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 algorithm's, 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.

Fig. 3. A heap structure that maintains the min-heap property.

Fig. 4 . The enQueue process compares a newly added value with its parent in a process called "bubbling-up".

Fig. 5. The compare / swap process continues recursively until the smallest value is positioned at the root.

Since the enQueue method maintains the min-heap property (as new items are added), we all but eliminate the task of finding the shortest path. Here, we implement a basic peek method to retrieve the root-level item:

//obtain the minimum path
func peek() -> Path! {
    if (heap.count > 0) {
        var shortestPath: Path = heap[0]
        return shortestPath
    }
    else {
        return nil
    }
}

The Results

With the frontier refactored, let's see the applied changes. As new paths are discovered, they are automatically sorted by the frontier. The PathHeap count forms the base case for our loop condition and the bestPath is retrieved using the peek method.

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

while(frontier.count != 0) {
    //use the greedy approach to obtain the best path
    bestPath = Path()
    bestPath = frontier.peek()
}

Want to see the entire algorithm? Here's the source.