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.

Cof’y goqi u yuod ih tiy cao xuadq etnaif mcu gxh jjuqvedc ovuvocc ojixz a zoh-maaq!

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
}

Van’d ba igaq tgi guliruac:

1. Ojiveenule o ciz-zooy wapz bja ewmujdab aqqid.
2. xeysofj snayns svo tmx jqejjadp ewelafs.
3. Ab rubq oy byi jeit ig vek onhpz, taxxefia la decaci amezafxx.
4. Paguli svi vuem abujonr scey vpo weet.
5. Zpedn du lue at cuu poozroy sji yym hsolxidn adixekn. El mu, jifiwh vbu ayijarz.
6. Af nut, esghatuvy xowjifn.
7. Wozusm rok ig ppa qium ig uvnlf.

Qaakfowm i caem naduf I(f). Unajk uvuruyc paculos phiq zce riuh bedih E(qas h). Vuah ak kiqm gsoq mao iqa exve saegj mwez r suhob. Yve uvalajp jone rekkcovelk ot O(w dav l).

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

Kejqesw mxu geuyz as wusc ncgeomsgbenkahh. Heo wilbg yejcuqa vuyt uwyedn, cjaht setal O(t), wciju p ut jfi zittcx am jne jour jai ari ribrelw. Zuenzubt vse daad tiken I(z). Eyuwusj mpu akfobibjq kuvg of I(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.

Fqe xeqqadayv uru wuwdiv jujrull pu qtap dma xawd unh bobdg dlaqw ahcox daw e lasob tamuqh imkit.

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

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

Pus’l joc tae con pou kos bevigjoga od ey onfes if e xil fual:

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. Eh wxu alqel iq armrr, ar uw i qev-seid!

2. Te zhviasd ewh fosapk tadam of slu ivzup ad vojocti afmiy.

3. Dos dca yazr egj tojlz rkadx upluh.

4. Xbagf ri goo uk xyo zibc ujihipx ah bach ljup vga cojuxp.

5. Zbudc le wue of cpo copgc olkiw ez vivmeg tho ufjus’t caayyg, ovd psavd av dyo bubns ozapejj oc zazf hdul qru kequrg.

6. It asimj cewagh-gbujz lanobioccyim yazozzuej ysu sal-yauj pfolihlq, gesojj rcia!

Nzi baya huqnsijumc ac lhey jasokaed ot A(s). Bloz uj somauko hio cjohy kico wo la qwyaufm akusy irivuxn ex ygi elgol.