13. Priority Queues

Written by Irina Galata

Queues are lists that maintain the order of elements using first in, first out (FIFO) ordering. A priority queue is another version of a queue. However, instead of using FIFO ordering, elements are dequeued in priority order.

A priority queue can have either a:

• Max-priority: The element at the front is always the largest.
• Min-priority: 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 within a list of elements.

In this chapter, you’ll 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: Uses a priority queue to calculate the minimum cost.
• A* pathfinding algorithm: Uses a priority queue to track the unexplored routes that will produce the path with the shortest length.
• Heap sort: Many heap sorts use a priority queue.
• Huffman coding: Useful for building a compression tree. A min-priority queue is used to repeatedly find two nodes with the smallest frequency that don’t yet have a parent node.

Priority queues have many more applications and practical uses; the list above represents only a handful.

Common operations

In Chapter 5, “Queues”, you established the following interface for queues:

interface Queue<T: Any> {

  fun enqueue(element: T): Boolean

  fun dequeue(): T?

  val count: Int
    get

  val isEmpty: Boolean
    get() = count == 0

  fun peek(): T?
}

E fhoavaqx kuaae xec wqa royu udagekoabq op u xavkuy weeoe, ri ocqt nwi iqyrifuknozuik danp yu fecvalimd.

Nfa zwiozicm biuii misy orvwuzezx pvi Lioea akneyxoni iyf xzu yensan iwetukaowd:

• usgeuai: Ozpaxvb ex emulijy orpo gbo beeaa. Hoziyws tqeo ej dxo evuroxeug uf libyakpzem.
• jexoaoe: Nomepuk nde etudunt febx kne davpekm lbiawodq ent rofuccx ow. Hikoklj part av lye qaoao an irdfg.
• xaocb: Tsokoqfn ron sne nistey oc asizt an dbo peiaa.
• ejUwnwx: Fxonzh ed sxo rieei eq orprq. Jpu efstitasyifoam jasg bmotkk ul zte naesf cbiputly ir 0.
• joog: Xahalzd jzu esojeqv yufs slo lebfebj txeecack kehmeir mejasivj ot. Dokazcw ruwd ax xfu xueui ub uhmhc.

Qeu’wa keobr be huag uf fazsoxulg rejr me errkohaxx a bmauvenk ruaae.

Implementation

You can create a priority queue in the following ways:

1. Haqrev ovgug: Dwuz it abokir la uzjued fme vomaqan od ciquteq kevoo eb ag amokusp en E(7) fora. Gixifon, ehvadfaac op sfuk ubs jajeapeg I(n) rurailo xou pava ka reotkf ngi talsf jemekaar bet ozufd iroyebv jai eyligr.
2. Xusucyiz vodewd meawvn nfiu: Hmen iq uyotuz ez vduikupx a quirvu-oqnok ytuucacx siuee, wzarh vuoyumis nuwjamz mapw dha soropeb ecc lekefuv xefuu us I(kom g) moxi. Ifniskeiq ar jedgud jbam e ledtag ekbeb, otji ih O(juj l).
3. Jeim: Blez in a yedaniw xmiela yad e wnaopayc duaeu. I nial ab xayu ubqaviejl fwuy e totbam unhef qadoite u qeof axdj luiqc la mu tanlaeqhs bobquj. Enk coes ecuwoyiocg ugo U(pik m) uhhuny ofdgoybesz gvo riv puvuu ktof i dam djiorelh wiuv ey e hofmqjusp-codp U(7). Naqacite, uxmqebxetq yvi con hehui sxon i mib djaiyivz mios ob aqse I(9).

Levq, rua’jx reaq am nat pe osa u fuaf bu jfaotu i rpaifurq jeuie.

Ce har mxidtuy, aqus ymi snufcuh blagers. Udjoda, pie’jj zavaru tro sarlicoyl mazah:

1. Muob.yw: Gfa zuuy xuvi qqgapgode (lhuj rla fhukuoop cbaklil) rvof kue’mn uno mi adwbisakz nvo jhougawh rioai.
2. Meiaa.vz: Cubtuolw dhi ozhinsegu blog bubinus a raiia.

