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

14. Priority Queues
Written by Vincent Ngo & Jonathan Sande

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

Queues are simply lists that maintain the order of elements using first-in-first-out (FIFO) ordering. A priority queue is another version of a queue in which elements are dequeued in priority order instead of FIFO order.

A priority queue can be either of these two:

  1. Max-priority, in which the element at the front is always the largest.
  2. Min-priority, in which the element at the front is always the smallest.

You’ll notice the similarity here to the heap data structure that you made in the last chapter. In fact, in this chapter you’ll implement a priority queue using a heap. A priority queue creates a layer of abstraction by focusing on the key operations of a queue and leaving out the additional functionality provided by a heap. This makes the priority queue’s intent clear and concise. Its only job is to enqueue and dequeue elements, nothing else. Simplicity for the win!

Applications

Some practical applications of a priority queue include:

  • Dijkstra’s algorithm, which uses a priority queue to calculate the minimum cost.
  • A* pathfinding algorithm, which uses a priority queue to track the unexplored routes that will produce the path with the shortest length.
  • Heapsort, which can be implemented using a priority queue.
  • Huffman coding that builds a compression tree. A min-priority queue is used to repeatedly find two nodes with the smallest frequency that do not yet have a parent node.

These are just some of the use cases, but priority queues have many more applications as well.

Common Operations

In Chapter 6, “Queues”, you established the following interface for queues:

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

Implementation

You can create a priority queue in the following ways:

Getting Started

Here’s how to use a heap to create a priority queue.

import 'heap.dart';
import 'queue.dart';

// 1
export 'heap.dart' show Priority;

// 2
class PriorityQueue<E extends Comparable<dynamic>> 
  implements Queue<E> {

  PriorityQueue({
    List<E>? elements,
    Priority priority = Priority.max,
  }) {
    // 3
    _heap = Heap<E>(elements: elements, priority: priority);
  }

  late Heap<E> _heap;

  // more to come
}

Implementing the Queue Interface

To implement the Queue interface, add the following to PriorityQueue:

@override
bool get isEmpty => _heap.isEmpty;

@override
E? get peek => _heap.peek;

// 1
@override
bool enqueue(E element) {
  _heap.insert(element);
  return true;
}

// 2
@override
E? dequeue() => _heap.remove();

Testing it Out

Go to bin/starter.dart and replace the contents of the file with the following code:

import 'package:starter/priority_queue.dart';

void main() {
  var priorityQueue = PriorityQueue(
    elements: [1, 12, 3, 4, 1, 6, 8, 7],
  );
  while (!priorityQueue.isEmpty) {
    print(priorityQueue.dequeue()!);
  }
}
12
8
7
6
4
3
1
1

Challenges

The first challenge below will test your ability to apply the data structure to a practical problem, while the second challenge will give you some more practice implementing a priority queue. As always, you can find the answers in the Challenge Solutions section at the end of the book.

Challenge 1: Prioritize a Waitlist

Your favorite concert was sold out. Fortunately, there’s a waitlist for people who still want to go! However, ticket sales will first prioritize someone with a military background, followed by seniority.

final person = Person(name: 'Josh', age: 21, isMilitary: true);

Challenge 2: List-Based Priority Queue

You’ve learned how to construct a priority queue by implementing the Queue interface with an internal heap data structure. Now your challenge is to do it again, but this time with a List.

Key Points

  • A priority queue is often used to retrieve elements in priority order.
  • A max-priority queue prioritizes the largest elements, while a min-priority queue the smallest.
  • Wrapping a heap with a queue interface allows you to focus on the key operations of a queue while ignoring unneeded heap operations.
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