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.

Let’s take a look at how you would obtain the nth smallest element using a min-heap!

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
}

Let’s go over the solution:

1. Initialize a min-heap with the unsorted array.
2. current tracks the nth smallest element.
3. As long as the heap is not empty, continue to remove elements.
4. Remove the root element from the heap.
5. Check to see if you reached the nth smallest element. If so, return the element.
6. If not, increment current.
7. Return nil if the heap is empty.

Building a heap takes O(n). Every element removal from the heap takes O(log n). Keep in mind that you are also doing this n times. The overall time complexity is O(n log n).

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()
}

Merging two heaps is very straightforward. You first combine both arrays, which takes O(m), where m is the length of the heap you are merging. Building the heap takes O(n). Overall the algorithm runs in O(n).

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.

The following are helper methods to grab the left and right child index for a given parent index.

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

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

Let’s now see how you can determine if an array is a min heap:

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
}

1. If the array is empty, it is a min-heap!

2. Go through all parent nodes in the array in reverse order.

3. Get the left and right child index.

4. Check to see if the left element is less than the parent.

5. Check to see if the right index is within the array’s bounds, and check if the right element is less than the parent.

6. If every parent-child relationship satisfies the min-heap property, return true!

The time complexity of this solution is O(n). This is because you still have to go through every element in the array.