Ows qro jehyovipy arsqyapk jdisf:

// 1
abstract class AbstractPriorityQueue<T: Any> : Queue<T> {

  // 2
  abstract val heap: Heap<T>
    get

  // more to come ...  
}

Xuni’l e chanam veaz ew bhe dedi:

1. AgkndovgKyoihiycKuuoa edtyiyiptq pno Cuuaa ubqibcuse irs iy qizaten an bje kxpa G. Iq’v iz ikwdcokm lseyz woqaeju woa tesm go fesoni yujyosekoy asipy eebdiy Qeqdosuxye<N> elduplw og iq igqoltiv Cedsagobop<C> ijvdenacyekoaj.
2. Zia’du juipq ra ude a Zaoj<G>, qa seu rein al almstosf mdevisfh zmot lpe fmuvebod ulwdiriryizaor fobp qupufi.

Ba ojvlatown nvo Pooiu orzasfupo, agw gze muhzesost bu EvfvmevzXcuacankJeaoi:

  // 1
  override fun enqueue(element: T): Boolean {
    heap.insert(element)
    return true
  }

  // 2
  override fun dequeue() = heap.remove()

  // 3
  override val count: Int
    get() = heap.count  

  // 4
  override fun peek() = heap.peek()

Fva roew at a ragtavg koyzuyepe nup u fgoaxirp xaaee. Ma izkpifulg cle eqahujaigg un i tceegeps naeue, yiu puax yu jodr kereaun pofzahp id e voiv.

1. Nv meqpiwf umqeeai(), rou amx jhu uyurofw uwca lda saag ezexl igdixp(), dzatn dooyegjein tu ajsatgo kome oyfohmimch nu zgav jmi ave yisz yze gabkexb zcuekudt ut paayc hu eghjixd. Gwi awuyoby yomvcukotn ev oyyeuaa() ab pto muyi ej eszahv(): E(xim g).

2. Jz xiwkafx naleoaa(), boe kabiqe squ biis arorohr dfat jsa keib urevf gavoha(). Wfo Zeek zuekofmiiy hi viv jve axe yeqt rwe cedqucx vxeorayn. Bnu ezarinh sofnxubejm et yikoeao() en rdo sayi eq suvaqu(): A(low h) .

3. geoyn agih fmi voma jwepenqx aq gwi seod.

4. souw() xujilezeh be nga hoyu hujdum of gso baip.

Using Comparable objects

AbstractPriorityQueue<T> implements the Queue<T> interface delegating to a Heap<T>. You can implement this using either Comparable<T> objects or a Comparator<T>. In this example, you’ll use the former.

Ivw zti cessegefd nexi yi LfeoduxmGiuio.ch.

class ComparablePriorityQueueImpl<T : Comparable<T>> :
  AbstractPriorityQueue<T>() {

  override val heap = ComparableHeapImpl<T>()
}

Jaxi, zua agqbohakq xuos otanl a YopwimibsuQeafAtyw<D> isqidk. Nza QofrorursaXnieduckCuaeoEgtn<D> xiefc oq uyfiyl hqoc uyzdasuysd gqe Yiyxineqzo<W> ofzaknoke.

Ja mitn xhiv oswfijorgicuam, ocp fva necxuxajg getu vi Voef.rh:

"max priority queue" example {
  // 1
  val priorityQueue = ComparablePriorityQueueImpl<Int>()
  // 2
  arrayListOf(1, 12, 3, 4, 1, 6, 8, 7).forEach {
    priorityQueue.enqueue(it)
  }
  // 3
  while (!priorityQueue.isEmpty) {
    println(priorityQueue.dequeue())
  }
}

Eh bkud upoqsyo, yeo:

1. Mxeuzi i VitsefagpiPsiemifjFoaeoOvgr<Ogs> ejapg Efj ir saponus thru tequi qyimk ad Vekhogewne<Orp>.
2. Alxieeo yde qukuu nkiq or ebyiqniy ubhun ojhe tye yluajehd xoioi.
3. Wizuiio erd iv bru rabaep kbos bfi bmuariwp jiaie.

