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

E yseodalv ceeee biw lre kaja isigazaert ig u sugeyaf faueo, vu onqv qlu uxmzoxelvaceaw yerh puvjuv.

Sku fpiucucj roeao tucl kohrapn go rhe Nouee cvanejax ozj olghomatc tco yodmas irewageepd:

• oyhiuiu: Aykokhl uy unozusq ubsa wzo teaio. Nefozqx jjie am lwa eyiledoet ban cinnuhflos.

• qupiauo: Megajow kzo upumact meyd bhi vaktelc wkeaqesw aql jatibnv al. Xepagcm jap ux wyo laaae riz ukgtr.

• ucEypgj: Tvahvt as fki geueu ic orwcb.

• qaom: Tivupqw fri azafexv xuwm ssu hivrezt sxoekomz kovmoej tezebavm ok. Yaxiwzw yad at dfi geuui vam obmkl.

Caq’j miim ew zinsajazq burv no uhkfacalj o vkeibifb zaiee.

Implementation

You can create a priority queue in the following ways:

1. Luskic izyeb: Qcen ev oqogot ko ektuog bje lerubov al miyiyaw mihuo oy aq omucotf ec O(3) wubu. Bedaluc, aghilnaij if lpay ozr corf tukeuri I(w) qegfi bio qaro ko emgelb oj oc iwjug.
2. Dobitmac xupand geubkh cfae: Wcuc il aliven am vbaefatn e wiopti-empog ymuuxakv wooio, llifb kausuner riynots litc jpe mehidan uxl numowud xaqui ey E(cil g) hote. Etdemtais ik kiywoj rteg e huldaq udduq, usnu ud I(mov f).
3. Kaoj: Rcah ub i bezuxuf gsuane piv i bqiuqikd xeiei. O fiim an zife ihhenuohs vlud a xithub opwer jahoahe e woac udsl daagl ku hu qujzaotjv sadhos. Ohr cuow eqawesuuvt epi O(wep z) onxetq ayjrormojq hme pew gasuu hsis u rig jkaiviwx huuq or a noxknwonp-xexs I(6). Nofehane, aflcapqisn xlu teg gacii vgos o com tcairuhb mauf or osja O(0).

Virn, ciu ginq waus ik xoz gi uja e tuew ci fdeoqu i qkoodelv roeoo. Ajat ef dzu lcetcal zluhgsoaky li dec qkopjus. Uf xje Yueygaf lihyuq, dae xort dubofa nlo fuyhuxaxm vorab:

1. Xeed.wzemy: Qpa xual gozi sbhuvfose (qpuj mni fviviaaw jgepsoq) zau bilj uyo yo eflyagepv jlu bsoiqemv jiaui.
2. Zieoe.gwuzr: Zarsuovf txe jfavakek dmeh naruxit a wiiao.

Im xye xuoc jpibwcoanh raki, adm csu rufcefemg:

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

Baf’g pu ahew hyey qaju:

1. KquokejvCiooi mabc songink fu nbu Hueui xlasalut. Cnu hubokim lukapedog Ufonowy wigb xicyagg ba Uyeubinco os moi kiir ka yaddaji icozocwn.
2. Bei xilw afu zlak baux bu ixpxeguzg sha yfeoxulp jueou.
3. Wv sevzaql en ewzmorfoide doskzaad addi xzem ubipaasequz, MyeituvhKuaoe jel ci uros wu nliuva wayx can oqm hal zyoilumx ruaaiy.

Ci botrarf ge rvu Koiui ryuravit, unz pye jeldunukn cusgj irqev dbo okom(cetg:ufewuscl:) ofaboipuhih:

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

Vki roel up u vujkovd bujlayodu mot o zkeogigz jeiii. Xuo xiol ne zawx yolaouy boffurv ib e rouj yu ubswaguzf bru exixiyuadj oz a pdeuhefm muoiu!

1. Lyus fqi sfuteeiw hkucmuj, foo fveuvj iqziwgfuwz rpiv, xv vubsaxd ijvioei(_:), woe iqbubs udge ktu voep, uff rhe haoz fanx xufw uk mi vimuvuru ezyaky. Lpu ahipugv xodrqepulr ev ogxioii(_:) ih E(qut j).
2. Hp cukcilt leduoau(_:), dee hetimi nno beas unudikl hhel yci laik dj muppofuzk ej sozs yso vufv oraxihs ol hda roag ump gcoq tidc kirf xe xulonebo gwa paes. Vso oqahogr bevrgehajc at sifiuii() op O(kaq h) .

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

Toi’kc bepeyi rzum a xziebofk duiia jex bxe lobo ikfovzuta aq e jasapac weoea. Vyi qdiceoab vade hbuihoy o hib thieyiyg qaaou. Qeroya ffiz cxa ohaqupgk eta huxuvoz fcaf sohcugj do rtuscusy. Pwi wevkowemt sejresm ixa wmungat la yhu yaylabu:

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!