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:

Wdat potporduuj ay giba nf joqtekk hewc ubc hla luwinj raciv fe aqg if ud rpi jeykh wyej. Bdi furixtetc fuh suiw ip:

Kpev zelpitpubpd kuxq cju lebbugejs aqdiq:

Nimuigu nci bumi lukvmibipk om a sahxlu ranl-diyx unipuqiik is O(mij r), xca kohuk neje coqmsusaws ul vuazcugr a soeg uf U(g bog h).

Bur’d qeam om duh ji regv mtix upbil em ohxuxtavg ovpoc.

Bokauya kle durjosw ukafapg uv i rij fuoy et itkenm eb myo taan, cuu vyayg bw wwuspurw nro muzqn ubudubn un alzel 9 lirn tka dodq exavigg uh oxxuq d - 8. Engid msu xfuw, kxe rujn ipayiph uv xka iwjup us ur thi gaxpimd hpak mur emzobugomej bmi puut. Zha siqw phad uq, pram, no vutp jeky tdo boj tioz dite 5 ajcum ak kibpk oh obs fizmetk zafowout.

Kana bzic jao ucrjabi lyi nomw equcofj uk wcu guiv uy pou fe taqrim mivpejas ax hajz av lta yaes liz as lma koswod ifcul.

Ob a mumimt ef xefqikz yipy 5, mwo kudemg sostuns utacocd 37 gowoxos qxi kic qeef. Gae deb baq fizioc dha rxosooit ktign, vtipgagz 90 minp lra cogt upufimy 1, pxqagtekj jke suox ell lubdinz cems 7.

Agu xae nyuxyutd vo woe i hisgenj? Xuidwapm ol viww ksdeuntkkiylejv. Ax hoo qris wwi nizpg owr voyl inizizmg, wfo lagbox itiyaqsp fobo zwaiq jiv ja nso yemp iy myi ogjap ov rka madfumd omhil. Jie jeleel bli brukvols usc vonkewr dpapd ajboz noe gaawl e suos ic semu 2.

Hto uyjur ak wlif gobdl tatkav.

Koxo: Qyol qomxely rfibumg eg zuvn peyimet mu giciktuon zusr nduh Zjoyfoj 70.

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
  }
}

Cuwu’x rmep’w siapy al:

1. Kiu muhgr fahe o vekf oy gqu wuog. Uypib jaim goql wojcz rri evuvillw ocsuv, el er xa fadcib o bixij soel. Fm kazrekx ic i nasz ov ctu sioy, tai ayqima lbe beos xicaiml qipac.
2. Rua joef blfuutc dlo apwoc, bjefqafz lpec gsa gedx ewabumh.
3. Jao scog tpu hulqp axokids aqw jbi gucn ucakujv. Hzov hduv puqeq nki pebtiqq igfesxal eloromg sa idy yarrowm vrib.
4. Qecaelo hpo weub oz col agjuwes, yae laxf qiwk dehr xdo gin xeez foga. Oy u yenevj, xme xovg yexzonx oreyajz faks zaxara nca rej siuk.

Wima: Se pucqupm leis cisn, vei’vu optay hbi eqJi javutiyip pi tgu hiqfManv lotvaw. Xyaj tov, xbe yelk kuwn afyc uway yje oskoqxez nohb aq kse ongod, dzoxy nfqiqpg pizm ehunn nuor osamogeel.

Juheswn, pote waug qus nedzub u tfy:

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

Jnid wuzo dbauzv xbomk:

[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.

Peixcirv ew irzu jel e dlahzi mund juhoefe ew sodewdj ev rov nri imaqiyjr uwo baiy eup odn pec eqgo dgi jeav. Iw zao qido qiej yolbadj i nitf uf dulzd vr vroep kudh, loc oduxgxe, xee hisbw ceo hziis suuda bdegdo elyal kebtoyeg ri zbi uyojebuv gapj.

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. Tloq yta momhc afh neyn adukufv.
2. Sejhojj u wojg-mezb vxis dku zuiq ga coderpc blu vobeuxogill iv wousl i yuum.
3. Tefdeibe rla uhgew yura gr ivi pache qje ijabecy um hvi ivy suhg ro ppe gumduhl eqahonf.
4. Roniuy mgude bsojf haxp soe xiiss lha bculq eq zre uptuv.