Home iOS & Swift Books Data Structures & Algorithms in Swift

22
The Heap Data Structure Written by Vincent Ngo

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

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.

Heap applications

Some useful applications of a heap include:

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
  }
}

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:

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
}

Removing from a heap

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

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
}
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
  }
}

Inserting into a heap

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

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)
  }
}

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
  }
}
Shifting up case
Wmilboxc ig yexi

Shifting down case
Npahxasj nuxq gavi

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.

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
}

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)
    }
  }
}

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()!)
}
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:
Heap operation time complexity
Jeid ohavevoan qoxa xejvbuhegv

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.

Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below:

© 2021 Razeware LLC

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.