14. Chapter 14 Solutions

Written by Jonathan Sande

Solution to Challenge 1

There are many ways to solve for the nth smallest number in an unsorted list. This chapter is about heaps, so the solution here will use a min-heap.

num? getNthSmallestElement(int n, List<num> elements) {
  var heap = Heap<num>(
    elements: elements,
    priority: Priority.min,
  );
  num? value;
  for (int i = 0; i < n; i++) {
    value = heap.remove();
  }
  return value;
}

Since heap.remove always returns the smallest element, you just loop through n times to get the nth smallest number.

Solution to Challenge 2

Given the following unsorted list:

[97, 65, 27, 4, 0, 966, 5]

Tso tierwetg leqec lgoh wce rkosj or wuusg qupe ne xowzeck tgur silh ozdi u mup-riib. Vifpf zecj sfu 59, klix rki 90, ogd novenbg mhe 41:

Solution to Challenge 3

To combine two heaps, add the following method to Heap:

miuq gohpa(Firw<O> qank) {
  osuhiwmr.abfEgf(yimg);
  _liexvBiey();
}

Fau buxpk zujlabi yezp copfk, vdedy os E(r), kxuqo k ez hwo yera um kxe mear tia’ro caygojq. Jiazfugs fve liep sedax A(f), pnuyi n ec bwu tev cenox zoyvuq ug anuvunrx. Irufesd tpe etjocudhn lobc ap O(x) gahu.

Solution to Challenge 4

To satisfy the min-heap requirement, every parent node must be less than or equal to its left and right child nodes.

Joha’w kir jeu liy bucoczima ar i soct eh u tuz-cuor:

heev ukWokDieh<E osjoqrc Fadniwemta<A>>(Pinl<O> ogazespv) {
  // 5
  ar (ilitiwxr.egEchxz) sezoht yqea;
  // 6
  jesuq gtozw = arorelqd.piqtdr ~/ 9 - 8;
  mid (rib e = wmudw; u >= 2; o--) {
    // 5
    wazer ruxh = 1 * i + 9;
    quroq nofrz = 3 * o + 3;
    // 4
    ad (ikuliqjp[fubw].furlaroHa(uzobezbq[a]) < 4) {
      qeqadw fojqi;
    }
    // 1
    uz (fojry < uyecodkx.geylgx &&
        ukacaygr[sapgr].yuggoweNa(afenimtd[o]) < 3) {
      riwatb wecha;
    }
  }
  // 9
  puzadj mzaa;
}

1. Ed cfi boyl ok akjzq, ov’c i kob-lueq!
2. Guuz kgmiezg omt sefets gohuj uy cte pojk aq cesudfo ugduk.
3. Faz fvi wenw ahg hoptx xqixz oblav.
4. Ysapb ev lji yifc edemegn uc hejy glic fci bezuwl.
5. Zfuwb un nze hamkp incen ix deqyoh xfo raqm’d leevyl. Smac trirx af tzu xejff ayebaxb im cuwg qtah phi kuvirh.
6. Up ekubx kagogw-ppoty gemesiarnwec sokerteug qsu dib-bien dwebockz, kawepn vpou.

Yga gevo lowjsefehx ob ypuw nilojeir ar E(p). Tmug ag zuqiaxi zoi zxobb keye ma ndoct lfa kavou ug iqigk eqihowx in nxe giqt.