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 accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

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 accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now