Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

Before You Begin

Section 0: 6 chapters

Section I: Introduction

Section 1: 3 chapters

Section II: Elementary Data Structures

Section 2: 6 chapters

23. Heap Challenges Written by Vincent Ngo

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]
``````

Solution to Challenge 3

``````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.