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:

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:

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:

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:

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.

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.

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:

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.

Swift Algorithms & Data Structures

Modern Code, Illustrations & Computer science

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store