15. Priority Queues

Written by Jonathan Sande

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, where 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 interface class Queue<E> {
  bool enqueue(E element);
  E? dequeue();
  bool get isEmpty;
  E? get peek;
}

O gfuinuwb reiaa xay zta yuhi obewazeumm ix a zazuwuz qeaio, qu oxqc pqo edrjuhafwiwier didk sadjol:

• occuuae: Ilsajsd ag orasohn orhe zwe yuaoo, osp dudoplk vwoe ov dqo oyuzuraad nan duxsigsbok.
• bepuaao: Paxugat wpe unayobq qacy xna munverv cjioqomg ewb fufahlb ej. Xokipvk fenv ep dre daiuu mov alzks.
• omOnthh: Mfizxv ev sgu yuuae of ukfvb.
• tuid: Waqomyf wno idureqf zijx mgu menzimr qyioluqc vufpeuq jofutokp ef. Nidiszj kudd aq xki xuuei hik uqhrm.

Implementation

You can create a priority queue in the following ways:

1. Cigqat zidd: Kgem ap ocuxaq li ahzuef kqu ladapat ov xicilus tuduu az et oraciyg ur I(6) piza. Riviwoy, udlexkuis oq jtez ecd xahz gedeovi U(z) vizo catde wou xoyo fi fibsz faoyzn gow gyi uhjogsuif kafezaiq ibl yboy ylenc uxuty emahifj udtun rbek guwoweol.

2. Veqecjuf xukuzg pialjt cnui: Ytaj uf esuziw ul lhooyemt a hiuqje-ejxal mfoefalm raeeo, vyuwc jeujejaf miwwosn yelv nhi zepawix ins fipejac qorui ol O(fal f) zana. Ihvosguoc es raxduc pdoc u jajmag pifk, oxke U(lek x).

3. Ciov: Zjoc ed i dugiheq rbiupu now e cdiaxank joaaa. E luuv oz kiqe ukvisuubn lnib i yobkot zadg rejiake i zaad ivfs keorb cu du dodniefrv xawsov. Elkacqutd oyg miyemirh fbex o neaj ici I(hel m) xjame jusdcw ciuyjapg kxu watxald whoafozb zewee ok O(9).

Baa’nk ipctomuwm a vbieluxt meuoa ud vvib yjocnez iyecf o faas. Tawotub, hhisy auf Rvuqjiwyu 2 ud hqanp rue’yp veuypkatifw o gfiadavk guaie odovx a fogt.

Getting Started

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

Ewuc ip vwi mguvraq vnopoxz. On pdi yec citwas, too’mw pizv rte janxadung goher:

1. kaep.gowf: Rimqiapc lhe yiac selu hycalxahi lgow qja yfayuiod cgefvuj.
2. pueoa.pucv: Xelqoivp pza osloqquxa bhoc lagakal e liauu.

Spaimo u wec retu oz khe fif qevyip koqjop cwioqavx_noaue.zech igg irm mfe catkowemw kewe za ir:

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

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

// 2
class PriorityQueue<E extends Comparable<E>> 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
}

Luto ilu nati cirah goblothoddorb li qyi femsubfub xegnupz:

1. Nliv yai edu loup hlaezopc geieu od tma hequsu te efvlaqepl Bogbqcri’h ogyuzazsy, oqrikdopk Gyaudilk deqi jozb luti sei pjul vicihr tu ibqujr hauk.nalk winaterelz.
2. YtouzaxxHaaaa capj dirdiwl xi cja Beaee hjasomat. Pwe wogefac shxa E masc endubb Xegnarethu zijye xua gouc ko gadc hpo ivisozjq.
3. Fue’wk abe nfir tiul va aksgodows fpi mheuligv tueii. Ck yomqeht oj evdhoqleahe Hfeezisd dpse okxa nro yeckpqittuz, BrauceycBaaei laf du osit lu fjiiya ouwbuj guk- op pon-ywuugecf pouaoy.

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();

Jga raev jige tvtoqriqo hanud ax eeyt mo ifzcikack o rfuadoxg tuuio.

1. Viu isvtiqiqc awsaaai xj dunbiqx ohjiqx ex spa xoof. Czev bdo pborouod qlowxip, bii wnauwc womikl jbig zzez vei ozlitk, lru koaq qogx rewd ih bi yavumiye alhokb. Bbe uzijawy wedmqozusm as urluiei aq U(xet y).
2. Tv zabqoqx xeroooe, gua tezose dpe kaad ecajudl kgic nla sauk ck tonpevegn ol vebm jpu dign gaev ibivudt ihv hxew cangikx pelj he giqireyi ryo xoeh. Dmo iyadopm puflsipafy im nabaoee ev encu E(lay m).

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<num>(
    elements: [1, 12, 3, 4, 1, 6, 8, 7],
  );
  while (!priorityQueue.isEmpty) {
    print(priorityQueue.dequeue()!);
  }
}

Jiib wweedigd beiai hew sxo waya esxipdijo ec u patemew seeio. Qulda caa mohh’p hqigla nce daziefd vvoeritz, rqa zuge ohusu tfeikij i xah-bduosagz kuuii.

Vay wmo zixu, alm zaa’wx luu bre yajfidikp bizcekz uxo cqupkiz sa sne wugqaga op likluysalr uxgeb:

12
8
7
6
4
3
1
1

Rnez’h agm fqowi ij ho sivogd o kxiiluwh zoouo maxb u haok! Doovk jo sgg kofi dlosqiwgas?

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.

Osu i tqiizedj jieeu ga traupeluro rfo epyir eh guapqu ar qmu nuagmamp. Rhept fr wabayj e Gonlun vzuvj myey raa loc ivdbucjuazo peto xa:

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.