package Ġkat as . kotlin . hack err ank . short est _ path Ċ Ċ import Ġkat as . kotlin . hack err ank . short est _ path . Binary Heap . Companion . binary Heap Of Ċ import Ġdat sok . should Equal Ċ import Ġorg . junit . Test Ċ import Ġjava . util .* Ċ import Ġkotlin . collections . ArrayList Ċ import Ġkotlin . collections . HashMap Ċ import Ġkotlin . random . Random Ċ Ċ class ĠBinary Heap < E >( ĊĠĠĠ Ġprivate Ġval Ġcomparator : ĠComparator < E > Ġ= Ġdefault Comparator (), ĊĠĠĠ Ġinitial Capacity : ĠInt Ġ= Ġ 3 2 Ċ ) Ġ{ ĊĠĠĠ Ġ@ Suppress (" UN CHECK ED _ CAST ") ĊĠĠĠ Ġprivate Ġvar Ġarray : ĠArray < E ?> Ġ= ĠarrayOf Null s < Any ? >( size Ġ= Ġinitial Capacity ) Ġas ĠArray < E ?> ĊĠĠĠ Ġprivate Ġval Ġindex By Value : ĠMutable Map < E , ĠInt > Ġ= ĠHashMap ( initial Capacity ) ĊĠĠĠ Ġprivate Ġvar Ġsize Ġ= Ġ 0 ĊĊĠĠĠ Ġfun Ġsize (): ĠInt Ġ= Ġsize ĊĊĠĠĠ Ġfun Ġelement (): ĠE Ġ= ĊĠĠĠĠĠĠĠ Ġif Ġ( size Ġ== Ġ 0 ) Ġthrow ĠNoSuch ElementException () ĊĠĠĠĠĠĠĠ Ġelse Ġthis [ 0 ] ĊĊĠĠĠ Ġfun Ġadd ( value : ĠE ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( index By Value . containsKey ( value )) Ġreturn ĊĠĠĠĠĠĠĠ Ġif Ġ( size Ġ== Ġarray . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġarray Ġ= ĠArrays . copyOf ( array , Ġarray . size Ġ* Ġ 2 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġthis [ size ] Ġ= Ġvalue ĊĠĠĠĠĠĠĠ Ġs ift Up ( size ) ĊĠĠĠĠĠĠĠ Ġsize ++ ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġadd All ( collection : ĠCollection < E >) Ġ{ ĊĠĠĠĠĠĠĠ Ġcollection . forEach Ġ{ Ġadd ( it ) Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġremove (): ĠE Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( size Ġ== Ġ 0 ) Ġthrow ĠNoSuch ElementException () ĊĊĠĠĠĠĠĠĠ Ġval Ġresult Ġ= Ġthis [ 0 ] ĊĠĠĠĠĠĠĠ Ġthis [ 0 ] Ġ= Ġthis [ size Ġ- Ġ 1 ] ĊĠĠĠĠĠĠĠ Ġsize -- ĊĠĠĠĠĠĠĠ Ġs ift Down ( 0 ) ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġremove All (): ĠList < E > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġresult Ġ= ĠArrayList < E >( size ) ĊĠĠĠĠĠĠĠ Ġwhile Ġ( isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult . add ( remove ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġupdate Priority Of ( value : ĠE ) Ġ{ ĊĠĠĠĠĠĠĠ Ġs ift Down ( s ift Up ( index By Value [ value ] !! )) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġclear () Ġ{ ĊĠĠĠĠĠĠĠ Ġsize Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġindex By Value . clear () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġtail rec Ġfun Ġs ift Up ( index : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( index . parent Ġ== Ġ- 1 Ġ|| Ġthis [ index . parent ] Ġ<= Ġthis [ index ]) Ġreturn Ġindex ĊĠĠĠĠĠĠĠ Ġswap ( index . parent , Ġindex ) ĊĠĠĠĠĠĠĠ Ġreturn Ġs ift Up ( index . parent ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġtail rec Ġfun Ġs ift Down ( index : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġmin Index Ġ= Ġindex ĊĠĠĠĠĠĠĠ Ġif Ġ( index . child 1 Ġ< Ġsize Ġ&& Ġthis [ index . child 1 ] Ġ< Ġthis [ min Index ]) Ġmin Index Ġ= Ġindex . child 1 ĊĠĠĠĠĠĠĠ Ġif Ġ( index . child 2 Ġ< Ġsize Ġ&& Ġthis [ index . child 2 ] Ġ< Ġthis [ min Index ]) Ġmin Index Ġ= Ġindex . child 2 ĊĠĠĠĠĠĠĠ Ġif Ġ( min Index Ġ== Ġindex ) Ġreturn ĊĊĠĠĠĠĠĠĠ Ġswap ( index , Ġmin Index ) ĊĠĠĠĠĠĠĠ Ġs ift Down ( min Index ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġto Set (): ĠSet < E > Ġ= Ġ 0 . until ( size ). map To ( Linked HashSet ()) Ġ{ Ġthis [ it ] Ġ} ĊĊĠĠĠ Ġfun Ġto List (): ĠList < E > Ġ= Ġ 0 . until ( size ). map To ( ArrayList ()) Ġ{ Ġthis [ it ] Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġto List (). join ToString Ġ{ Ġit . toString () Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġoperator Ġfun ĠE . compareTo ( that : ĠE ) Ġ= Ġcomparator . compare ( this , Ġthat ) ĊĊĠĠĠ Ġprivate Ġfun Ġswap ( index 1 : ĠInt , Ġindex 2 : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġtmp Ġ= Ġthis [ index 1 ] ĊĠĠĠĠĠĠĠ Ġthis [ index 1 ] Ġ= Ġthis [ index 2 ] ĊĠĠĠĠĠĠĠ Ġthis [ index 2 ] Ġ= Ġtmp ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġoperator Ġfun Ġget ( index : ĠInt ): ĠE Ġ= Ġarray [ index ] !! ĊĊĠĠĠ Ġprivate Ġoperator Ġfun Ġset ( index : ĠInt , Ġvalue : ĠE ?) Ġ{ ĊĠĠĠĠĠĠĠ Ġarray [ index ] Ġ= Ġvalue !! ĊĠĠĠĠĠĠĠ Ġindex By Value [ value ] Ġ= Ġindex ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun ĠisEmpty (): ĠBoolean Ġ= Ġsize Ġ== Ġ 0 ĊĊĠĠĠ Ġfun Ġis NotEmpty (): ĠBoolean Ġ= Ġ! isEmpty () ĊĊĠĠĠ Ġfun Ġcontains ( value : ĠE ): ĠBoolean Ġ= Ġindex By Value . containsKey ( value ) ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġfun Ġ< E > Ġbinary Heap Of ( var arg Ġvalues : ĠE ): ĠBinary Heap < E > Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġresult Ġ= ĠBinary Heap < E >() ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvalues . forEach Ġ{ Ġresult . add ( it ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġprivate Ġfun Ġ< E > Ġdefault Comparator (): ĠComparator < E > Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠ ĠComparator Ġ{ Ġo 1 , Ġo 2 Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ@ Suppress (" UN CHECK ED _ CAST ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( o 1 Ġas ĠComparable < E >). compareTo ( o 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġprivate Ġval ĠInt . child 1 : ĠInt Ġget () Ġ= Ġ( this Ġ* Ġ 2 ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġprivate Ġval ĠInt . child 2 : ĠInt Ġget () Ġ= Ġ( this Ġ* Ġ 2 ) Ġ+ Ġ 2 ĊĠĠĠĠĠĠĠ Ġprivate Ġval ĠInt . parent : ĠInt Ġget () Ġ= Ġif Ġ( this Ġ== Ġ 0 ) Ġ- 1 Ġelse Ġ( this Ġ- Ġ 1 ) Ġ/ Ġ 2 ĊĠĠĠ Ġ} Ċ } Ċ Ċ class ĠBinary Heap Tests Ġ{ ĊĠĠĠ Ġ@ Test Ġfun Ġ` heap Ġconstruction `() Ġ{ ĊĠĠĠĠĠĠĠ Ġbinary Heap Of ( 3 , Ġ 2 , Ġ 1 ). toSet () Ġshould Equal Ġset Of ( 1 , Ġ 2 , Ġ 3 ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test Ġfun Ġ` keep s Ġmin Ġvalue `() Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġheap Ġ= ĠBinary Heap < Int >() ĊĠĠĠĠĠĠĠĠ 1 0 . down To ( 1 ). forEach Ġ{ Ġn Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġheap . add ( n ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġheap . element () Ġshould Equal Ġn ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test Ġfun Ġ` re moves Ġmin Ġvalue `() Ġ{ ĊĠĠĠĠĠĠĠ Ġbinary Heap Of ( 1 ). remove () Ġshould Equal Ġ 1 ĊĠĠĠĠĠĠĠ Ġbinary Heap Of ( 3 , Ġ 2 , Ġ 1 ). let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġit . remove () Ġshould Equal Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġit . remove () Ġshould Equal Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġit . remove () Ġshould Equal Ġ 3 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test Ġfun Ġ` can Ġgrow Ġbeyond Ġinitial Ġcapacity `() Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġheap Ġ= ĠBinary Heap < Int >( initial Capacity Ġ= Ġ 1 ) ĊĠĠĠĠĠĠĠĠ 1 0 . down To ( 1 ). forEach Ġ{ Ġn Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġheap . add ( n ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġheap . size () Ġshould Equal Ġ 1 0 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test Ġfun Ġ` cannot Ġhave Ġduplicates `() Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġheap Ġ= ĠBinary Heap < Int >() ĊĠĠĠĠĠĠĠĠ 1 0 . down To ( 1 ). forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġheap . add ( 4 2 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġheap . size () Ġshould Equal Ġ 1 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test Ġfun Ġ` can Ġuse Ġcustom Ġcomparator `() Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġmap Ġ= Ġmap Of (" a " Ġto Ġ 3 , Ġ" b " Ġto Ġ 1 , Ġ" c " Ġto Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġval Ġcustom Comparator Ġ= ĠComparator < String > Ġ{ Ġs 1 , Ġs 2 Ġ-> Ġmap [ s 1 ] !!. compareTo ( map [ s 2 ] !! ) Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġheap Ġ= ĠBinary Heap ( comparator Ġ= Ġcustom Comparator ) ĊĠĠĠĠĠĠĠ Ġheap . addAll ( listOf (" a ", Ġ" b ", Ġ" c ")) ĊĊĠĠĠĠĠĠĠ Ġheap . remove () Ġshould Equal Ġ" c " ĊĠĠĠĠĠĠĠ Ġheap . remove () Ġshould Equal Ġ" b " ĊĠĠĠĠĠĠĠ Ġheap . remove () Ġshould Equal Ġ" a " ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test Ġfun Ġ` can Ġupdate Ġpriority Ġof Ġan Ġitem `() Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġmap Ġ= Ġmutable Map Of (" a " Ġto Ġ 3 , Ġ" b " Ġto Ġ 1 , Ġ" c " Ġto Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġval Ġcustom Comparator Ġ= ĠComparator < String > Ġ{ Ġs 1 , Ġs 2 Ġ-> Ġmap [ s 1 ] !!. compareTo ( map [ s 2 ] !! ) Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġheap Ġ= ĠBinary Heap ( comparator Ġ= Ġcustom Comparator ) ĊĠĠĠĠĠĠĠ Ġheap . addAll ( listOf (" a ", Ġ" b ", Ġ" c ")) ĊĊĠĠĠĠĠĠĠ Ġheap . element () Ġshould Equal Ġ" c " ĊĠĠĠĠĠĠĠ Ġmap [" a "] Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠ Ġheap . update Priority Of (" a ") ĊĠĠĠĠĠĠĠ Ġheap . element () Ġshould Equal Ġ" a " ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test Ġfun Ġ` re moving Ġall Ġitems Ġreturns Ġthem Ġin Ġsorted Ġorder `() Ġ{ ĊĠĠĠĠĠĠĠ Ġbinary Heap Of ( 3 , Ġ 2 , Ġ 1 ). removeAll () Ġshould Equal ĠlistOf ( 1 , Ġ 2 , Ġ 3 ) ĊĊĠĠĠĠĠĠĠ Ġ( 0 .. 1 0 0 ). forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġrandom Size Ġ= ĠRandom . nextInt ( 1 0 , Ġ 1 0 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠRandom . next Bytes ( random Size ). toList (). let Ġ{ Ġbytes Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġheap Ġ= ĠBinary Heap < Byte >() ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġheap . addAll ( bytes ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġheap . removeAll () Ġshould Equal Ġbytes . distinct (). sorted () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ }