13 Heaps¶

Heaps are another classical tree-based data structure with special properties to quickly fetch the largest or smallest element.

In this chapter, you’ll focus on creating and manipulating heaps. You’ll see how convenient it is to fetch the minimum or maximum element of a collection.

What’s a Heap?¶

A heap is a complete binary tree, also known as a binary heap, that can be constructed using a list.

Note

Don’t confuse these heaps with memory heaps. The term heap is sometimes confusingly used in computer science to refer to a pool of memory. Memory heaps are a different concept and not what you’re studying here.

Heaps come in two flavors:

Max-heap, in which elements with a higher value have a higher priority.
Min-heap, in which elements with a lower value have a higher priority.

The Heap Property¶

A heap has an essential characteristic that must always be satisfied. This characteristic is known as the heap property:

In a max-heap, parent nodes must always contain a value that is greater than or equal to the value in its children. The root node will always contain the highest value.
In a min-heap, parent nodes must always contain a value that is less than or equal to the value in its children. The root node will always contain the lowest value.

The image below on the left is a max-heap with 10 as the maximum value. Every node in the heap has values greater than the nodes below it. The image on the right is a min-heap. Since 1 is the minimum value, it’s on the top of the heap. Every node in this heap has values less than the nodes below it.

108451Max Heap42581Min Heap

Note that unlike a binary search tree, it’s not a requirement of the heap property that the left or right child needs to be greater. For that reason, a heap is only a partially sorted tree.

The Shape Property¶

Another essential aspect of a heap is its shape property. A heap must be a complete binary tree. This means that every level must be filled except for the last level. Additionally, when adding elements to the last level, you must add them from left to right.

In the diagram below, you can see that the first two levels are filled. The last level, Level 3, isn’t full yet, but the nodes that are there are located on the left.

810471Level 1Level 2Level 3

Heap Applications¶

Some practical applications of a heap include:

Calculating the minimum or maximum element of a collection.
Implementing the heapsort algorithm.
Constructing a priority queue.
Building graph algorithms that use a priority queue, like Dijkstra’s algorithm.

Note

You’ll learn about priority queues in Chapter 14, heapsort in Chapter 18, and Dijkstra’s algorithm in Chapter 23.

Fitting a Binary Tree Into a List¶

Trees hold nodes that store references to their children. In the case of a binary tree, these are references to a left and right child. Heaps are binary trees, but they are implemented with a simple list.

Using a list might seem like an unusual way to build a tree, but one of the benefits of this heap implementation is efficient time and space complexity since the elements in a heap are all stored together in memory. You’ll see later on that swapping elements will play a big part in heap operations. This manipulation is easier to do with a list than it is with an ordinary binary tree.

Take a look at the following image to see how you can represent a heap using a list. The numbers inside the circular nodes represent the values in the list, while the numbers outside the nodes represent the indices of the list. Note how index 0 is at the top of the heap, indices 1 and 2 are for the left and right children in Level 2, indices 3 to 6 form Level 3, and finally index 7 is in the partially filled Level 4.

Level 1Level 2Level 3Level 481342107501374562

To represent the heap above as a list, you iterate through each element level-by-level from left to right. Your traversal looks something like this:

1084712350index1234567level 1level 2level 3level 4

Every level gets twice as many indices allocated to it as the level before.

Accessing Nodes¶

It’s now easy to access any node in the heap. Instead of traversing down the left or right branch, you access a node in your list using simple formulas.

Given a node at a zero-based index i:

The left child of this node is at index 2i + 1.
The right child of this node is at index 2i + 2.

1084712350index1234567i = 0Left: 2i + 1 = 1i = 0Right: 2i + 2 = 2Left: 2i + 1 = 3i = 1Right: 2i + 2 = 4i = 1

If you want to obtain the index of a parent node, you can use either of the formulas above and solve for i.

Given a node at index i:

The parent of this node is at index (i - 1) ~/ 2.

That works for both left and right children since the ~/ integer division operator drops any fractional value.

Accessing a particular node in an actual binary tree requires traversing the tree from the root, which is an O(log n) operation. That same operation is just O(1) in a random-access data structure such as a list.

Implementation¶

Open the starter project for this chapter and add a lib folder to the root of the project. Inside that folder create a file named heap.dart.

Adding a Constructor¶

Since there are both max-heaps and min-heaps, start by adding the following enum to heap.dart:

enum Priority { max, min }