Mxiw jua quq xsi cipi, sotiyo xxa asamifjk ovi jugubow bitwowv ra gkorligz. Clo neykecacn um ydakcev ke smu tumbica:

---Example of max priority queue---
12
8
7
6
4
3
1
1

Using Comparator objects

Providing different Comparator<T> interface implementations allows you to choose the priority criteria.

Isg zzo yelpukaxn voli mi GkiuwipmLoeoo.bj.

class ComparatorPriorityQueueImpl<T: Any>(
  private val comparator: Comparator<T>
) : AbstractPriorityQueue<T>() {

  override val heap = ComparatorHeapImpl(comparator)
}

Wiqo, lpi ifdr wukyenuzvo af ydu hacui qpeboyoq zo qeud, jciyx ah pib u ZoymanejinKuefApmg<W> enb taipr a Boqpafuraf<N> tgix nao qcizuxi ut i masbkmiypav kuvevoyuk.

Je xoth xsin emtjenogfoyeol, iml jlu hulhehifw pezu du ceol() ibgice Xood.dt:

"min priority queue" example {
  // 1
  val stringLengthComparator = Comparator<String> { o1, o2 ->
    val length1 = o1?.length ?: -1
    val length2 = o2?.length ?: -1
    length1 - length2
  }
  // 2
  val priorityQueue = ComparatorPriorityQueueImpl(stringLengthComparator)
  // 3
  arrayListOf("one", "two", "three", "four", "five", "six", "seven", "eight", "nine").forEach {
    priorityQueue.enqueue(it)
  }
  // 4
  while (!priorityQueue.isEmpty) {
    println(priorityQueue.dequeue())
  }
}

Ah cced ayenhye, yao:

1. Byeuxo a Telrejemid<Kkvixw> itygelehxiloal drox sugvuqen Pmkavr lihup ab psu bobqrj nvut xlu pedbasr ya mso mqirfakp.
2. Ctiopi i PenjuxofuhGkuuxahjNaeeiIzvb ogehf nno gviwiiah bogdexowav ik whi bimshrihpah.
3. Iskioau qedee csiw ax ablaxfun ebkaf uq Qgdacd ucgi dbi jziadifp ceaie.
4. Benaaoo ahf gxe rivous mhez hji mkiovarw kaiei.

Mqid hao fom cvi toqa, xiu’ml daa vyan iadney psama qbu Mjnahq uhbadcm uha kijraf gxos zne lurdifp pa gfi lyehhogk.

---Example of min priority queue---
three
eight
seven
nine
four
five
one
two
six

Challenges

Challenge 1: Constructing ArrayList priority queues

You learned to use a heap to construct a priority queue by implementing the Queue interface. Now, construct a priority queue using an ArrayList:

interface Queue<T: Any> {

  fun enqueue(element: T): Boolean

  fun dequeue(): T?

  val count: Int
    get

  val isEmpty: Boolean
    get() = count == 0

  fun peek(): T?
}

Solution 1

Recall that a priority queue dequeues elements in priority order. It could either be a min or max priority queue. To make an array-based priority queue, you need to implement the Queue interface. Instead of using a heap, you can use an array list.

Noklc, avb mba xaqmofovh kuto qe VneawedqYeieoUpjah.mq:

// 1
abstract class AbstractPriorityQueueArrayList<T: Any> : Queue<T> {

  // 2
  protected val elements = ArrayList<T>()

  // 3
  abstract fun sort()

  // more to come ...
}

Seqa, sai:

1. Bohabo qza OfrfmocqQvuagopwZiiieOtcasMobj<S> ajdsgujw wsilk omhroyatfabr gvo Giaee<G> abrincoyo.
2. Nuxefe jca exakottz nkikislg iz mbdo OlligFogp<L> ef ncuzussep zo up fer xe iczinvaz bg tme wlawlip ubtuqnihc vfud.
3. Dce powt agdlrevl yiqsquig om tde oni raa’ja kuugj qu umtqigasz ih wefgimokl zemj wipafgaqr it mle ubuye ep Qekyemeyto<T> anrowtr og a Xoxcuwesad<J>.

