跳转至

14 Chapter 14 Solutions

Solution to Challenge 1

Start with the following Person type:

class Person extends Comparable<Person> {
  Person({
    required this.name,
    required this.age,
    required this.isMilitary,
  });

  final String name;
  final int age;
  final bool isMilitary;

  @override
  int compareTo(other) => throw UnimplementedError();
}

Since a priority queue needs to compare elements, Person also needs to be Comparable.

Given a list of people on the waitlist, you would like to prioritize the people in the following order:

  1. Military background
  2. Seniority, by age

The key to solving this problem is to finish implementing the compareTo method in Person so that you can use a priority queue to tell you the order of people on the waitlist. Replace compareTo with the following code:

@override
int compareTo(other) {
  if (isMilitary == other.isMilitary) {
    return age.compareTo(other.age);
  }
  return isMilitary ? 1 : -1;
}

If two people have the same military background, then age is used to see who has the highest priority. But if the military background is different, then the one having a military background is prioritized.

Before you test your implementation out, override toString so that Person is printable:

@override
String toString() {
  final military = (isMilitary) ? ', (military)' : '';
  return '$name, age $age$military';
}

Import the PriorityQueue that you made earlier in the chapter if you haven’t already. Then run the following example in main:

final p1 = Person(name: 'Josh', age: 21, isMilitary: true);
final p2 = Person(name: 'Jake', age: 22, isMilitary: true);
final p3 = Person(name: 'Clay', age: 28, isMilitary: false);
final p4 = Person(name: 'Cindy', age: 28, isMilitary: false);
final p5 = Person(name: 'Sabrina', age: 30, isMilitary: false);

final waitlist = [p1, p2, p3, p4, p5];

var priorityQueue = PriorityQueue(elements: waitlist);
while (!priorityQueue.isEmpty) {
  print(priorityQueue.dequeue());
}

You should see the output below:

Jake, age 22, (military)
Josh, age 21, (military)
Sabrina, age 30
Clay, age 28
Cindy, age 28

Solution to Challenge 2

To make a list-based priority queue, all you have to do is implement the Queue interface. Instead of using a heap, though, you use a list data structure.

Here’s the Queue interface that you’ve used previously:

abstract class Queue<E> {
  bool enqueue(E element);
  E? dequeue();
  bool get isEmpty;
  E? get peek;
}

Getting Started

First, add the following code to a project that contains the Queue interface:

enum Priority { max, min }

class PriorityQueueList<E extends Comparable<dynamic>> implements Queue<E> {
  PriorityQueueList({List<E>? elements, Priority priority = Priority.max}) {
    _priority = priority;
    _elements = elements ?? [];
  }

  late List<E> _elements;
  late Priority _priority;

  // more to come
}

So far this is nearly the same as your heap implementation. This time, though, you have a list.

Which Is the High Priority End?

At this point you need to make a decision. You can either put the high priority elements at the start of the list or at the end of the list.

It might seem logical to put the high priority elements at the start of the list since that’s how you implemented heap. However, think about the properties of a list and what you need to accomplish in a queue. Inserting and removing from the beginning of a list is slow. If you make the start of the list the high priority end, then every single dequeue will be slow. On the other hand, if you put the high priority elements at the end of the list, then dequeuing will be a lightning-fast removeLast operation. Enqueuing will be slow no matter what you choose, but you might as well make dequeuing fast!

The code in the rest of this answer will assume that the end of the list is the high priority side.

Sorting an Initial List

Replace the PriorityQueueList constructor with the following code:

PriorityQueueList({List<E>? elements, Priority priority = Priority.max}) {
  _priority = priority;
  _elements = elements ?? [];
  _elements.sort((a, b) => _compareByPriority(a, b));
}

int _compareByPriority(E a, E b) {
  if (_priority == Priority.max) {
    return a.compareTo(b);
  }
  return b.compareTo(a);
}

_compareByPriority returns an int following the requirements of the list’s sort function. Just like you’ve seen before with Comparable values, a comparison result of 1 means the first value is larger, -1 means the second is larger, and 0 means they’re equal. The sort algorithm in Dart has a time complexity of O(n log n) for large lists.

Implementing isEmpty and peek

Add the following methods to begin implementing the Queue interface:

@override
bool get isEmpty => _elements.isEmpty;

@override
E? get peek => (isEmpty) ? null : _elements.last;

Since the high priority side is the end of the list, peeking returns the last element.

Implementing enqueue

Next, add the enqueue method:

@override
bool enqueue(E element) {
  // 1
  for (int i = 0; i < _elements.length; i++) {
    // 2
    if (_compareByPriority(element, _elements[i]) < 0) {
      // 3
      _elements.insert(i, element);
      return true;
    }
  }
  // 4
  _elements.add(element);
  return true;
}

To enqueue an element in a list-based priority queue, perform the following tasks:

  1. Start at the low priority end of the list and loop through every element.
  2. Check to see if the element you’re adding has an even lower priority than the current element.
  3. If it does, insert the new element at the current index.
  4. If you get to the end of the list, that means every other element was lower priority. Add the new element to the end of the list as the new highest priority element.

This method has an overall time complexity of O(n) since you have to go through every element to check the priority against the new element you’re adding. Also, if you’re inserting in between elements in the list, you have to shift all of the remaining elements to the right by one.

Note

Since you’re working with a sorted list, you could improve the efficiency of this algorithm by using the binary search that you learned about in Chapter 12. Insertion would still be O(n) in the worst case, but at least the search part would be O(log n).

Implementing dequeue

Next add the dequeue method:

@override
E? dequeue() => isEmpty ? null : _elements.removeLast();

Here is where the benefit of putting the high priority elements at the end of the list comes in. removeLast is O(1) since you don’t have to shift anything, so that makes dequeue also O(1). That’s even better than the heap implementation!

Making the Queue Printable

Finally, override toString so that you can print your priority queue in a friendly format:

@override
String toString() => _elements.toString();

Alternatively, if you wanted to hide the fact that the high-priority items are at the end, then you could reverse the list with _elements.reversed.

There you have it! A list-based priority queue.

Testing it Out

To test out the priority queue, run the following in main:

final priorityQueue = PriorityQueueList(
  elements: [1, 12, 3, 4, 1, 6, 8, 7],
);
print(priorityQueue);
priorityQueue.enqueue(5);
priorityQueue.enqueue(0);
priorityQueue.enqueue(10);
print(priorityQueue);
while (!priorityQueue.isEmpty) {
  print(priorityQueue.dequeue());
}

You should see the output below:

[1, 1, 3, 4, 6, 7, 8, 12]
[0, 1, 1, 3, 4, 5, 6, 7, 8, 10, 12]
12
10
8
7
6
5
4
3
1
1
0

This challenge was an exercise in implementing an interface from scratch. However, because of the slowness of enqueuing elements, you probably wouldn’t want to use your PriorityQueueList in a real project. The heap implementation performs better overall. On the other hand, if you have an application where you need dequeuing to be O(1) and you don’t care about enqueuing time, the list-based implementation might be the better choice.