You’ll provide Priority as a constructor parameter to specify the priority type when you create a heap.

Below Priority create a class named Heap with the following basic implementation:

class Heap<E extends Comparable<dynamic>> {
  Heap({List<E>? elements, this.priority = Priority.max}) {
    this.elements = (elements == null) ? [] : elements;
  }

  late final List<E> elements;
  final Priority priority;
}

This setup offers a few features:

The default is a max-heap, but users can also choose to create a min-heap.
You can optionally specify a list of elements to initialize your heap with. Later in the chapter, you’ll add a method to sort them.
Since elements of a heap need to be sortable, the element type extends Comparable. As mentioned in previous chapters, the reason for using Comparable<dynamic> here rather than Comparable<E> is because this makes int collections easier to create.

Providing Basic Properties¶

Add the following properties to Heap:

bool get isEmpty => elements.isEmpty;

int get size => elements.length;

E? get peek => (isEmpty) ? null : elements.first;

Calling peek will give you the maximum value in the collection for a max-heap, or the minimum value in the collection for a min-heap. This is an O(1) operation.

Preparing Helper Methods¶

Any complex task can be broken down into simpler steps. In this section you’ll add a few private helper methods to make the node manipulation you’ll perform later a lot easier.

Accessing Parent and Child Indices¶

You’ve already learned the formulas for how to access the indices of the children or parent of a given node. Add the Dart implementation of those formulas to Heap:

int _leftChildIndex(int parentIndex) {
  return 2 * parentIndex + 1;
}

int _rightChildIndex(int parentIndex) {
  return 2 * parentIndex + 2;
}

int _parentIndex(int childIndex) {
  return (childIndex - 1) ~/ 2;
}

Selecting a Priority¶

When you made the Heap constructor, you allowed the user to pass in a max or min priority. Add the following two helper methods that will make use of that property:

bool _firstHasHigherPriority(E valueA, E valueB) {
  if (priority == Priority.max) {
    return valueA.compareTo(valueB) > 0;
  }
  return valueA.compareTo(valueB) < 0;
}

int _higherPriority(int indexA, int indexB) {
  if (indexA >= elements.length) return indexB;
  final valueA = elements[indexA];
  final valueB = elements[indexB];
  final isFirst = _firstHasHigherPriority(valueA, valueB);
  return (isFirst) ? indexA : indexB;
}

Both methods compare two inputs and return a value to indicate the one with the greater priority. However, the first method compares any two values while the second method compares the values at two specific indices in the list.

Again, in a max-heap, the higher value has a greater priority, while in a min-heap, the lower value has a greater priority. Centralizing that decision here means that none of the code in the rest of the class knows whether it’s in a min-heap or max-heap. It just asks for the results of the priority comparison and goes on with its business.

Swapping Values¶

You’ll add insert and remove methods to the class in just a bit. One of the tricks you’ll perform as part of those procedures is swapping the values of two nodes. Add a helper method to Heap for that:

void _swapValues(int indexA, int indexB) {
  final temp = elements[indexA];
  elements[indexA] = elements[indexB];
  elements[indexB] = temp;
}

Now that you’ve got your helpers, you’re ready to start the real magic!

Inserting Into a Heap¶

Say you start with the max-heap shown in the image below:

4631528

If you want to insert the value 7, you start by adding it to the end of the heap. Internally, that means you’re appending it to the end of the list:

46315287

The problem, though, is that this is a max-heap, and the 7 is violating the rules of a max-heap. It needs to be on a higher priority level.

The procedure for moving a node to a higher level is called sifting up. What you do is compare the node in question to its parent. If the node is larger, then you swap the value with that of its parent. You continue swapping with the next parent up until the value is no longer larger than its parent. At that point, the sifting is finished and order has returned to the universe…or at least to your heap anyway.

Take a look at this in action in the following image. First you compare 7 with its parent 4. Since this is a max-heap and 7 is larger than 4, you need to swap the values:

8463715284637152

The next parent up is 6. Since 7 is also larger than 6, swap those two values:

8463715284637152

The final parent is 8, but since 8 is larger than 7, you leave the 7 where it is. The sifting is finished.

8457631284756312

Your heap now satisfies the max-heap property.

Implementing insert¶

Now that you’ve got the theory, it’s time to implement it in code. Add the following two methods to Heap:

void insert(E value) {
  // 1
  elements.add(value);
  // 2
  _siftUp(elements.length - 1);
}

