22. The Heap Data Structure

Written by Vincent Ngo

Have you ever been to the arcade and played those crane machines that contain stuffed animals or cool prizes? These machines make it very hard to win. But the fact that you set your eyes on the item you want is the very essence of the heap data structure!

Ever seen the movie Toy Story with the claw and the little green squeaky aliens? Just imagine that the claw machine operates on your heap data structure and will always pick the element with the highest priority. The Claw…

In this chapter, you will focus on creating a heap, and 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 important characteristic that must always be satisfied. This 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 important property of a heap is that it is a 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 useful applications of a heap include:

• Calculating the minimum or maximum element of a collection.
• Heap sort.
• 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 the heap and a sort function that defines how the heap should be ordered. By passing an appropriate function in the initializer, this type can be used to 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 seems 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 the heap are all stored together in memory. You will see later on that swapping elements will play a big part in heap operations. This is also easier to do with an array than with a binary tree data structure. Let’s take a look at how heaps can be represented using an array. Take the following binary heap:

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

Your traversal would look 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 simply access the node in your array using simple formulas.

Given a node at a zero-based index i:

• The left child of this node can be found at index 2i + 1.
• The right child of this node can be found 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. In a random-access data structure, such as an array, that same operation is just O(1).

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 you can represent a heap using an array, you’ll look at some important operations of a heap.

Removing from a heap

A basic remove operation simply 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. This 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 that you know how to remove from the top of the heap, 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 that 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 actually find the index of the element you wish to delete?

Searching for an element in a heap

To find the index of the element that 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 that 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 priority of the element 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 elements for the heap. To satisfy the heap’s property, you loop through the array backwards, 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 creates a max heap (because > is used as the sorting function) and removes elements one-by-one until it is empty. Notice that the elements are removed 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 that you implemented in this chapter:

• The heap data structure is good for maintaining the highest- or lowest-priority element.
• Every time you insert or remove items from the heap, you must check to see if it satisfies the rules of the priority.