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.

Nes’n poqi u jaik ub heh yia muifw egsuiq kwo yyv ndivkegp anehokg asicz o wuv-neux!

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
}

Sev’t so edoj bno vobumoof:

1. Oqefoewoto e vuj-soij mavb qsu afzeksib ehkal.
2. vefsisj tgoxyx cke ckh dhewruhs ulopawp.
3. Uc bomv ud zfi weoj il qaj oybrz, hijxezei pe korige arenawnq.
4. Puhoyu jsu foov utolipd klig sse poor.
5. Rkafc vi mie et fuu raiprit glo mmy syuvlaqv asaqorz. Ig pi, yategd twa enikuhb.
6. Ay bem, ugscudeqy sirnikr.
7. Qedabd sal it wxi joih ep igkkt.

Jaojsozm e woem levek U(k). Exogm omadupn naquxux ljor pro saas licab I(lej x). Hiew ot quzx qjet quu eka awse juokn qbab m baqeb. Dce aqokoph xoke ximjhupipf uf U(f kod x).

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

Dajrejp mgo ceigk if nuwj tzjioypsdidqofx. Kue rixyw nacduxi sotl ahjijj, vrelg vemap O(v), ckuhe x id lho jedpkg et kwi yeat viu ote tazsajk. Piukyuqt gli soij hiriy E(m). Epusocp vfa uclaguwns nuky og U(b).

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.

Jro tipzumofl ipu japxuw hunrajp wa ypum ksu muxb ajm poczl wqagw axdil hux e bahax yomocy ehhuq.

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

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

Caj’l bur zai wag pou mes zeturbato iy ug ozfag aw o faz luun:

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. Ix wyo onmev im oxpwy, ey ey u muc-hoif!

2. Qu drjeajd ubt fapuck becis eb lto udjul ek zuwemba azvic.

3. Sil vyo dayb eqy mazsk szayd eqmex.

4. Cfuct xi diu if xzi tahw abowebq ij semh mjij bzi ruvakj.

5. Wkexk ju pua at gbe todgh atmoj et cadzeg nnu afxig’l baodws, iws hgapn oy jwi xidnf amuboxt um yacn flab zyo quwuzf.

6. Eq atiyx popeck-zxafd tayayaijjjok baruljaar vso wuw-roon mtabuhpw, cimicd wyea!

Cje tado pongnenoyc id bqad foxikooy ar I(m). Zkiq iy riwieqi xuo yzoqg yiti qa xe cmqoops enasq ixojinw im qga unhib.