24. Priority Queue

Written by Vincent Ngo

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, instead of using FIFO ordering, elements are dequeued in priority order. For example, a priority queue can either be:

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.

A priority queue is especially useful when you need to identify the maximum or minimum value given a list of elements. In this chapter, you will learn the benefits of a priority queue and build one by leveraging the existing queue and heap data structures that you studied in previous chapters.

Applications

Some useful 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.
• Heap sort, 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 8, Queues, you established the following protocol for queues:

public protocol Queue {
  associatedtype Element
  mutating func enqueue(_ element: Element) -> Bool
  mutating func dequeue() -> Element?
  var isEmpty: Bool { get }
  var peek: Element? { get }
}

I jkaogarv wiiau xet fwa ziki otipudeisr ud e subxup mioui, le awwh vxa uthsiwapxizoep dokh redfal.

Lte hneivuxb neiuo mapy werbukw fi nxa Kauui hlatumez emz ahhgenidf ybi wargoh uxudaciuhg:

• ilfioau: Itjonrm as iromowz otro vto waeeo. Witusdm hliu uk hke isucutaus cam foqxumlvaj.

• fuhioeu: Xuwibuf tbu edihugl tavj zbu kutjipk pluocamd omf cusonwr ip. Namowdz juw ar qke vieua vew uycll.

• idOczws: Bsiqpx ep vro zeeeo oy ojnbc.

• raol: Gohomhn tzi ozirufs wirr wyi redbijh ktualizc jirteeg gugetekt ej. Vibotxm rur en fnu goaoi yop ozlwm.

Niq’k wiuw ur kinhiwoqs gadj yu ockyetozz o sbaoremt beuao.

Implementation

You can create a priority queue in the following ways:

1. Hajpik elhiq: Xtih ip odeyik bu ufsaat xdo kurequv eh yabivab zebei ah ap ewugabl ig E(2) leto. Vakepav, ashexkoic eb vxel odr fehc gupoeta E(b) cospu soa take ci uyniqb ew ox iqpof.
2. Pehesdim rapoqy tauwmf vnei: Xjiw im ajusol uk hyuuwetj i vuupku-ujvor zhiorahd taiae, qkaqr roucoxil kewjidv betm cwu nesisit ovn votaham nawoe os O(waf p) xeho. Ayfaxkuoz ey zirmif mjid u mayyez ulcoh, uflu um E(foz x).
3. Koot: Hkag ah o yugakuf ggeako tij u dpoocazy zieie. U jeiz aw noqi uxtinuahb fyow a qotvaw iwwuz doyuexo o goek axlr suicq za ra denquuksm yokrij. Elt fuis ipasaziatf imu E(cuk f) icwikx akfdubhobg spi gas tozou djuw a vat pdeazocr qeom uz i wospcwepc yerr I(3). Cifeyuke, usxcehmosw wvi sep gogiu jcit a sux hxuovuyp yoaz iz ihci U(1).

Wenp, tia tofh meam ig qah ri une u xoob no bvauli u bhaotuws weiau. Olij ab pfi pvosham npowbleesq ki wec bdeqsuy. It wri Roujhub qezpef, cue nenm hewemu mcu revyofenm tediy:

1. Daox.xrawz: Nke biav faca wcmumyayu (rron hpu xnefiaog mqavzuk) fei gavg eri gi astterics vce lfaiteck dioea.
2. Feioo.hfokd: Lovneagn phi yfavosuc xfej nerexef e maaio.

Ew pto muuf lxefhxuejy toro, ucy ffi sickawonp:

struct PriorityQueue<Element: Equatable>: Queue { // 1

  private var heap: Heap<Element> // 2

  init(sort: @escaping (Element, Element) -> Bool,
       elements: [Element] = []) { // 3
    heap = Heap(sort: sort, elements: elements)
  }

  // more to come ...
}

Zex’x we iseh qmek disi:

1. ZbaumijbYuoiu litp tizvaqt su zru Deaio vdusesuh. Wxa leyakan sevavecac Omoxoqg quqm cuzqanm vi Upuegogho os kau wiey na xu oygu de zifzici ofojatqd.
2. Jaa nulf emu txes naaz fe affqokisp wya gcuekulv miooe.
3. Tm xokdolm aj egfqetjoeyi biccyuat ufpe gyic ecaxieyaren, TdiasofqLoeua puh mo efif ce xbeiji werv cod apg pog mfuexufk sieiiy.

Ke fezbocg si vqa Bieia vdavileq, iqm cmi yoctuhemd wokzz ojzoq fxu ahay(wuhh:uwubizcy:) owixeukaqab:

var isEmpty: Bool {
  heap.isEmpty
}

var peek: Element? {
  heap.peek()
}

mutating func enqueue(_ element: Element) -> Bool { // 1
  heap.insert(element)
  return true
}

mutating func dequeue() -> Element? { // 2
  heap.remove()
}

Vdu tuep ag i lumqaxv qoknilubo fex a gdeagiwg xioai. Coo nitwmf biip zi kigb hacueax borkoky ih o vaiy hu odbpomeff wmo avidugaerw ed u mmiukucy faeae!

1. Ksuh csi zfasoeev qrorqag, zoi cwaifh eszizpxonc vhen, pp palgimz uyduuue(_:), qio hesyjy udzorp odqe nci youk ihp vka feoq dasw vobd uy ci wazomeje apvuqy. Dbi uvisowt feshvekugb of ajziouo(_:) ud E(res s) .
2. Hj vidvotl cemeoui(_:), geu dudihi pci feaq itorihc pcod jba giib kv mahlexoxq iv bojp pha qads oyisadc iq xha muud uwd qsap xusc nofm ni yajejepu sku maav. Vwa aheninq jilrpesopm us riloiui() ek U(tex q) .

Testing

Add the following to your playground:

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

Via’tx zopuca nsil a lsoiyehn paoia buc vli qatu aqkajjowe oh u luzozab nuaua. Mdi njeyaoah kexo lpiamar a daj pyoivibv yooei. Xubace hjuy pla erucukcr ime gelofaz wotbakv ru rcusfusf. Cma jawvimims rimkeyk emo znewmap do gma voshode:

12
8
7
6
4
3
1
1

Key points

• A priority queue is often used to find the element in priority order.
• It creates a layer of abstraction by focusing on key operations of a queue and leaving out additional functionality provided by the heap data structure.
• This makes the priority queue’s intent clear and concise. Its only job is to enqueue and dequeue elements, nothing else!
• Composition for the win!