Chapters

Hide chapters

Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

23. Heap Challenges
Written by Vincent Ngo

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

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

Think you have a handle on heaps? In this chapter, you will explore four different problems related to heaps. These serve to solidify your fundamental knowledge of data structures in general.

Challenge 1: Find the nth smallest integer

Write a function to find the nth smallest integer in an unsorted array. For example:

let integers = [3, 10, 18, 5, 21, 100]

If n = 3, the result should be 10.

Challenge 2: Step-by-Step diagram

Given the following array, visually construct a min-heap. Provide a step-by-step diagram of how the min-heap is constructed.

[21, 10, 18, 5, 3, 100, 1]

Challenge 3: Combining two heaps

Write a method that combines two heaps.

Challenge 4: A Min Heap?

Write a function to check if a given array is a min-heap.

Solutions

Solution to Challenge 1

There are many ways to solve for the nth smallest integer in an unsorted array. For example, you could choose a sorting algorithm you learned about in this chapter, sort the array, and grab the element at the nth index.

func getNthSmallestElement(n: Int, elements: [Int]) -> Int? {
  var heap = Heap(sort: <, elements: elements) // 1
  var current = 1 // 2
  while !heap.isEmpty { // 3
    let element = heap.remove() // 4
    if current == n { // 5
      return element
    }
    current += 1 // 6
  }
  return nil // 7
}

Solution to Challenge 2

[21, 10, 18, 5, 3, 100, 1]

5 3 10 1 100 18 21 5 3 10 18 100 1 21 5 10 3 18 100 1 21

4 97 1 34 372 13 7 62 0 1 35 1 04 517 0 09 3 14 249 59 3

Solution to Challenge 3

Add this as an additional function of Heap.swift:

mutating public func merge(_ heap: Heap) {
  elements = elements + heap.elements
  buildHeap()
}

Solution to Challenge 4

To check if the given array is a min-heap, you only need to go through all the parent nodes of the binary heap. To satisfy the min-heap requirement, every parent node must be less than or equal to its left and right child node.

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

func rightChildIndex(ofParentAt index: Int) -> Int {
  (2 * index) + 2
}
func isMinHeap<Element: Comparable>(elements: [Element]) -> Bool {
  guard !elements.isEmpty else { // 1
    return true
  }
  // 2
  for i in stride(from: elements.count / 2 - 1, through: 0, by: -1) {
    let left = leftChildIndex(ofParentAt: i) // 3
    let right = rightChildIndex(ofParentAt: i)
    if elements[left] < elements[i] { // 4
      return false
    }
    if right < elements.count && elements[right] < elements[i]  { // 5
      return false
    }
  }
  return true // 6
}
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