A heap is a specialized data structure used to keep track of the minimum or maximum values in the structure. We visualize a heap as a binary tree, although in implementation it is most common to use an array to store our values. Binary trees, a subset of a classic tree structure, will be discussed more in-depth in a later lesson, but essentially means that each parent can have at most two children, a left child, and a right child.
The beauty of modeling the data as a binary tree allows us to take one small chunk of a large data structure, a single tree branch (parent, left child, right child) and apply an algorithm to just that branch and then repeat it throughout the whole tree. This technique of reducing a problem down to its smallest solvable chunk is called dynamic programming, a common topic of technical interviews. In order for our data structure to be truly classified as a heap one of two conditions must be met for each branch in a binary tree:
- In a min-heap, for any given element, its parent’s value is less than or equal to its value.
- In a max-heap, for any given element, its parent’s value is greater than or equal to its value.
One of the most recognizable advantages of a heap is the ability to get the minimum or maximum item from a data structure in O(1) or constant time. Since we are working on a type of binary tree, we can assume that each time we add or remove an item from the heap and re-sort it will run in O(logN) times where N is the total number of nodes in the tree. These are quite good run times for our basic get, add, and remove functions!
Heaps are commonly used as priority queues, think a standard FIFO (first in first out) queue except we want the first out to be the min or max of the items in the queue. Most famously though, a heap is used when implementing Dijkstra’s algorithm for finding the shortest path in a weighted graph (road networks, character move sequences, or finding how many degrees of separation you are from Kevin Bacon).
Heaps commonly come up on interview questions, though rarely as the primary question and more as the hidden optimal solution to a problem that can be solved another way with a brute force method.
Throughout this lesson, you will learn how to implement a min-heap that will be responsible for keeping track of a To-Do list of tasks and due dates.
In the editor to the right, you will see a simple implementation of a
MaxHeap class designed to store a collection of integers. As you can see we are using an array,
heap to model the binary tree.
Run the code and look at the structure of the heap printed to the console, you will notice that the first element is always the maximum value but the rest of the structure is not perfectly sorted. This is because, in order to meet the requirements of a heap above, only individual subtrees need to be sorted in order for the heap to work.