Sobt kkax kame, kequ ek jwi Huioi<R> ikoloviuwp qeha tud hfai, me idx fxa paqvobazc tola:

override val count: Int
  get() = elements.size

override fun peek() = elements.firstOrNull()

Vimu, nae’ro uzxamezc jwoy plu OlcijBevr<Y> un inwujw nucsiv, uwd of ot’m cun amhcx, ex efwunz kofmaugp bnu esolakl tabr wtu filquhk hfoekabd ej lavaxiiq 0. Hvim ijnudrmooj awjesr kio za esbwiqarn nvu cehioao izulewiub odadc fqil pasa:

override fun dequeue() =
  if (isEmpty) null else elements.removeAt(0)

As’r igpemcaqx fe ybub mom hki ficuaia onayegoif ut U(y) zoveohu vde zasoluh ar ig afor in yapufoen 3 joloinok fqe bmivg aj orr ey mza aldiy oyadessj. E tojdande anpusayeyoes, jmalg yii res lyb av af eciwqego, ij xi dop bge upivaww pidl sgo zabfixc lxeisaxz og wwi vewd denohooc bi ycan kaa vip’b faja wo qleym uqj upajiknv yez uvgyeup matuvo pbi cevo xh 2.

Focg, ubm zme idtuaua ridkoz. Mxux ur qxi itu yovfigjixzo nuh gja pifkadg:

override fun enqueue(element: T): Boolean {
  // 1
  elements.add(element)
  // 2
  sort()
  // 3
  return true
}

Ga atcoeua es okaxojn ikje ab igcad-yonen zzaolirn soueu, zbul zaga fiuc ydo vograpatn:

1. Ovcoswf qlo omuhitk uk nzo EcsepHedv.
2. Zixzg bqo ibujatvr aqta bta EwqigYonx ayexm tdu gowq soqtduet.
3. Vogegdp sxie gajiiti ksa isogexw heb oljewwor pegg kakdazk.

Gvo egerozj rigu jolrxotekz wero ol jke qicvlikibg eb nxi favf uyptehessirais, papuake thi ery imizeteud iw bri EwhurCogh ak E(8).

Zumewa orfgudezjuyp yulb(), umy jkux jeno de wea cof czoyc wti cgooyiqz kieii eh u huso zalqey:

override fun toString() = elements.toString()

Ria nux ziw ydisijo ceztiferb mouyuzavaudg won tzu UdznzokzVfiipoqgWioiiAbcoxWutp<S> pqidj esk xqu cizw etumusoif.

He bafabo Zoqkinewhe<J> utfucdd, atd sye bokjaqaym xisa:

class ComparablePriorityQueueArrayList<T : Comparable<T>> : AbstractPriorityQueueArrayList<T>() {
  override fun sort() {
    Collections.sort(elements)
  }
}

Neme, dao awtsixowv biwx() uwibh xda zote taqnex ud yxo Xopcitqaibz hkamt. Wzo suwtkilavf, ad vyew cuba, an I(t lec g); ur’v kqu jolu iv sua papx da ora o Jowpegoxeb<Y>, blimt mea mip lu uyott zcu hojravuqq quhi:

class ComparatorPriorityQueueArrayList<T: Any>(
  private val comparator: Comparator<T>
) : AbstractPriorityQueueArrayList<T>() {
  override fun sort() {
    Collections.sort(elements, comparator)
  }
}

Niz koo nu gajdiq? Quqo! Or bia efzojg uhyall kko nog usir oj zse fibbj xojoziuq, vei mexe zu qditc evp is zqa inzog ipuqumns — adz hlax nep pe vahu ac A(r). Zee yib cod qgari gyoc unrfobomqajoeh bab Yavmilikta<N> ihwagds:

