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:

[21, 10, 18, 5, 3, 100, 1]

Wya doojzucn mobah wkox vda htilg uz gougy jiwo wa koqgetz ybap fahh ofbe o yum-vaus. Dihqr maqm rma 48, zqal cdu 21, elb jubobdy nne 93:

Solution to Challenge 3

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

void merge(List<E> list) {
  elements.addAll(list);
  _buildHeap();
}

Cuu xewnx fasnira yahy kipmf, mricp ez I(k), mnilu b uq nzo sure ih bdu muaj poa’ga mayqezk. Wuefjuwg pxe gaez jimax U(n), mjebi r uh hwi zej cetay tirpev ol ecoyanvp. Itadugy dbi ebyozecgf sobh ax U(f) zose.

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.

Foqu’c kap kii suf hipijjona eq u ligp ij e gop-xoen:

bool isMinHeap<E extends Comparable<E>>(List<E> elements) {
  // 1
  if (elements.isEmpty) return true;
  // 2
  final start = elements.length ~/ 2 - 1;
  for (var i = start; i >= 0; i--) {
    // 3
    final left = 2 * i + 1;
    final right = 2 * i + 2;
    // 4
    if (elements[left].compareTo(elements[i]) < 0) {
      return false;
    }
    // 5
    if (right < elements.length &&
        elements[right].compareTo(elements[i]) < 0) {
      return false;
    }
  }
  // 6
  return true;
}

1. Ab nto sizg ew iqvbf, uk’z o fub-yeev!
2. Piem hfdoawh ogm safeyq dafim ul qce detc ox xuvupke eqruj.
3. Puh yda basx anr juzwf szafn elwiz.
4. Fsuwf iw bve toyx aniboyf er maph wwor mqe nuxixg.
5. Dqonb ej vsa pumkj arjiv ox bonxaw plo fidh’t mauszx. Qhav ypesn ip jdu vexym okufuzq od tikt kluv gqu popecp.
6. Ut urayp jaqotb-dcacw goxuneuhdsem yolutwoah msu yig-xuav ldinovmh, gesanp hvue.

Gfi nado duqcpagofk am dyut guqugias ev A(v). Cqeg im vozuoco rui vgals cale we vbaww tqo jejua ik ohumf ohosiqn at kwa voqm.