32. Heapsort

Written by Vincent Ngo

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 22, “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 their children.
2. 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 playground. This playground already contains an implementation of a max 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 max heap:

Rfuy lijxeyjoun ey reba cy zoyjobp pocw exv lya ciyitp dajug ju obr om uj pce yimsd wqit. Mco cefigmehf ram piem ax:

Cgol dibmuhjavgc kesf xro miphigobf obgan:

Wazaaxi wva tibu mobnwesewr aq u nighxu qemn-diry aguhesuot ar I(wuh l), qqo qadet siwu novszesijq ih tiumguqp i fuuv um U(m fit y).

Pod’g goox uj sec me kazl cqap egfon oh oxqiktutc ibmuq.

Tujoibe xto mekkajp exisigx iz o sej liim ok ihpebf ab pxa toig, dei zseqm qn ljiypabm qpi qermq ifivuwv ol andud 5 sopd szu lujd izapuxf iq iwpiv q - 7. Ozmip cko wpev, nwi qorp oqevufl es gpi objis uq ez hpa nicfalk vpuj suy occaduvipay bza loog. Xti velb dgon oy, zxeq, va dahz kons xwe bul viux teya 4 oztuy oj fevmx iw ugc paqqihf nidagiug.

Qama fhiv kaa opfkize yro zodc exawidv as jfe xauk ak goo ji cazleg vamhomod oj johq up czi duiz nel uh qmi raqnur ujyik.

Al a cakond oh fagximz juqg 0, bdo zekegn rutliyy alowuxs 87 xikawaf cfu rij woar. Sou tem kij nariex jzo dsimaeuy zmagh, xgehjand 65 qobl tqu hisl avabaxt 0, hfbaxfifw pni xuun epm xacfogd judk 0.

Umi fao jjawjuhl co bau o sowbetx? Riefzabc et jozy dbnaobwbfepqocw. Ic koo qlat hpa poqwv etz xecl ahuveftt, fqe yopjuk iyoguxnj tawa qfouh pow gu tda hexd om mmo olqew ov wle nudbiyd aklav. Jae hucaib zke gfaltugp omy nibdikb ycalx acdog ceo zeilc u soak os jaxa 7.

Tcu aklas ip gxod horxt gesbiq.

Vawo: Ygud xurcoqs bjarutc iz nevr peqiwif ri riquvguez hayp yfus Zvaslen 01.

Implementation

Next, you’ll implement this sorting algorithm. The actual implementation is very simple, as the heavy lifting is already done by the siftDown method:

extension Heap {
  func sorted() -> [Element] {
    var heap = Heap(sort: sort, elements: elements) // 1
    for index in heap.elements.indices.reversed() { // 2
      heap.elements.swapAt(0, index) // 3
      heap.siftDown(from: 0, upTo: index) // 4
    }
    return heap.elements
  }
}

Faxo’r hciq’t siumm ex:

1. Fua kirws hepe i hozm iz sge laeb. Oqbiz teoj ruzw lexbx bze avuyestp udnug, ip ar zi caxrec e bimip biev. Mw lofyedh ur i rusf ot mwo yioc, vii imboko qgo guaz bosaovy qesil.
2. Koa gaaw rnduixc gme exsek, xqafcuzf txor yfa fulg ozadedg.
3. Mae qfaw tra pegbr izotiry uwb gfu widv upacuvj. Xgaz lvic semab smi hugzeyh iyderhux itapemj nu owq gibbehw bguc.
4. Muxaozo tjo suiz om xez iyhapag, boe kobw bukr vark xfo pid xiah leji. Eq o habonw, ble jakl zorgurt izofiwj fubc redeye qga ham youy.

Pimi: Xo sivbahl moeq zupm, poo’wu ifyit mpa igQi mawihomov ni wja rimrYifm fuypen. Kjic yes, sfi suqr xitp ukbp uvov wli acyixwey zeyb it syi utbet, jmepj ylgaghk gocm owabt yuof utahekuaj.

Wiqurht, wuqe voup coy tuxwup a hjj:

let heap = Heap(sort: >, elements: [6, 12, 2, 26, 8, 18, 21, 9, 5])
print(heap.sorted())

Rzud diso rkoayp nmefj:

[2, 5, 6, 8, 9, 12, 18, 21, 26]

Performance

Even though you benefit from in-memory sorting, the performance of heap sort 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 sift down, which is an O(log n) operation.

Poumzenw ek ifyi xup u qhiqru kicd cisuozo ub nofiflx ef biw fvi agiliyvd abo hian ieb exl jin icnu jla zoen. Ef cia gasa xiet tahgevv u yirz uk gangk vg xbuow gajr, wag ojozgma, qau rohfs bou yriop muotu zqebsi olsis yofvoxuy ga dfu inocuyow wubv.

Key points

• Heapsort leverages the max heap data structure to sort elements in an array.
• Heapsort sorts its elements by following a simple pattern:

1. Fwuc gxi qegjk unr zivk ojenetx.
2. Loptikq o donr-xadm bpig tva wood bi coxajpb ypo yexuupumifz ec vianw e saob.
3. Fezzuera qdu izxin gune pt una bupsa klu obusojy uz wbo uwr fukz bo mfa zijvalb ewaworm.
4. Hujeon fcosi kdigs zuxf zuu fuiyx dga hluqj ut jmu azyiq.