22. Heaps

Written by Vincent Ngo

Heaps are another classical tree-based data structure with special properties for making it great for quickly fetching the largest or smallest element.

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

What is a heap?

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

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 are studying here.

Heaps come in two flavors:

1. Max heap, in which elements with a higher value have a higher priority.
2. 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 invariant or 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.

Another essential property of a heap is that it is a nearly complete binary tree. This means that every level must be filled, except for the last level. It’s like a video game wherein you can’t go to the next level until you have completed the current one.

Heap applications

Some practical applications of a heap include:

• Calculating the minimum or maximum element of a collection.
• Heapsort.
• Constructing a priority queue.
• Constructing graph algorithms, like Prim’s or Dijkstra’s, with a priority queue.

Note: You will learn about priority queues in Chapter 24, heap sort in Chapter 32, and Dijkstra’s and Prim’s algorithms in Chapter 42 and 44, respectively.

Common heap operations

Open the empty starter playground for this chapter. Start by defining the following basic Heap type:

struct Heap<Element: Equatable> {

  var elements: [Element] = []
  let sort: (Element, Element) -> Bool

  init(sort: @escaping (Element, Element) -> Bool) {
    self.sort = sort
  }
}

This type contains an array to hold the elements in a heap and a sort function that defines how the heap should be ordered. By passing an appropriate function in the initializer, this type can create both min and max heaps.

How do you represent a heap?

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 indeed binary trees, but they can be represented with a simple array. This representation 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, as the elements in a heap are all stored together in memory. You will see later on that swapping elements will play a big part in heap operations. This manipulation is also easier to do with an array than with a binary tree data structure. Take a look at how you can represent a heap using an array. Take the following binary heap:

To represent the heap above as an array, you iterate through each element level-by-level from left to right.

Your traversal looks something like this:

As you go up a level, you’ll have twice as many nodes than in the level before.

It’s now easy to access any node in the heap. You can compare this to how you’d access elements in an array: Instead of traversing down the left or right branch, you can access the node in your array 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.

You might want to obtain the parent of a node. You can solve for i in this case. Given a child node at index i, this child’s parent node can be found at index floor( (i - 1) / 2).

Note: Traversing down an actual binary tree to get the left and right child of a node is a O(log n) operation. That same operation is just O(1) in a random-access data structure, such as an array.

Next, use your new knowledge to add some properties and convenience methods to Heap:

var isEmpty: Bool {
  elements.isEmpty
}

var count: Int {
  elements.count
}

func peek() -> Element? {
  elements.first
}

func leftChildIndex(ofParentAt index: Int) -> Int {
  (2 * index) + 1
}

func rightChildIndex(ofParentAt index: Int) -> Int {
  (2 * index) + 2
}

func parentIndex(ofChildAt index: Int) -> Int {
  (index - 1) / 2
}

Now that you have a good understanding of how to represent a heap using an array, you’ll look at some important operations of a heap.

Removing from a heap

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

Take the following max heap:

A remove operation will remove the maximum value at the root node. To do so, you must first swap the root node with the last element in the heap.

Once you’ve swapped the two elements, you can remove the last element and store its value so you can later return it.

Now, you must check the max heap’s integrity. But first, 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. Since the heap no longer follows this rule, you must perform a sift down.

To perform a sift down, you start from the current value 3 and check its left and right child. If one of the children has a value that is greater than the current value, you swap it with the parent. If both children have a greater value, you swap the parent with the child having the greater value.

Now, you have to continue to sift down until the node’s value is not larger than the values of its children.

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

Implementation of remove

Add the following method to Heap:

mutating func remove() -> Element? {
  guard !isEmpty else { // 1
    return nil
  }
  elements.swapAt(0, count - 1) // 2
  defer {
    siftDown(from: 0) // 4
  }
  return elements.removeLast() // 3
}

Here’s how this method works:

1. Check to see if the heap is empty. If it is, return nil.
2. Swap the root with the last element in the heap.
3. Remove the last element (the maximum or minimum value) and return it.
4. The heap may not be a max or min heap anymore, so you must perform a sift down to make sure it conforms to the rules.

Now, to see how to sift down nodes, add the following method after remove():

mutating func siftDown(from index: Int) {
  var parent = index // 1
  while true { // 2
    let left = leftChildIndex(ofParentAt: parent) // 3
    let right = rightChildIndex(ofParentAt: parent)
    var candidate = parent // 4
    if left < count && sort(elements[left], elements[candidate]) {
      candidate = left // 5
    }
    if right < count && sort(elements[right], elements[candidate]) {
      candidate = right // 6
    }
    if candidate == parent {
      return // 7
    }
    elements.swapAt(parent, candidate) // 8
    parent = candidate
  }
}

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

1. Store the parent index.
2. Continue sifting until you return.
3. Get the parent’s left and right child index.
4. The candidate variable is used to keep track of which index to swap with the parent.
5. If there is a left child, and it has a higher priority than its parent, make it the candidate.
6. If there is a right child, and it has an even greater priority, it will become the candidate instead.
7. If candidate is still parent, you have reached the end, and no more sifting is required.
8. Swap candidate with parent and set it as the new parent to continue sifting.

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

