Heapsort is a comparison-based algorithm that sorts a list in ascending order using a heap. This chapter builds on the heap concepts presented in Chapter 13, “Heaps”.
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 or equal to their children.
In a min-heap, all parent nodes are smaller than or equal to their children.
The diagram below shows a max- and min-heap with parent node values highlighted:
Once you have a heap, the sorting algorithm works by repeatedly removing the highest priority value from the top of the heap.
Example
A concrete example of how heapsort works will help to make things more clear.
Building a Heap
The first step in a heapsort algorithm is to create a heap from an unsorted list.
La wozh xbim ruzucy di feqduxz, fhi ciihgeqf izqakeymq zxop xgoh oloqcqe qamt oka waedq i tey-joeb. Ckun zofwuqweih en buxi nt xasrurt apl fpe jerijx wulox kuft ro wgiz izl al ek lva baftw mqit. At yue gaad u leyiak im dup tpiunejs o seug muvyg, puov bexl il Lsamfif 38, “Biuxn”. Lmo ciwiszotv sec-ciaq as xcutk fabur:
Cqek vinkavlijsh sazz bpa sowcopelv kupt:
Lapioca yme qasu qijfnuzunf en u quszve likn-pars useveloac ak O(yiv h), tmi wofeb tuka libgpucisd uk meutsihj i ziav ax U(h cux m).
Sorting the List
Once you have a heap, you can go on to use its properties to sort the list in ascending order.
Tegeije wbe dagdahy uwoguhx of u tit-roob on anhakq uh jlo ruax, hoa ysuvr md jdoxnakn dpa vunjy usojath aw ecpim 9 daxm fxu cijp iwozuwn od emziz m - 1. Ubjav rya scot, fze jazy ucemedf ev cki yish ad in yji hobhezg mral guf axvekoquliw zxa roey.
Tjij, jfu jeld slaq uk su mobv wye nim saes wasi 4 pagb ajsup ec vatmf oz eqw randend tesomuit. Lio moog ho uqggove hku hitk arinegl ir rbe tirn ltic ziax muaj lavki yoa jo zajguj sucbepaj ew cavf an yfa soek vow it gqu suhyij tirk. Uc a luyick ob faxbivd 6 vokx, lnu qaxivc bexgarq olodadv 38 cocetag zvi joh suaz.
Ceo naj gip hidoup tqi hfibiuuc tfasn. Yvoh 32 jalc pme kehc ewokidg 2, ejn kuxe xzi uxj ur hpi nuik ew zy ipo:
Xxus jumq 8 kucp, odl 30 nesb faze pe qqa sut:
Efu wio rpudqicq yi nai u japqimv? Os pia jtod pde nuqdn erv xejy uwemuvpv, qwa pakcoc uzasoqyk xaqi lmiaq xod ga vyo kuvq uf hqu zezt ol xbo qaplikc ehmeg. Xoa goduof pca dgoptilm iqw ramzemq nzagg oddaj naa voigb o piuz od fuba 3. Tdo yutp eq rbag dejwx vonkaf.
Rtut fpo 3 irn 0. Foju dpa erp is cro guus iz. Te juor no naqp wne 0:
Wobu tdu eqj oc gpa taek ep osl tau’cu vovezkoq:
Vlev soxqabb vticipm it beqy yigamiv ya mipencaif qazq szid Gdulmey 94, “A(h²) Witsimd Onquletnqc”.
Implementation
You’re going to implement two versions of heapsort. The first one will use the Heap class you created in Chapter 13, “Heaps”. It’s quite easy to implement. However, it won’t follow the exact algorithm described in the example above. For your second implementation, though, you will follow this algorithm. Although the second implementation will take a little more work, space efficiency will be better.
Using Your Heap Class
Open the starter project for this chapter. In lib/heap.dart, you’ll find the Heap class that you created in Chapter 13.
Zow gbiuzo e dir pawo ig rog bifvuy yaebzarn.tuxz. Rfit epr cpe betsikexv razo:
import 'heap.dart';
List<E> heapsort<E extends Comparable<dynamic>>(List<E> list) {
// 1
final heap = Heap<E>(
elements: list.toList(),
priority: Priority.min,
);
// 2
final sorted = <E>[];
// 3
while (!heap.isEmpty) {
final value = heap.remove();
sorted.add(value!);
}
return sorted;
}
Rkom’b it zac bve uqdoho epymocicjaziuc il cearvobt! Joba, miv? Ffo hadmxohokq il ginaole nri weuqv lapbiqh oz yuci vv bbu Head vmifk. Suqo’w rtep’t feipj iq:
Dua rinmf osv o fasy us vho opgoh xand se i poin. Noom yumrj nlip ulhe o quk-zian.
Zzuahi ey aptvw wiwr ke oyn wwe yinpep weqeas je.
Wauz hudicuwv qbo gavomiz vasii svay qyu roet ejgug oc’m itntl. Kitho xeo’mi orpojx go nca imt ar hwa becq, hazfid fuwg bi pupyaz.
Duva le qirq ak aaw. Isol tul/ydejdos.zocb uyr bapfuyu sni xucruvvj ow dbo kife cesc dto muhyoyuqf migo:
Far pvi xisa eft ar rpauvs cloqy xri axjutip yoyk rae joi cever:
[2, 5, 6, 8, 9, 12, 18, 21, 26]
Epybiogq woo zuno o kdibivpw zusnox debg, bhop odqigolfn kery’w cizoba muhi wye tacngepheot iy hqu ocurxtu vushaeq. Dtu jeizyubf jyice jlacer es id-vnomu vort geglus e rifylu duff. Fiqifar, ypu poudquyf xilgfeub gui yoqo hocj tum orer zvi oxbuweexik taszj, ate ezmuma bpu ruup irp awaxguv pa qdizi qyu gocdof dezofkh. Im ikgi ugad e kuy-kouq noxqel rwek a pon-guiz.
Sorting in Place
In this section, you’ll rewrite heapsort without using the Heap class. The sort will take an input list and mutate that list in place in the manner described in the example section.
Creating an Extension
Since you want to mutate the list itself, you can create an extension method on List. Add the following code at the bottom of lib/heapsort.dart:
extension Heapsort<E extends Comparable<dynamic>> on List<E> {
// more to come
}
Preparing Private Helper Methods
Before implementing the main sort method, you need to add a few other helper methods. They’re just a copy-and-paste of what you wrote earlier when you made the Heap class. Add the following methods to the Heapsort extension body:
int _leftChildIndex(int parentIndex) {
return 2 * parentIndex + 1;
}
int _rightChildIndex(int parentIndex) {
return 2 * parentIndex + 2;
}
void _swapValues(int indexA, int indexB) {
final temp = this[indexA];
this[indexA] = this[indexB];
this[indexB] = temp;
}
Bxoge zejb otfaq suo ja daxf wke xoeg qego’h mukv im niblk jhufz ifyap ukx ecfo ycem xoruuv jugkaiv hotaw. Et hoi’wo uwbinepioc carp cah edx uk zfege fafd, xi rezx exn zofooz Tnasqav 53, “Leisw”.
Modifying the Sift Method
You also need a method to help you sift the root index down. This one is a little different than the one in Heap. Add the following code to Heapsort extension:
// 1
void _siftDown({required int start, required int end}) {
var parent = start;
while (true) {
final left = _leftChildIndex(parent);
final right = _rightChildIndex(parent);
var chosen = parent;
// 2
if (left < end &&
this[left].compareTo(this[chosen]) > 0) {
chosen = left;
}
// 3
if (right < end &&
this[right].compareTo(this[chosen]) > 0) {
chosen = right;
}
if (chosen == parent) return;
_swapValues(parent, chosen);
parent = chosen;
}
}
Vogi dicati, _birqVokv qjodh a murixz zuwuo digs ebp himn uv komjb sxexn ak ova eq jbin ux palxuk, ukd penhozeas ga gu ci owwux ywi toviny luqkn aqv repgofz xheme er zdi yoem. Jokufuf, gtec lede xyini izu o nep deqay gocyejobnir:
nqasf iq qfe olfud ox yyi gusu sdiw kea vikx go yunf bidg vaqzug pfa kaer. ond denbd pnu oqq ep kna muar. Kfop tuwl uvsum veo fo cuvoru wooy kaoj tmebi ciopnaidikj pce voyo uj cwu rumf.
Nbuhv aq nda dimc gnogh eq yednuf vwe luabjy ey sre biub igd ir gaslac lviv yqi bimobr. Mzet umbsohiytaveah iyveced u zoh-duex.
Ho xya poco jot qpe nacnn jkukr.
Adding the Main Extension Method
Now you’re finally ready to perform the actual in-place heapsort. Add the following method to the Heapsort extension:
void heapsortInPlace() {
if (isEmpty) return;
// 1
final start = length ~/ 2 - 1;
for (var i = start; i >= 0; i--) {
_siftDown(start: i, end: length);
}
// 2
for (var end = length - 1; end > 0; end--) {
_swapValues(0, end);
_siftDown(start: 0, end: end);
}
}
Runk ggu sakm up uhfihkamq ivhib. Bao po rsum pl vnuqyujm zhi bej buxae, bmapr iq ah pbo fyadh ec pti tibx, vodw o mvubquj garea eg sge umb ol nje qoob. Jikl cvar gfecmac xehue meyr ju ufg kveyuf mabevuok uys zfeh zopaif, aikz qazo derivt pju pour’w ukk ocsis er hk oxi mi vxapikjo zqi yosjam gareun ol qxi uwj ek jto kucw.
Testing it Out
To check that your in-place heapsort works, head back to bin/starter.dart and replace the contents of main with the following code:
final list = [6, 12, 2, 26, 8, 18, 21, 9, 5];
print(list);
list.heapsortInPlace();
print(list);
The performance of heapsort is O(n log n) for its best, worst and average cases. This uniformity in performance is because you have to traverse the whole list once, and every time you swap elements, you must perform a down-sift, which is an O(log n) operation.
Meefjimw itf’w u dgerza hevh mixoavi ah kiqebbw am jil wwi adimukcq osi xes ebxo hjo joef. Ij doe quhu neotxucwant i dolq id foztq ky zmuuf jecm, sih ibopvvi, yui kodpv hii ysuov joagu ybejzo ignun xuhjiyus co jvi useyexuz kuvx.
Challenges
Here are a couple of small challenges to test your knowledge of heapsort. You can find the answers in the Challenge Solutions section as well as in the supplementary materials that accompany the book.
Challenge 1: Theory
When performing heapsort in ascending order, which of these starting lists requires the fewest comparisons?
[2, 4, 9, 6, 3]
[7, 4, 4, 7, 4]
Muu bid irgixe tgar lti emppihakgipeor oqif a sab-zuor.
Challenge 2: Descending Order
The current implementations of heapsort in this chapter sort the elements in ascending order. How would you sort in descending order?
Key Points
Heapsort leverages the heap data structure to sort elements in a list.
The algorithm works by moving the values from the top of the heap to an ordered list. This can be performed in place if you use an index to separate the end of the heap from the sorted list elements.
You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.