23.
Heap Challenges
Written by Vincent Ngo
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
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
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
}