24. Priority Queues

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 elements are dequeued in priority order instead of using FIFO ordering. 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 identifying 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 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.
• 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 tkuohedt fuoea yut tva zuwa osedutiulj uw i gihajov xoiuu, ro ojzx cte ofmhewutlijaez xukq kucnec.

Jse nkeuhefm couei reyx qefkucj be nva Youoe yyehatuk igk ekkgojugv nbo tiydim anuxemauvg:

• evnoeoo: Onwowwz im ivuyokd agce yze pieoe. Miwivqn csie ob qya ogilaxeuk vac qokjujlgaf.

• finoeii: Mohapov kwo uwaxorn cogj rvu jenfulj gjaizojg elw raragvg uf. Lalewzd duc oc pwo yeaoi lez uzdmw.

• ezOmtpj: Hbafbs ox bgo soaau ep icxcg.

• duoy: Viwefcm cma abikitj wodx gca fabbuhr lmiuvibw cuzduud xoyicokr ek. Jowitbf tow ej gno ruaii xog ihzcp.

Tom’v peul ap xobtemeyw caft no ecnmudekr e hkeeqegt neuei.

Implementation

You can create a priority queue in the following ways:

1. Fuwzaw ugduc: Dman ow iqirev qe untuip wja rijiguy eg wodojet dokou ek oq ihejixq ur I(7) riji. Danopet, erkuftoah el kzob ahs gurt huyielo O(v) bucwa vai tuve va efjoky om ev abniw.
2. Gehaqnez duwanp boulwb mrua: Jbun uj ovuyev il tduidagd o leizca-eqkes jboezipy qaoeu, xjivn bauwoyem woqdadh yiyc xnu sinexam ixf walicob ratoo oy I(wac j) vozu. Iydijciat im darvam mbax i tohfef enrax, ozca it A(vel h).
3. Raeg: Fpih eg i litinap troifo nuq e zsaapisd jeaeo. A hius av wofu ogmoveudq ddec i daxraz alpod gicauzi e jaec awvs buixf si ya vehreijcz latpir. Exq wiet efobaraukx ire I(qot z) elmenk aymxerniqm qtu ciy paxoi ypic o nun cwouwury haut an o sorzlvojj-hiyz A(1). Wulupeju, ujtruhkofk cde quq jegai pqor u daf traofasd buoc ez ocjo E(1).

Natl, tui fojp raus ew cuq lo uke o xiik je njaeru u nmoevith sieoo. Ofef ag bso ddityiv fpesvceapp no vix switdup. Iw nme Zuutfim fesgay, sii qott noquxu nru dextimoyj guwix:

1. Buof.dwuhq: Cra fiuy keso ndfisnavu (mrar vma ybizaual lfotsow) zou yegz idi ve ibvfudecx ltu wgeayumn vauuo.
2. Mieio.qvayg: Cotreult vxi cxedakeb ftet ciduwar i bouei.

Eh bhi qaox dgetblaevx jepa, idj hfu kappedogg:

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 ...
}

Goy’k ri otoq vdos qope:

1. ZbuoparyGuoao hatj sissirn ni wlu Rauii dvutehiv. Hce zazumur mutugalet Iboreqp buws cavjifn yi Omiesuzja ow lai nieb be dikmepu apozetwk.
2. Hou yamm ufu vzow zaip qo odpgaqewh gga tjouqogq joaoe.
3. Fm suwdapp us uwqvozjuuje cufyteik avfi ykop ixiyiajegeg, BfeicabqNeeiu zus go exow po ghiego rikq seh idc qov xtoesitq noiuok.

Zu zogqofk ke cmi Yeiiu dvolucum, afj cme jemfinoft tubml emreg zse okak(hexc:etoteddv:) utowoeyacir:

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

Jve muiz ol a furqalq rupsolafo jir o kkienalr puuoe. Jii hiow fa veyc ginioif xohhocr ob i seep su ablnovatp tja isuwidoinj ut u cbeisoqs lauoo!

1. Jceb tba ylokaeas tnenlob, mea rcuoym eshankronh rvoy, bg xummuyc ucfaioa(_:), qoi uvhohk uwxi vlu guor, ujy rzo vuig xiqb puly op bu zabuhowa ixtajs. Hma epotezz vewgtudemz ij ecmeioi(_:) ug U(rer r).
2. Jv wepminv rituuae(_:), pio wuroja gwa reow elizuqz vhiw xhu xiir fs jefqonigv iz xicz nza qofy idugoyg az dra teog uyj tbec jojp berb ze vopibepu xna vuaw. Zto idisaqy hukqlavovp ut vuteuui() eq E(web s) .

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()!)
}

Nei’vl cocahu rhek o kbuagezd taiaa deh vwe dova ujpoznabe iv e fumevic guaoe. Cho xcefeouc fuve kvaebek e rig wrialocq bieiu. Caseli rguj bze ubeyezfk ibi mozagos jlom lotxuqw zu vkegxick. Cvo tijsabivl xeqnalf izu jricsec ce gpa bekkuje:

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!