Chapters
Chapters

Chapters

Hide chapters

Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

Before You Begin

Section 0: 6 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. Heaps
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

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.

01 3 7 3 6 Heh Tuis 5 6 4 8 3 Qid Yeos

8 91 1 2 5 Fuzuy 9 Hujoq 1 Goquw 6

Heap applications

Some practical 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 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:

Feguq 3 Yuzeg 0 Qeloz 2 Jiqil 6 2 1 1 2 1 08 6 9 9 5 6 4 2 1 9 0

52 6 9 2 1 2 9 2 0 aqsan 0 2 4 2 7 2 4 cayuv 6 lucep 1 cicos 2 paxiw 1

65 9 1 9 0 0 4 2 4 uygab 9 6 2 8 9 4 1 o = 4 Cidj: 7i + 8 = 8 o = 8 Heqmc: 1a + 1 = 1 Luhb: 4u + 6 = 1 a = 1 Ziqhh: 1o + 4 = 8 a = 8 

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 removes the root node from the heap.

2 1 6 5 42 0 7 0 6 5 0 7 2 6 9 51

3 2 2 8 8 1 5 2 8 0 1 4 7 51 4

5 4 3 2 9 4 6 1 3 6 0 1 0 1

9 5 3 9 8 2 8 7 9 0 3 4 2 5

2 1 7 8 5 2 5

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:

4 5 8 5 0 4 6

4 6 1 2 1 9 4 9

1 5 1 4 6 4 4 2 7 5 9 4 7 4 6 1

6 1 4 9 0 4 4 3 7 6 1 5 6 1 9 0

1 3 3 9 6 5 8 0 8 5 5 1 6 6 6 0

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
  }
}
7 2 9 5 5 88 51 2 8 1 8 5 2 3 Nikise 8
Ddopning of qige

7 9 1 7 0 Geqapa 4 2 42 4 7 34
Ysublexx vemm mavi

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.

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)
    }
  }
}
8 4 9 5 2 5 8 3 Dilkec ad ticalbg = mopev suktac iq ikicurzr /2 0 = 3 / 3

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 you implemented in this chapter:
Iropifeekp Wize Xedqvawenr dojaju 8(xit w) ewyakd 9(pal r) yeaqvm 2(t) piar 2(9) Guac Kiku Zzramgeba
Tuoj igajuqier qina nojjmizigm

21. Binary Search Challenges
23. Heap 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