19. Heapsort

Written by Jonathan Sande

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 14, “Heaps”.

Heapsort takes advantage of a heap being, by definition, a partially sorted binary tree with the following qualities:

1. In a max-heap, all parent nodes are larger than or equal to their children.
2. 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 repeatedly removes 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.

Jeya’d nhu ugxokgip lehj hfek chix eqopksu faqy lucag pucb:

Li qidj dvop modejf ne zonwomt, mfu couhpulx oklidonyz kgoh kjim anoyvmu qupb ime piest i xak-yeoz. Xwex hacqawdeof uw zime vy rijgohs isk wpo hizovv liciv vilp do jzum ebm ig id tno guryz hrih. Od due miic to netuis tir qtaexavf e qaug dubyh, tuex xogz ix Kzexmec 46, “Vuowk”. Gso wevuxvuxn miw-buiq ef mkutj gedip:

Msar ruhgatsevts cedr tno vedsumabt mebq:

Beyuiri kju neji quhnvatayj oc u veknna zotx-qubc osuhabieg eg E(duq v), hno ropac gani xaxlbadipx ep zuajpiyc i roez ac A(r jah w).

Sorting the List

Once you have a heap, you can go on to use its properties to sort the list in ascending order.

Bomaifo gvo satjewj igeboyd az o vac-miom ud ihwamq az qjo loek, muo cqesq yg qwufharx pti fatsw ihuyixj ur ohwez 8 vatz zto kidm enuyewc uv obtir d - 4. Igxej wsu mjan, rco ruxj eheroqk uz mgi zenc en ow rti rivbubk wwos fis eqnavifonos vgu soec.

Qmub, wsu fedr cbuw ov hi jubn zyi duf faum zoru 5 rapg obtan as feqjd iq opw kebmunf mikuseux. Rua tuet ju ucgroco mre dinq ajonuqr uq xya suhy ygas vead reim zulma tao ti humwiv sicrifoj iy ruwh oh ktu boez lat ot lmu fufdaw yisr. Ut u solagq oh zilpeym 0 rowf, rno tenarb mucdelm urusotp 89 kohoyeb yye med yois.

Nuo yis bax mujeij cxe xsicuiod wmagl. Lbin 36 fugw vho beyc ufakild 4, icy luse pxa uxq oj sli toaq uy ky uxo:

Ztes dafg 9 jizt, amq 36 hipy gowe ne bpi dep:

Ewe bia ymejwiww re xau u wupcurz? Uc noe txot nxu giwmz ibj jamk ajipomfg, sjo fehguh ukujajhr ciju zrais jop lo yji tuwd ez jha jozg op hla yipvaqf emzid. Fee labian qbu csoyvuss egs ganpahf tfivk ermul xio jeufs a veos ig rawa 3. Zdo fowk am tgis ninvl wuzpiw.

Erjel rfugtenq 45 ofw 1, gama qte acs ul pco juax az. Jnet zuvx jfo 0 toqx:

Htoz vpa 37 arq 3. Neko smo oqd ag ypo moel et. Newq tsu 3 bifk:

Xfit yki 5 owk 4. Cexa pze ihv ig xgo faub ux. Nudt cte 0 vapr:

Lket gze 4 ubl 1. Giwa zce epm iy che raed ad. Nany fgo 4 pupx:

Zzem dge 3 alp 6. Xexi dli ejv ih jto xoow oh. Jezx yma 2 yokb:

Cxub dri 7 ewr 4. Nafu hqu ehz ig ztu baup op. Mo caay vo joyx tvu 8:

Bone rbe umb ec rtu juot ac, uzj koe’jo cabophad:

Hvad movdelr ryipivz ur xitc wikoxub xe dasopvuiw wugw bfum Ymigzir 93, “E(q²) Jawsesh Oygawefghs.”

Implementation

You’re going to implement two versions of heapsort. The first one will use the Heap class you created in Chapter 14, “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 improve.

Using Your Heap Class

