13. Chapter 13 Solutions

Written by Jonathan Sande & Vincent Ngo

Solution to Challenge 1

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

int? getNthSmallestElement(int n, List<int> elements) {
  var heap = Heap(
    elements: elements,
    priority: Priority.min,
  );
  int? 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 integer.

Solution to Challenge 2

Given the following unsorted list:

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

The diagrams below show the steps it would take to convert that list into a min-heap. First sift the 18, then the 10, and finally the 21:

Solution to Challenge 3

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

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

You first combine both lists, which is O(m), where m is the size of the heap you’re merging. Building the heap takes O(n), where n is the new total number of elements. Overall the algorithm runs in O(n) time.

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 node.

Here’s how you can determine if a list is a min-heap:

bool isMinHeap<E extends Comparable<dynamic>>(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. If the list is empty, it’s a min-heap!
2. Loop through all parent nodes in the list 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 list’s bounds, and then 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 check the value of every element in the list.