void _siftUp(int index) {
  var child = index;
  var parent = _parentIndex(child);
  // 3
  while (child > 0 && child == _higherPriority(child, parent)) {
    _swapValues(child, parent);
    child = parent;
    parent = _parentIndex(child);
  }
}

The implementation is pretty straightforward:

First you add the value that you want to insert to the end of the elements list.
Then you start the sifting procedure using the index of the value you just added.
As long as that value has a higher priority than its parent, then you keep swapping it with the next parent value. Since you’re only concerned about priority, this will sift larger values up in a max-heap and smaller values up in a min-heap.

The overall complexity of insert is O(log n). Adding an element to a list takes only O(1) while sifting elements up in a heap takes O(log n).

That’s all there is to inserting an element in a heap.

Making the Heap Printable¶

It’s time to try out your handiwork, but before you do, override the toString method of Heap so that it’s a little easier to observe what’s happening:

@override
String toString() => elements.toString();

That will show the raw list, which is good enough for now, but feel free to implement something that looks more like a binary tree.

Testing Insertion Out¶

Replace the contents of bin/starter.dart with the following code:

import 'package:starter/heap.dart';

void main() {
  final heap = Heap<int>();
  heap.insert(8);
  heap.insert(6);
  heap.insert(5);
  heap.insert(4);
  heap.insert(3);
  heap.insert(2);
  heap.insert(1);
  print(heap);
}

These inserts don’t require sifting since you inserted them in max-heap order.

Run that and you should see the output below in the console:

[8, 6, 5, 4, 3, 2, 1]

This list corresponds to the image you saw earlier:

4631528

Now add the following two lines at the bottom of main and run the code again:

heap.insert(7);
print(heap);

This time adding the 7 does require the internal sifting. Run the code again and the final line in the console output will be the following:

[8, 7, 5, 6, 3, 2, 1, 4]

Your code moved 7 to its appropriate location. The list above corresponds with the following heap:

84576312

Success!

Removing From a Heap¶

A basic remove operation removes the root node from the heap.

Take the following max-heap as an example. The root node that you want to remove has a value of 10.

483610152

In order to perform the remove operation, you must first swap the root node with the last element in the heap. In this case, since the last node has a value of 3, you swap the 10 and the 3.

486315210

Once you’ve swapped the two elements, you can remove the last one:

486315210

Now, you must check the max-heap’s integrity. Ask yourself, “Is it still a max-heap?” Remember, the rule for a max-heap is that the value of every parent node must be larger than or equal to the values of its children. If not, you must sift down.

To sift down, you start from the current value and check its left and right child. If one of the children has a value that’s greater than the current value, you swap it with the parent. If both children have a greater value, you swap the parent with the larger of the two children. You continue to sift down until the node’s value is no longer larger than the values of its children.

In this case, both 8 and 5 are greater than 3, so you choose the larger left child 8 and swap it with the 3:

46315284631528

Now compare the 3 with its two new children, 4 and 6. Since 6 is the largest, swap the 3 with that one.

41526431526838

Once you reach the end, you’re done, and the max-heap property has been restored!

4631528

Implementing a Down Sift¶

Go back to lib/heap.dart and add a method to Heap to handle sifting down:

void _siftDown(int index) {
  // 1
  var parent = index;
  while (true) {
    // 2
    final left = _leftChildIndex(parent);
    final right = _rightChildIndex(parent);
    // 3
    var chosen = _higherPriority(left, parent);
    // 4
    chosen = _higherPriority(right, chosen);
    // 5
    if (chosen == parent) return;
    // 6
    _swapValues(parent, chosen);
    parent = chosen;
  }
}

_siftDown accepts an arbitrary index. The node in this index will always be treated as the parent node. Here’s how the method works:

Store the parent index to keep track of where you are in the traversal.
Find the indices of the parent’s left and right children.
The chosen variable is used to keep track of which index to swap with the parent. If there’s a left child, and it has a higher priority than its parent, make it the chosen one.
If there’s a right child, and it has an even greater priority, it will become the chosen one instead.
If chosen is still parent, then no more sifting is required.
Otherwise, swap chosen with parent, set it as the new parent, and continue sifting.

Implementing remove¶

Now that you have a way to sift down, add the remove method to Heap:

E? remove() {
  if (isEmpty) return null;
  // 1
  _swapValues(0, elements.length - 1);
  // 2
  final value = elements.removeLast();
  // 3
  _siftDown(0);
  return value;
}