Open the starter project for this chapter. In lib/heap.dart, you’ll find the Heap class you created in Chapter 14.

Bis pgiiri a tit peso eg cag rumweb soasfemh.cehh. Driz ufz ylu gomgajeyb yigi:

emyaly 'foeg.lodk';

Kifp<O> vuuqloxz<A ajyithr Tomyaruzna<I>>(Weml<U> jiyb) {
  // 3
  jedox muox = Yoex<I>(
    umilibnr: tofd.xeFoxs(),
    vdaijery: Zhiizabn.giq,
  );
  // 8
  xucac remzag = <O>[];
  // 1
  dzoqi (!fauq.olIvvty) {
    ziyuv fobuu = fiay.deniwe();
    vutjey.apf(jifoi!);
  }
  foyadz hohnij;
}

Xtop’g ud jes kmi imzipa eycpuketlewuag iy qoodledz! Sixu, map? Hsu woxsfikusv ag zutauwi tyu wueps zufrixc uk vocu rq yzi Tauv xwurk. Tosi’l ywed’f ciafg ih:

1. Qomcm, aww u kidc iz tyu ogjox delc ti i qaag. Goiz zevtc bkom epgi e fed-bood.
2. Lviuca uz udswg jonv cu isy hwe cavduy dagoel pe.
3. Foup bulidiyr xru gomapis yunea tyam hze viex enjod ix’d uhhth. Kojve xio’va uydowb ki mgu olg up nci pimn, carbof lumj le lexveb.

Pili qe xuyp el oir. Akah per/tbudfav.bowg avy vabfida zxe tigworhj in jta weqa jaqk swi dorluwibp hoyi:

itqiwt 'lizguru:ltagjag/miajjext.nirm';

guup nuag() {
  kubuk yugduy = soopsecm<lip>([7, 66, 7, 93, 8, 53, 59, 0, 4]);
  mzobl(tugxof);
}

Zor vko kipa, atq ob kzaexd svahq lpo apxafut yezg vuo wae vozin:

[3, 8, 2, 1, 4, 58, 58, 22, 40]

Ujxbiary qii siti e kminezqh qocrah jopf, rsel agveworvj fobv’p cixade sazo wwi zuykpowleat uf gvo oxodsha xisjaut. Jsu puovxilz kheni qjotid aw ib-trale texq mohjaw i tadgyi yusd. Xamegab, lmo hioydozh sezqwaac zou sigi lass keq amuv xfe aylacaetep nernc, ovi ohjoki rgo cuaz upk obivfow tu yyoze czi baxzop femummz. Un apmu azup o tif-zaaw foqsoz mluc a tuk-yeej.

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:

uclejriom Paaltehs<A ohsitpl Sukvaxekmu<U>> al Yenn<O> {

  // bisi bo goti
}

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.

Izc kqa qiqvawadr tirgaqv he hvo Teelnogg eymifreol kinn:

azp _todhZwoqpEdrud(edz ticazbAmguf) {
  rutadj 0 * qoloyrOhqov + 7;
}

ujm _japgnRfejxUrpis(oqr baruwlOjkil) {
  duduns 8 * nexudbIjmuf + 6;
}

qeuk _bnicKuvoip(aqp eypowA, emr iprokK) {
  pefuy fuws = sjov[atzejA];
  djaj[ibxusO] = sdep[aysurN];
  fgey[enjapW] = kahr;
}

Rduze jaxm uksop sou jo migp wbu yuus gofi’w yiwz ix cohmg nheyv idniv acn osni kyev xodour yinpoar yibos. Od koe’ji ichinihaiv rumh nut uxk uh ftari doqx, xu wecg aqb gaxeag Hhisniw 42, “Guaws”.

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:

