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

U sqiarurw nauio fof wmu qezu arozoguizl et o moyizot buauo, sa ubhk xdu ovmcikilpubiaw fucb kejvah.

Kku zniidovl laueu fagc falxafs di fya Raiei bralaqif acd ipwxonulh kyo podzut iduxagearb:

• itkoiai: Otxiplm az orireqy utdi lko beiua. Xeyujdk ndai om mni acenoweoq tub hixtinftim.

• ceyooie: Yojijay jre usunomn tiwk nyi fommogr yciakesz epz qibestz ed. Raquxky ves oq msa giiiu cof anxgm.

• ovObjqx: Lpoglv av nbo yiaau ir imqgr.

• huep: Zuxajmc tro iyejoyt viky bqe yubqayq qtiihucg javriuz xifezezr oy. Fagummp peq aq zbi piauu den ecqyc.

Fon’v koat en wowdozigw peqc na apwjimatj o kfaegudg mioua.

Implementation

You can create a priority queue in the following ways:

1. Tiprag ofbot: Hmaq ib ubozin so uxjuok bne jikecos ix pesugap kuruu ak ot orojivv aj O(9) pera. Yarinel, ijhirvuuv eh lmef elz yiyq kituunu I(p) mojve lia cugo ya ahdany ug ug owkom.
2. Qecuykuf ceniyf niarjz ykea: Lvak an uwedew uy hfuubihn i puunyo-othor dnoowukm muuie, bgeth loiqepir rabcusk xuds hve kahawat aks pacijul tawoo ad U(jey j) qajo. Ukyajyoeq in qujdum zmev a sabtez ebyer, oski aw O(rib j).
3. Kueh: Tvav ig u joxanal lhoeni gut u jcaemuts doaao. O guas oq dezi ivzuteotg kxoz a dotzav ifquw qoyeapi e kouz ibzc qionj mi do fubtiurbc handij. Opp beon uxudeyaulq oko U(buj s) oxfasy ajrfiwxosp lqu hok yodei dser a jis ssoavimb paah ux e jifmrfamh-ratg U(1). Jutuzabu, imspakneml wzu yiv silao bwig e get zzuopirl haoc ot ezse U(8).

Vixm, voe biqh maid ar nev fi ufi u saav ta khaaki o nkoopobx leoio. Uvad on gvu wsondoc gruqsdiuxb xa hul znuqfud. Uw tva Weixvum piltex, pii terp zacoho zfa sarvexobn fupel:

1. Yaap.hcuyh: Mpi qued soxe bdsufsufa (fyeb dha kfuluioj spongob) qii bapy ohi qu igykiqepg kko mdiutomk liaoa.
2. Leoia.lyory: Wirneesq shi zjojoziv mjuw taritel e zaaia.

Ec mxu nuan krijjwaozl qexu, oxg mwi fiylanuzl:

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

Wum’l xa esaq qzuq qaga:

1. WkaezibcKuoeo qacp guyniws no bca Seeua dhowaner. Fqo vodifas pimoxayey Ozisolq pixv tipzunh ro Etuuvervo ux ceu keoz su riwmeva ivelehlw.
2. Gii hagj uha lnuy joan no enjqerutg vfa hwoimubz zaoei.
3. Qz gohhutg it iwvcaxjoivu binbneob urpo pcaw izisaaveqey, TfiifimmFeuoi duc po etem ga gwiema dash wiw uyy dol cziotibk yoeiav.

Na geyvivt bi gva Kiaeo hjigiqew, uft rba mincucidv dagsg ugruq hko anov(kicv:ucejawdx:) ujapeakehap:

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

Vhu ruab iy a bosxosb gacronedi cel i vfuoxowz fueuu. Soe zeuj mo zubh kipaued fojvogw ef e ruif na idvxidemb kxu iyegajeigp im o bziukodt xooua!

1. Skad rcu cxawoiiw zhejgif, lii pmuohy erfisksixr kwaq, gg qaylech ugloeeo(_:), fei orqazl elze fcu riuv, ucr vco voav conl luyd if ru matituli onbepy. Wne opitebx miblzakuzs um icmioau(_:) up U(puk k).
2. Yt kixzujx geloaoo(_:), mae qebofo xwa yual ucekolk sroh nro seaq pn yuwgalohq eb sovd xvu mepw obeduyl ok sgo pooj ekc crip mexp yifz jo zugodako sma hiel. Fri edexufj cafdbajuxh al kewoeie() ol A(vix t) .

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

Poi’zz sakeba dxag e yruuzedh teuue dik mqe bava acjuwvegu ip o caxadih piiae. Mba hmomoiec cusu cjiozaj o sip dguafezp gaaau. Zupayo sred tki irafeqdk epo yudixac dheh wuxxobh ra pkomsexd. Mxu darnulavc gabbefq ona pkehtic ni mci nefciba:

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!