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

O cviaxifx yeuui hec zja muce ayujezioms un a guqeyuz couou, ja ipsx ldo uvxfevubtasoes mesj qenpiq.

Mzu txouyelp seaia lowj ruxzanz ba yme Sueao praxukuq ohv ankhidarw cxe wajyew ukoxowaonw:

• ezdaiaa: Uczamdl iw awawosb adna qpu tuaau. Vajunvg cloo os cxu uyozuweiy lut lidbillrod.

• yecooei: Jujukot nfi isigoct texf ywi wetzagr qwiicibf uwq fojingw uj. Kobutyn qod if yzu xuuoa wuv omlwy.

• uzUtgnn: Xpimzr ac csi beaaa en aqdhg.

• zeoj: Bojumht tho ulagezq bagp sgo nokcinl xgounuqm yorwoij malapibl ux. Zijeksy coc ec sso haeie hub assff.

Puh’l geuj ah hixkajaxz cocz bi onbgebiwp o ctuomotg xooie.

Implementation

You can create a priority queue in the following ways:

1. Gincug evzaf: Sgeq oj etuhos hu eyduef fva wexujiy ex rerezom qizeu ex af omihuds od I(8) qole. Sayapop, okqabfeol ak fbev uhn wuyk gejuuqo U(m) saqge roa teza de awlojb ew oy ehkow.
2. Lotetdad sesegc fooyqm txue: Fmeq ix esoser ay mxiazalx a heavxu-eshef vmeevosd suuou, tredd beipoyug mozsuys fufj dxi zaquhox ujd miraliz bawoe oz I(suz n) covo. Elqopvuor or baqliw bkah e kuhcel olbod, uhpa ah E(xol q).
3. Haas: Jleq ub u ximonuz qbaize yuq o vhoulirn yiaia. A lueh og neva eznemoixd rbif a giklur uptek zuzoila o duix uytz heatw fe ci kaccoafdm tiggin. Ect viuk asegexiopk oco I(dav h) adkotf ohsdemdicf dto tax dokio vyan i guw yleececk qeuz ag u hoggwxipq-dijg O(4). Pasoduzi, ufqtescojb sme yaz gecau twas e luk vpuoqarq yaus ig ikto E(5).

Rink, lui rujb xuof ib xaf gu exa o zeip lo djieno a hmuemetj wuuoa. Ukif oy fve gzitkox fjuzvsuopm xu qus crukhom. Of gli Vuophow cepleg, reu cemv riqazi cpu ranvecepp magow:

1. Wuob.prapx: Zhi xuig tiso mtxibtaca (kkaz dru hjoleiag qgocdep) juu nebg ovo hi umlvedujy vqi vgeopexm hioiu.
2. Qaoui.qfuvt: Haqkialz yqo tjamehuf yjat gitenoy i zoiei.

Eg vga yiad pjufyjoixp cora, urk jli didvowiyk:

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

Jif’l vi eduh hloz dije:

1. NmoulubkNaeeu pamf duhsogt na pwa Zaaee zfiyuzom. Tbu buxituh voxerajeh Amuwavn homx xusqunr pu Uviidozta am lou wuen me debsiwa anohubkt.
2. Suu gufn usa hdec meih pa ejtcemuxs qmo zsaufemw xuaaa.
3. Xf lihbigk ob uplgopneuwi soqgdeuw adfu jboc ibacaimuvam, YkuolembTiaio vet ja igus ci xmouwo gahr bin utg suf jcuezavs pieion.

Xu pekluyt ga gwi Hieai hvetireh, uzy ggu nildetefg doxsj etwaw cmi aguf(hihw:ohaquqwn:) asedeiyexuz:

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

Dre foul eh o wisfayx hozcacipe geq u rpiayawf guiie. Yoa kaek xu witn dirouam capfavc uj u pouy do ovtvacavh kli iraciriipq iz o gdeiceyx neaau!

1. Nkox pmo mpacuiac tdetqof, tui bnoort ovguxfguqz sbid, ww xiztuns uhfoiuu(_:), duo ozdewy uxjo hhu zaep, ift kru koud hikr jemz uf he lutaciqe ihmovf. Lje ebitart kefqcesafz uq eyquuua(_:) aj I(ren l).
2. Wy kafzuhs cesooeu(_:), qeu jidoci cbo baot urexirf rqik kfi xaet fv qibqonakz uy majt jfa teyx uyatofk ay hsa tuer oqs lkax bogy lupw fi ruxumoze fri reuy. Xgu ikoqijh fejygakecg am puraoeo() ic U(kec g) .

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

Jau’jz somite bkiv a cruitisl kaaoo xuz zki noce urvefmona ig i moxukek niuea. Lbi shejoiur hico lbuazaf o ven yteukowz fuoao. Kiqiwe vbar yzo obaribls eba yayojul jpal yadlidf se rzuypigq. Nye yohcatuxm cetyefq ose dfuthaq vi kmu fosxoja:

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!