Chapters

Hide chapters

Data Structures & Algorithms in Dart

First Edition · Flutter · Dart 2.15 · VS Code 1.63

Section VI: Challenge Solutions

Section 6: 20 chapters
Show chapters Hide chapters

13. Chapter 13 Solutions
Written by Jonathan Sande & Vincent Ngo

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

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]
9 3 72 3 016 19 18 5 5 62 62 154 1 82 4 59 3 17 627 0 16

2 34 1 36 964 33 6 98 9 0 54 1 77 006 8 01 0 75 632 15 3

Solution to Challenge 3

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

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

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.

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;
}
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now