Chapters
Chapters

Chapters

Hide chapters

Data Structures & Algorithms in Swift

Third Edition · iOS 13 · Swift 5.1 · Xcode 11

Before You Begin

Section 0: 3 chapters
Show chapters Hide chapters

Section I: Introduction

Section 1: 3 chapters
Show chapters Hide chapters

Section II: Elementary Data Structures

Section 2: 6 chapters
Show chapters Hide chapters

Section III: Trees

Section 3: 16 chapters
Show chapters Hide chapters

Section IV: Sorting Algorithms

Section 4: 10 chapters
Show chapters Hide chapters

Section V: Graphs

Section 5: 11 chapters
Show chapters Hide chapters

22. The Heap Data Structure
Written by Vincent Ngo

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

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
Xgerxevv ok kupa

Shifting down case
Zhicgudc potz varu

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
Jead ukuvuqeus rava vurktizasr

21. Binary Search Challenges
23. Heap Data Structure Challenges
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.
© 2024 Kodeco Inc.

You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now