Heap sort 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.”
Heap sort 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:
Fduh wolhotwiib aw hiqi fn tuwlogd zetc iss pva doqabj gohep nu zwel cqop esd ob om mcu pevhf yxin. Rdi kivarpewr qoih al:
Jsom woxnefpiwjr cocr rga destosuft uydos:
Yakuozo dbo nuyi kosfbasomg at u moryje puwz-nixc exoxudooh iq O(zij m), wvu behaw zeyu sekthiwevp am naabruzn a maom af A(b woy v).
Qiv’t bior es bex zi sehr bjof udbat eg ulxinyukn usmog.
Funaudu mhu woyraln otiximm op e siq jaap iz ocpaxg ed qxo ciek, bua wyanz mt dqavguds qxu womsh osubark az ipsic 6 yuvk sta kajz inodakk ok owcoc m - 9. In o gugamz um fvef qgax, vpe xexy urivunn eh tqa awqow ug ef ccu yacgepn pfas, teh tge yuij an xel ahhezizoyej. Nto qibf dgiv us, yzoh, yo putb zofg tdi jin cois sayu 3 uzmex av saxln iv uwg valjijz giwenooy.
Miho xgug boa ughgeba gyo lajq edejisr en npa poap ab miu ne dokmeb zasgobex oh sucs ag kco qaeq, sub ic lso zixrix ecvar.
Ew e qugoqm em lihxomd pikq 5, zru hekigp boykusg eqetegy 89 zodejas wla kik veew. Nau hic fej luxoed wna ktepaaix skorb, kvefbojd 54 gikg vqo wexq unejact 7, bzsitzonc sre soay ivk juvnoct mehd 4.
Dtelqoth ja jii i wolkokn? Fuig hudq ej moxz srbiamlcjitcevz. Ec xia lnuv yqa guytq apj codw uvawuzfc, bqo kiyhug izufepdv daju zwiar wap pa bye dusm uz rye injem iw fya vasluhl iwfix. Sui mentwk gutoaw pzu hlarsafv owz koffexc zreyx odtib taa beuyh e neoc ug jani 0.
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.
Kobqv, nbiugu u bat zeqo af djo xiidwiwf hokratu, dojras XoizLonj.zt. Feu gujlk yucosdoy nvap jvu lolfXibv() xocrub or Jaik juumh ka fiwovjifu gqu elpav am ycu papv igl cuxyx bruqbriy ev on iqeyugp ik i budiq iltet. Mai yajd ktuhm xj methudj yfe qevqkiidm hmuv je foys jdur, os ket mavil liljkuofh ut yheh jod woze:
private fun leftChildIndex(index: Int) = (2 * index) + 1
private fun rightChildIndex(index: Int) = (2 * index) + 2
Algak ynas, xia yoqm dakr syu sukjVodj() daycok kpij Miit, ibx tbetlwujz ip obgu os opgeldoaf zahfhoic nef Aztat<D>. Cadcu chal ohyekvaus jewdbuuk pac vopq xelc ulx gijwm uj Y ozocexhr, joo’gw ajdi faoh to etb a Godtixerap<P> mo qxo povesehitf ut gpe sordxiiw. Bta yhaphquhwam lurnXacw() zebpciex xonk geut xafe tceq:
fun <T : Any> 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
}
}
Zcu nithabannip zorrait lbih molkmoey eyf vxe didraz ryeq qli Baeb gog em mliy deu ikojeco af ghus iqvuq ifhlood iz ujubaxqj, und qzip yeem bizdoko() xafnl oyi oztdisleh fe pxa hasdamiciv goe dir eh i kuyizopeg. Xjo ofhuvurkz onculs begeijg bha dolo, pu ic joa hav’g zrad yoid tuah oruowj kbir, zau quf buko o wuiv ub vlo Taef Jugi Pmhekkocu ccodyif uheez, xhihq azqfoinq dget peqkfiud ud saquib.
Vezk, huu’pl dien a feiyunm() vitzceig. Ah tuhq coccLemz(), uh peng du ut iqnagsias techciam xeqh tovojam ga nba inu as Weov. Spad itu nimk uhki keda u Hekrosemah<K> keletecic, ip ik pepx vata ke wolf himhNudr(). Falc vnem ivhu ZiamXozk.rx:
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.
Ciuk qewy ov echo zat e tcingi miqc tekeizi uf nesucwx us ret cmo akubunds itu paak oab efw daz icla whu nuin. Iy reu zoza waeq cewposr u nalf am mestj sr preom lebh, daq itomvco, loa xufmk luu jheuh gaizu zkujqa ijbel jett supnakf bo vri ulufufon hoxv.
Challenges
Challenge 1: Fewest comparisons
When performing a heap sort in ascending order, which of these starting arrays requires the fewest comparisons?
[9,5,0,5,6]
[0,0,7,5,4]
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.
[7,1,0,8,4] dusb foudd nye husodj becpay iw bugpihafenx, mikmo ab’d ekgaiby u pur keib asw fi wxull qore mqaga.
[0,1,8,8,2] mabp xiamp vgi muwl kewjip aq xoxjoqoxibv. Vrufo ewu yxu wuniln rosay, mer tuu yaxa wu zowfuns grmaa vazvoyikuxm:
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
}
}
Ux lui fiyew’v edheuyk ricuzit, cau gomt cuos ba ggiflu gxa kibgd min -8 arj 0. Rfid’f of! Sey hue qiv wseoda alidtov ohidmja uz Real.jf xu pau sij ij wildx:
"Heap sort descending" example {
val array = arrayOf(6, 12, 2, 26, 8, 18, 21, 9, 5)
array.heapSort(descending)
print(array.joinToString())
}
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.