Here’s how this method works:

Swap the root with the last element in the heap.
Before removing it from the list, save a copy so that you can return the value at the end of the method.
The heap may not be a max- or min-heap anymore, so you must perform a down sift to make sure it conforms to the rules.

The overall complexity of remove is O(log n). Swapping elements in a list is only O(1) while sifting elements down in a heap takes O(log n) time.

Testing remove¶

Go back to bin/starter.dart and replace the body of main with the following:

final heap = Heap<int>();
heap.insert(10);
heap.insert(8);
heap.insert(5);
heap.insert(4);
heap.insert(6);
heap.insert(2);
heap.insert(1);
heap.insert(3);

final root = heap.remove();
print(root);
print(heap);

Run that to see the results below:

10
[8, 6, 5, 4, 3, 2, 1]

This removes 10 from the top of the heap and then performs a down sift that results in 8 being the new root.

You’re now able to remove the root element, but what if you want to delete any arbitrary element from the heap? You’ll handle that next.

Removing From an Arbitrary Index¶

Add the following method to Heap:

E? removeAt(int index) {
  final lastIndex = elements.length - 1;
  // 1
  if (index < 0 || index > lastIndex) {
    return null;
  }
  // 2
  if (index == lastIndex) {
    return elements.removeLast();
  }
  // 3
  _swapValues(index, lastIndex);
  final value = elements.removeLast();
  // 4
  _siftDown(index);
  _siftUp(index);
  return value;
}

To remove an arbitrary element from the heap, you need an index. Given that, here’s what happens next:

Check to see if the index is within the bounds of the list. If not, return null.
If you’re removing the last element in the heap, you don’t need to do anything special. Simply remove it and return the value.
If you’re not removing the last element, first swap the element with the last element. Then, remove the last element, saving its value to return at the end.
Perform a down sift and an up sift to adjust the heap.

But — why do you have to perform both a down sift and an up sift?

Assume you’re trying to remove 5 from the max-heap below. You swap 5 with the last element, which is 8. You now need to perform an up sift to satisfy the max-heap property:

7192110105885972Remove 5Shifting up case

Now, assume you are trying to remove 7 from the heap below. You swap 7 with the last element, 1. In this case, you need to perform a down sift to satisfy the max-heap property.

52571Remove 72107110Shifting down case

Calling _siftDown and _siftUp ensures that both of these situations are handled.

Testing removeAt¶

The code that follows demonstrates the example from the previous image:

final heap = Heap<int>();
heap.insert(10);
heap.insert(7); // remove this
heap.insert(2);
heap.insert(5);
heap.insert(1);

final index = 1;
heap.removeAt(index);
print(heap);

Internally, the value 7 is at index 1. Run that in main to see that removeAt successfully sifts the necessary nodes to give the following heap:

[10, 5, 2, 1]

Removing an arbitrary element from a heap is an O(log n) operation. However, it also requires knowing the index of the element you want to delete. How do you find that index?

Searching for an Element in a Heap¶

To find the index of the element you wish to delete, you need to perform a search on the heap. Unfortunately, heaps are not designed for fast searches. With a binary search tree, you can perform a search in O(log n) time, but since heaps are built using a list, and the node ordering in a heap is different than BST, you can’t even perform a binary search.

Searching for an element in a heap is, in the worst-case, an O(n) operation since you may have to check every element in the list. However, you can optimize the search by taking advantage of the heap’s max or min priority.

Add the following recursive function to Heap:

int indexOf(E value, {int index = 0}) {
  // 1
  if (index >= elements.length) {
    return -1;
  }
  // 2
  if (_firstHasHigherPriority(value, elements[index])) {
    return -1;
  }
  // 3
  if (value == elements[index]) {
    return index;
  }
  // 4
  final left = indexOf(value, index: _leftChildIndex(index));
  if (left != -1) return left;
  return indexOf(value, index: _rightChildIndex(index));
}

Here’s what’s happening:

If the index is too big, the search failed. Return -1. Alternatively, you could rewrite the method to return null, but -1 is what List uses in its indexOf method.
This step is the optimization part. Check to see if the value you’re looking for has a higher priority than the current node at your recursive traversal of the tree. If it does, the value you’re looking for cannot possibly be lower in the heap. For example, if you’re looking for 10 in a max-heap, but the current node has a value of 9, there’s no use checking all the nodes below 9 because they’re just going to be even lower.
If the value you’re looking for is equal to the value at index, you found it. Return index.
Recursively search for the value starting from the left child and then on to the right child. If both searches fail, the whole search fails. Return -1.

Testing it Out¶

Go back to bin/starter.dart and replace the body of main with the following:

final heap = Heap<int>();
heap.insert(10);
heap.insert(7);
heap.insert(2);
heap.insert(5);
heap.insert(1);
print(heap);

final index = heap.indexOf(7);
print(index);

This code attempts to find the index of the value 7.

Run the code and you should see the output below:

[10, 7, 2, 5, 1]
1

The index was correctly recognized as 1.

Accepting a List in the Constructor¶

You may recall that when you made the Heap constructor, it took a list of elements as an optional parameter. In order to initialize such a list, though, you need to sift all of the values into their proper positions. Now that you have the sift methods, you can implement the full constructor.

Replace the current Heap constructor with the following one:

Heap({List<E>? elements, this.priority = Priority.max}) {
  this.elements = (elements == null) ? [] : elements;
  _buildHeap();
}

void _buildHeap() {
  if (isEmpty) return;
  final start = elements.length ~/ 2 - 1;
  for (var i = start; i >= 0; i--) {
    _siftDown(i);
  }
}

If a non-empty list is provided, you use that as the initial elements for the heap. You loop through the list backwards, starting from the first non-leaf node, and sift all parent nodes down. You loop through only half of the elements because there’s no point in sifting leaf nodes down, only parent nodes.

Note

You might wonder whether you could start at the front of the list and call _siftUp on every element. Well, you’d be right. You could do that. However, it wouldn’t be as efficient. Since the top of the heap has only one node, you’d have to do more work to sift every other node toward this position. And when sifting is required, the nodes are more likely to have to travel further. The bottom of the heap, on the other hand, holds half of the nodes already, and it doesn’t take so much work to sift the relatively fewer number of nodes above them down. In Big O notation, although a single up or down sift is O(log n), building a heap using the up-sift algorithm has a time complexity of O(n log n), while building it with the down-sift algorithm has a time complexity of only O(n). Read stackoverflow.com/a/18742428 for a more in-depth explanation.

Testing it Out¶

Time to try your new constructor out. Add the following to main:

var heap = Heap(elements: [1, 12, 3, 4, 1, 6, 8, 7]);
print(heap);

while (!heap.isEmpty) {
  print(heap.remove());
}

The constructor creates a max-heap from the elements of the list. Then the while loop repeatedly removes the largest element until none are left. Run that and you should see the following output:

[12, 7, 8, 4, 1, 6, 3, 1]
12
8
7
6
4
3
1
1

Try it again but this time make it a min-heap. Replace the first line in the code block above with the following:

var heap = Heap(
  elements: [1, 12, 3, 4, 1, 6, 8, 7],
  priority: Priority.min,
);

This time you should see the opposite result:

[1, 1, 3, 4, 12, 6, 8, 7]
1
1
3
4
6
7
8
12

Challenges¶

Think you have a handle on heaps? Try out the following challenges. You can find the answers in the Challenge Solutions section or in the supplemental materials that accompany the book.

Challenge 1: Find the Nth Smallest Integer¶

Write a function to find the nth smallest integer in an unsorted list. For example, given the following list:

final integers = [3, 10, 18, 5, 21, 100];

If n = 3, the result should be 10.

Challenge 2: Step-by-Step Diagram¶

Given the following unsorted list, visually construct a min-heap. Provide a step-by-step diagram of how the min-heap is formed.

[21, 10, 18, 5, 3, 100, 1]

Challenge 3: Combining Two Heaps¶

Write a method that combines two heaps.

Challenge 4: Is it a Min-Heap?¶

Write a function to check if a given list is a min-heap.

Key Points¶

The heap data structure is good for maintaining the highest- or lowest-priority element.
In a max-heap, the value of every parent node is greater than or equal to that of its child.
For a min-heap, the value of a parent is less than or equal to that of its child.
Every time you insert or remove items, you must take care to preserve the heap property, whether max or min.
There can’t be any holes in a heap. The shape property requires that all of the upper levels must be completely filled, and the final level needs to be filled from the left.
Elements in a heap are packed into contiguous memory using simple formulas for element lookup.
Here is a summary of the algorithmic complexity of the heap operations you implemented in this chapter:

OperationsTime Complexityremove0(log n)insert0(log n)search0(n)peek0(1)Heap Data StructureHeap operation time complexity