Now how do you add to a heap?

Inserting into a heap

Let’s say you insert a value of 7 to the heap below:

First, you add the value to the end of the heap:

Now, you must check the max heap’s property. Instead of sifting down, you must now sift up since the node that you just inserted might have a higher priority than its parents. This sifting up works much like sifting down by comparing the current node with its parent and swapping them if needed.

Your heap has now satisfied the max heap property!

Implementation of insert

Add the following method to Heap:

mutating func insert(_ element: Element) {
  elements.append(element)
  siftUp(from: elements.count - 1)
}

mutating func siftUp(from index: Int) {
  var child = index
  var parent = parentIndex(ofChildAt: child)
  while child > 0 && sort(elements[child], elements[parent]) {
    elements.swapAt(child, parent)
    child = parent
    parent = parentIndex(ofChildAt: child)
  }
}

As you can see, the implementation is pretty straightforward:

• insert appends the element to the array and then performs a sift up.
• siftUp swaps the current node with its parent, as long as that node has a higher priority than its parent.

Complexity: The overall complexity of insert(_:) is O(log n). Appending an element in an array takes only O(1) while sifting up elements in a heap takes O(log n).

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

You have so far looked at removing the root element from a heap and inserting into a heap. But what if you wanted to remove any arbitrary element from the heap?

Removing from an arbitrary index

Add the following to Heap:

mutating func remove(at index: Int) -> Element? {
  guard index < elements.count else {
    return nil // 1
  }
  if index == elements.count - 1 {
    return elements.removeLast() // 2
  } else {
    elements.swapAt(index, elements.count - 1) // 3
    defer {
      siftDown(from: index) // 5
      siftUp(from: index)
    }
    return elements.removeLast() // 4
  }
}

To remove any element from the heap, you need an index. Let’s go over how this works:

1. Check to see if the index is within the bounds of the array. If not, return nil.
2. If you’re removing the last element in the heap, you don’t need to do anything special. Simply remove and return the element.
3. If you’re not removing the last element, first swap the element with the last element.
4. Then, return and remove the last element.
5. Finally, perform a sift down and a sift up to adjust the heap.

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

Assume you are trying to remove 5. You swap 5 with the last element, which is 8. You now need to perform a sift up to satisfy the max heap property.

Now, assume you are trying to remove 7. You swap 7 with the last element, 1. You now need to perform a sift down to satisfy the max heap property.

Removing an arbitrary element from a heap is an O(log n) operation. But how do you find the index of the element you wish to delete?

Searching for an element in a heap

To find the index of the element you wish to delete, you must 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 an array, and the node ordering in an array is different, you can’t even perform a binary search.

Complexity: To search 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 array:

func index(of element: Element, startingAt i: Int) -> Int? {
  if i >= count {
    return nil // 1
  }
  if sort(element, elements[i]) {
    return nil // 2
  }
  if element == elements[i] {
    return i // 3
  }
  if let j = index(of: element, startingAt: leftChildIndex(ofParentAt: i)) {
    return j // 4
  }
  if let j = index(of: element, startingAt: rightChildIndex(ofParentAt: i)) {
    return j // 5
  }
  return nil // 6
}

Let’s go over this implementation:

1. If the index is greater than or equal to the number of elements in the array, the search failed. Return nil.
2. Check to see if the element you are looking for has higher priority than the current element at index i. If it does, the element you are looking for cannot possibly be lower in the heap.
3. If the element is equal to the element at index i, return i.
4. Recursively search for the element starting from the left child of i.
5. Recursively search for the element starting from the right child of i.
6. If both searches failed, the search failed. Return nil.

Note: Although searching takes O(n) time, you have made an effort to optimize searching by taking advantage of the heap’s property and checking the element’s priority when searching.

Building a heap

You now have all the necessary tools to represent a heap. To wrap up this chapter, you’ll build a heap from an existing array of elements and test it out. Update the initializer of Heap as follows:

init(sort: @escaping (Element, Element) -> Bool,
     elements: [Element] = []) {
  self.sort = sort
  self.elements = elements

  if !elements.isEmpty {
    for i in stride(from: elements.count / 2 - 1, through: 0, by: -1) {
      siftDown(from: i)
    }
  }
}

The initializer now takes an additional parameter. If a non-empty array is provided, you use this as the element for the heap. To satisfy the heap’s property, you loop through the array backward, starting from the first non-leaf node, and sift down all parent nodes. You loop through only half of the elements because there is no point in sifting down leaf nodes, only parent nodes.

Testing

Time to try it out. Add the following to your playground:

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

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

This loop creates a max heap because > is used as the sorting predicate and removes elements one-by-one until it is empty. Notice that the elements are removed from largest to smallest, and the following numbers are printed to the console.

12
8
7
6
4
3
1
1

Key points

• Here is a summary of the algorithmic complexity of the heap operations you implemented in this chapter:

• The heap data structure is good for maintaining the highest- or lowest-priority element.
• Elements in a heap are packed into contiguous memory using a simple formula for element lookup.
• Every time you insert or remove items, you must take care to preserve the heap property of the heap.