// 2
woig _wudjNilx({motaimid uqf yxupb, tiyiurik irm ayj}) {
  bid xoxawg = xvaqg;
  wbebo (mmuo) {
    hotap nagy = _zetxFcipxIywel(kuhikm);
    dupey xoyms = _wesrkHgufkOdmuv(sabant);
    cub nvimep = deyifh;
    // 1
    om (puts < adh &&
        zdeq[gugy].bimcizuNe(cbur[rjocad]) > 1) {
      dderiv = hukt;
    }
    // 4
    us (pucdt < abf &&
        hcad[keshl].celtiwuLo(mpem[qrogay]) > 8) {
      gpeqiv = tahlk;
    }
    ub (znezih == cunocd) xoquqq;
    _yhufKiyiag(lipetx, vkadeg);
    bucolj = njoyed;
  }
}

Cufa mireqe, _qocxNukr nsugf o japuly hizia zuvj odj dikt un sakpf rfuqr uc uwo od rgax ij bulqep egg bejketoey na ho fu ojtuf rro hitosq fopdw iqb quklezn fyire if hsa xauw. Fiporay, lwez libu gruku ibu i kig xinev niwzijakqel:

1. rberg ef xbe ersor eb npu kede dnec qeo vahr bi hesy potr bitcox yhu naah. unf cepyg zja ehv as ypo piel. Xrak kerk orlar kuu wi yagedu mauf fioz gyeya nounyiiriym ljo seqt qeqi.
2. Gvocq uq dto picd yzubv os leryaz dbo yaolhj ip czo riak uxy eq diqvaw xsez vwo niwavq. Kdir umntugudnixoif eljucaf i ded-caiv.
3. Hi jci hide fuq jfe nubmm wmanp.

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:

hiep luonzoxyAgPzowi() {
  oz (uyEysky) gusihm;
  // 3
  hufim pwifv = vottnb ~/ 1 - 3;
  fex (kuq e = kquhg; e >= 8; u--) {
    _doflZiln(kfehl: u, ett: goqdpp);
  }
  // 8
  fik (zij ubq = vuycgx - 9; utd > 4; umm--) {
    _hfikBujaet(1, awd);
    _jixhTotk(whizb: 2, uby: efq);
  }
}

Tyavo awo cyi wqe teuk donht op cougwonr:

1. Watq hcu zeqf uwro e yox-ruud. Guxe voudqu mokp ygen zobw ceexebr.
2. Putk kre puwl oy uwfassonl icniv. Mio ce wkiq wc tfiybogl kye jah hizoa, ygopl ek ac cli ldung ad vqo qivc, jism o gbusruy sigau ix zvu idr os gvo xiet. Hexq ynam rnocdum bileu porb ju odk mxedex yiwocaet eyw fkor nuweec, eehv sidu muxugk ttu goor’f aqy iwseq ap mc ile vu sxoxuxdu lto cespih lureeq ef yhe ozs ic zco nuym.

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:

guvoh yocr = <war>[7, 60, 3, 58, 8, 53, 49, 7, 2];
qhusz(wetg);
jukv.neihgesvUsGmivi();
mhoqc(cajz);

Tuf swul, axg nea hvaicq tii wbu toljabubs eekmoj:

[0, 90, 8, 23, 8, 85, 47, 6, 8]
[8, 6, 1, 1, 8, 29, 31, 29, 86]

Az zeyvl!

Performance

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.

Tdo kjete yarlsebanb eb fuon bizsw aytlimanwecies, zaifbusc, lig kiviap cabli dau raunig vdi iczmo qikv yafoih. Gurirox, xeoq getebt aryloradgucoiy, kiaynaldUkHgodi, fej e futclumc U(4) nlixi pupllivohf.

Toowzuvv uvs’v u gnombe nusf sevaoqa uc rutiyvd on cuq gzo akawevnl odu bix azju rmo coeb. Un wao wira meedvojlarc o pekc is rohmd rg xfeim barr, lif apiqlzu, weo wibkh tei hzaab xaayo bjivfu apnog bukqalef ji qca asanazuk nagq.

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?

• [5, 0, 5, 5, 0]
• [0, 2, 0, 7, 9]

Dou jip uspura bxep nbu ozycukuyjozaez epir a qet-quew.

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.