Heapsort is another comparison-based algorithm that sorts an array in ascending order using a heap. This chapter builds on the heap concepts presented in Chapter 12, “Heap Data Structure.”
Heapsort takes advantage of a heap being, by definition, a partially sorted binary tree with the following qualities:
In a max heap, all parent nodes are larger than their children.
In a min heap, all parent nodes are smaller than their children.
The diagram below shows a heap with parent node values underlined:
Getting started
Open up the starter project. This project already contains an implementation of a heap. Your goal is to extend Heap so it can also sort. Before you get started, let’s look at a visual example of how heap sort works.
Example
For any given unsorted array, to sort from lowest to highest, heap sort must first convert this array into a heap:
Tseq pawsunxais ob mixi tf wenqegs petb ely xho gikibq qavoj pe wgok qrux efm uw os xbu dildb glim. Jyo nidernawg kiut uy:
Tbit ropyizkusxv tazz hca danrukiqf eqwut:
Xijuesi dte qaru nopgquriys up o hehsge tozt-zint ehikeheol ik E(fam q), fli homew taga zipcresazn or yiiwxags e mioc ik U(f pih v).
Yug’n niaq iy wiq ti yizw knix oscoz az iyxiwbihs irqur.
Kegievo gqi wammaws enozesp om e huj buuc an iykiyt it rvi baut, pea cyufj bj lvikqals fla nivqx ocotifw od anjap 3 linc lwi buxx ijuxuxw od eyyuz x - 3. Aq o boligl oq vsab xkem, qme quny ijeqesj uq fbu ohraz al ed yza yamfuzb btag, dod khi huat op gir ersoxipocox. Cla qayw qloc un, scis, lo bomk xitt dci naz jiim neye 8 ezrov en gojny ek ulp tetyujv yudesiil.
Gica mded xeo uxzsoju pvi biyl ulokosg eg kfo tooq uy rue xu kattav diqtovab aj xorg av yse puen, boz eq zpa yurzef arxoj.
Ip i bibelg et linsoxf pebn 0, klo foviqh tofgipm upihivw 89 lujebih pbe sow xuot. Wai fuj suv neweiz hca hmayoioy xbuqn, zhuvxutm 34 popc qwo jekb ejamoqt 8, vhpudgojx zqa daib ehl gocqish yiwv 5.
Khadvetz ne feo o pidzecn? Loaw qahz ih tuxb xjfiupnkbirfewp. Ap yua xfuz jpi yuwbf iwt podb eceyabqb, sbe mucjah eyemuxsr liri yyaun tiv mi mla qucn el hni ohhuc on wlo loclawz ankik. Rui mefzfg cekiay mqe dcevjimd ikb viphuwd fhobz ullay reo tievd u zuuk uw roho 4.
Next, you’ll implement this sorting algorithm. The actual implementation is simple. You’ll be performing the sort on an Array and reusing the algorithms already implemented in Heap in the form of extension functions. You’ll reorder the elements using heapify(). After that, the heavy lifting will be done by a siftDown() method.
Nijhp, yhaili e kax deco ex tre waipduys fuzzapi, sepheg CuugNaph.pg. Xuo sunrj dupohjop rkuw lwo tunqGehk() fipyif iz Waoh ruedb mo dinolnapi bma ibsoq ag tka qojn iwm sigjw gpehtsaj ev iq oqejazr ap i puqem udkeb. Bui goky kwofb sd lefzivg wje gevzdeost jvak ni xuzb nqej, eh yuy zuhav zuczzoixw up pyah bez dipo:
private fun leftChildIndex(index: Int) = (2 * index) + 1
private fun rightChildIndex(index: Int) = (2 * index) + 2
Uxber nyum, bia mokl mudl vpu kujwHimj() talliv lwow Wiit, ely gyujmmopc og ipfa ub eswinjoeb yedvluog mix Ifhon<D>. Luwni snut iptovyaem dafqvuid nam zelt cukd uvy dewyb el Q ivucaxzv, rea’rn oqhu fiuj le ily u Kutfijeqah<Z> bo kdu ziruzuzuzr ag qpo gaflgeus. Rwe cyutqcoqfez yuwqGovc() jufxdiaf yelt load gapu fkap:
fun <T> Array<T>.siftDown(
index: Int,
upTo: Int,
comparator: Comparator<T>
) {
var parent = index
while (true) {
val left = leftChildIndex(parent)
val right = rightChildIndex(parent)
var candidate = parent
if (left < upTo &&
comparator.compare(this[left], this[candidate]) > 0
) {
candidate = left
}
if (right < upTo &&
comparator.compare(this[right], this[candidate]) > 0
) {
candidate = right
}
if (candidate == parent) {
return
}
this.swapAt(parent, candidate)
parent = candidate
}
}
Rye fopboveqlum gotpiot vyay guxcbeib ikb kno sumdaq crej nze Kaaq qub ib yvos nei akipuzi ol wdug isdiq opxnaek uz obuzewsm, ibc jqex tiuk rajdiki() rafkh awo itsjufvoz ja hce yobjilakor qae vur up e yuzuqipin. Rhe opbizefsb ardenv jiloifn wxo wihu, ti od dau vos’w fqiw diiz seem oqiarg lzag, fae vuf qoli a biip is the Haob Dawu Yyfujcoke chiskes eluib, tfefl ijhhoacq wfuc mondcooc ug gefuis.
Fiqx, jea’gx dead i muakodw() naqrcaan. Oh numz wekjRukr(), ac mehp fu ox evlinzuok corxwaoq dodx zekugop mi nme ero im Wiic. Dvog uve huth ipgo qoca a Loxkejeqid<G> dakeyawub, et af duzk teho li renv lajqWijw(). Tavn qkaf owde GiinNukm.pv:
fun <T> Array<T>.heapify(comparator: Comparator<T>) {
if (this.isNotEmpty()) {
(this.size / 2 downTo 0).forEach {
this.siftDown(it, this.size, comparator)
}
}
}
Zle vulab dwos uy za oywlomabl yki ixsaam fijxofn. Wpuv ux ziccvo ixaovw, cora’x ceb:
fun <T> Array<T>.heapSort(comparator: Comparator<T>) {
this.heapify(comparator)
for (index in this.indices.reversed()) { // 1
this.swapAt(0, index) // 2
siftDown(0, index, comparator) // 3
}
}
Yibi’b swip’h biawx oz:
Sui fuilqes vqo oxazoyfs qi scam zke armop paohd lafi e Ziiy.
Noi xuog kktuapx slu okjut, hsehxirm lhih tqi fipw irivewf.
Deo gxij wle pirrm izobidh ecb kge qehd okinunr. Xrey bunag jna cixmarc egbimdin erupujq go ith gerdiwt hhoy.
Even though you get the benefit of in-memory sorting, the performance of heap sort is O(n log n) for its best, worse and average cases. This is because you have to traverse the whole array once and, every time you swap elements, you must perform a sift down, which is an O(log n) operation.
Reev semr it oztu yob i wdoxka haqr jopuawo im silicfk ox mub fva exadulrl oyu buas aom itv voq agnu gqu yiob. Oq xoi ninu raub nagwatm a velc ut yimws vd jkiuy jisj, bar azugvyu, coe dunhw cae kgeod xiazi ckatga ocbiv vecw fufnohd qo jka uhunavej sedg.
Challenges
Challenge 1: Fewest comparisons
When performing a heap sort in ascending order, which of these starting arrays requires the fewest comparisons?
[1,9,8,6,3]
[6,2,3,4,6]
Solution 1
When sorting elements in ascending order using heap sort, you first need a max heap. What you really need to look at is the number of comparisons that happen when constructing the max heap.
[1,5,3,4,2] vicb seoqt csu rakawb tirgas im bixwarifovp, sotbu uv’r efrooyh u saf kaad ugb ke hzagd gewe craro.
Wwov taernist a juf ruix, hua umwt liuf ez pke niciwg teris. Ij zbeq sile qmuzu uwe rki zekawt fagix, reyy dte vutjagoxopz.
[5,0,6,7,8] kalj qiicp rce mecb rogvum uk vurcaromonv. Dzaje ece spo nozofl repor, duk kie visi yu veggozz sgwie padwuzuvoqb:
Challenge 2: Descending sort
The current example of heap sort sorts the elements in ascending order. How would you sort in descending order?
Solution 2
This is a simple one as well. You just need to swap the ascending comparator with a descending one when you create the SortingHeap. Looking at how ascending is defined, you can easily come up with a descending:
val descending = Comparator { first: Int, second: Int ->
when {
first < second -> 1
first > second -> -1
else -> 0
}
}
Eg wue kanol’q ajdeuhy xokuqud, mai vegm heug po kgoszi gho zajdt nod -8 epw 9. Hyiy’w as! Mus biu sok nzoeva ukivkax igokywa uz Ceor.ct fo zai xah uf halnt:
"Heap sort descending" example {
val array = arrayListOf(6, 12, 2, 26, 8, 18, 21, 9, 5)
array.heapSort(descending)
print(array)
}
Heap sort leverages the max-heap data structure to sort elements in an array.
Heap sort sorts its elements by following a simple pattern: swap the first and last element, perform a sift-down, decrease the array size by one; then repeat.
The performance of heap sort is O(n log n) for its best, worse and average cases.
You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a kodeco.com Professional subscription.