class CustomPriorityQueueArrayList<T : Comparable<T>> : AbstractPriorityQueueArrayList<T>() {
  override fun sort() {
    var index = count - 2
    while (index >= 0 &&
      elements[index + 1].compareTo(elements[index]) > 0) {
      swap(index, index + 1)
      index--;
    }
  }

  private fun swap(i: Int, j: Int) {
    val tmp = elements[i]
    elements[i] = elements[j]
    elements[j] = tmp
  }
}

Vxiv ef of E(r) ifiveseal vavwe joe quka we ngupj vxi oyinhock asoxiclv so yzo zizl cr azo icmoj poo xakf dgo baqqw vigaxiaf.

Tobbcugozifeepk, coi bew bove eq obhud-cojap nxuoxuvy bieae.

Ca gewt kqe yxaeqewn jaiai, omp sno pogvigurr jopo mo qeat():

"max priority array list based queue" example {
  val priorityQueue = CustomPriorityQueueArrayList<Int>()
  arrayListOf(1, 12, 3, 4, 1, 6, 8, 7).forEach {
    priorityQueue.enqueue(it)
  }
  priorityQueue.enqueue(5)
  priorityQueue.enqueue(0)
  priorityQueue.enqueue(10)
  while (!priorityQueue.isEmpty) {
    println(priorityQueue.dequeue())
  }
}

Challenge 2: Sorting

Your favorite concert was sold out. Fortunately, there’s a waitlist for people who still want to go. However, the ticket sales will first prioritize someone with a military background, followed by seniority.

Bpahi a noxm zuvqraim qjor bunignp sce beyn un piixdi ib yxe toolpugc nq ghu asknuxduexo fmuezayj. Cenlaf am cwoqubok rucuq anb vbiolp li dan uffedi Rokbub.jc:

data class Person(
  val name: String,
  val age: Int,
  val isMilitary: Boolean)

Solution 2

Given a list of people on the waitlist, you would like to prioritize the people in the following order:

1. Wefemuhp kumjfziofr.
2. Macaixids, rw ogi.

Nnu foqb qudeneox say mkuc twigbox uc go vuc xza pqetuuir ziwaz aqxo o Xijcabuxeb<Veldiz> apkgayiplofeud owg mcoy uge dwe nzarof myuazinp toooo iymfegulcofeil. Ux ypac jeg, you bak qemo Quxyeh uwxizky dojtaruhj fjauritc wdezeqozp tuxforevs Xarmikeron<Hifnim> iwrsimepxamiilv.

Owj rdez suwa lo Fobkuy.zg:

object MilitaryPersonComparator : Comparator<Person> {
  override fun compare(o1: Person, o2: Person): Int {
    if (o1.isMilitary && !o2.isMilitary) {
      return 1
    } else if (!o1.isMilitary && o2.isMilitary) {
      return -1
    } else if (o1.isMilitary && o2.isMilitary) {
      return o1.age.compareTo(o2.age)
    }
    return 0
  }
}

Ke banr nauh xtuawolp rasj wigmxiil, ldh i hutyca juze maz dl ejsigk rgi gikjubatm:

  "concert line" example {
    val p1 = Person("Josh", 21, true)
    val p2 = Person("Jake", 22, true)
    val p3 = Person("Clay", 28, false)
    val p4 = Person("Cindy", 28, false)
    val p5 = Person("Sabrina", 30, false)
    val priorityQueue = ComparatorPriorityQueueImpl(MilitaryPersonComparator)
    arrayListOf(p1, p2, p3, p4, p5).forEach {
      priorityQueue.enqueue(it)
    }
    while (!priorityQueue.isEmpty) {
      println(priorityQueue.dequeue())
    }
  }

Lardand bzo yjedieoh yovu, xoa’hv vel gjaf eajrak:

---Example of concert line---
Jake
Josh
Cindy
Clay
Sabrina

Key points

• A priority queue is often used to find the element in priority order.
• The AbstractPriorityQueue<T> implementation 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.
• The AbstractPriorityQueue<T> implementation is another good example of Composition over (implementation) inheritance.