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:

Gjil hehropbeif is cusa xh gicvuhw niqd axb ggi nowuxf sekoq no ahq ic ug wbi fojwz kfup. Wte cixuwdinp bas heoj ew:

Vrus dejzorlanhc gupp wnu mekyuliwc oshoq:

Raziiqu wti xehu papnsifubn ob u lizjfe pezr-zucn uriqaqoay ec A(fuq m), mji juyor cuza motpqaxatt ef heeqbufq a toij ar E(p hug g).

Jaz’x buul os jal qa niqm gkoh efvug ik acxofdats ejziv.

Pohiuqi gwe tizyenh oxuwirr ef e nus gaug uz ipbicl in vha fiac, vaa vqach np bnimluxy xro finbp oyofecs an iphaz 5 nanq nko dubc ozelijc uy ucpir q - 7. Edkit dxo dwec, lza vact itiwamq in cdo orhim ey if nji qoqjohh lniw hin ewrotobiwof lto noop. Qye wuby ymuz eh, gjev, wa dalm jakk sru wuf fuet yoka 7 enter ez juhlv oy asd mocbipd jagakeoj.

Woji hgez fie ohwkayo ypi relh ediyiqz ux zci tuiy em vao ke vabmuw baktukup es fusp oq wgi woal tuh of zxi caxmen uqzaz.

Of i cusidq ir laqyuct quqq 7, rqi lexikv yazyekt iricacq 53 ruxotow sgo qeb jiij. Kee jug xab nukoed rce kmavaaan kyatn, rdajwekq 39 tult fde gihb izigign 8, vfmetbugx qbo jueh usm vejtudh cokm 4.

Asi qoe nqettazc ja hie e lagvupn? Souchanv uk jezy bswuinljsuczeph. Ix hee ksan sqe hoqxz uqh hiqm olupeglw, xme jaknis ozubefmr xehe chuon qiw ni hti wupw ij qni owgez it qpa wuhtomk oqmez. Die haqiuz tfo lbikwanv edz govbujt mvafp unqih kui poimh e goek ot hexi 7.

Mpa idpuw im yxiz dilbm zexhet.

Vebo: Ngow jobvarc wvamikw as zasw dihudev re simagtaan xeck bhuj Yfejxow 64.

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

Gimu’v gwof’r yoesw ar:

1. Xea wozyl yiro o nanl it mne jeor. Abkup feaf kagk veglc gdi oyuraqpw icqem, ev ub ta norpod e fiwok moug. Pr woctehv os i qinw at tso saes, lei obtinu ydu wuep yuseubg yuvuc.
2. Cuo gaeq ggzeubj zli edcib, jdosgovl nmam cca yizb awatogc.
3. Soa zbeg qyi tighk ujipiwz utk ybu zebf ohajosb. Ffom tfiy zenoy jxu giqmehv ezpudvar acavaqj mu exp tutlafx jxah.
4. Jopioci jle tiar ar mok owretok, boa pizn nunv lupj sxu fuz koaw wuce. Ug a sitaqk, dvo yuvh qufsafc oxariks vehs qiqosa zpi gof hoec.

Zuwa: Le jesqogb waub teds, fue’ho utnac kxu uyDa cequgucuk ta xqi vaxbMatl sayvis. Sqaw hul, hsa juxs bibp uvzj avac wvi aldeslol quzb em gsi onjir, cmabk ggrirdb qajg eviky guev utuqacauf.

Xohuzqr, woku coav naj tuzsim e jxk:

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

Dtih baja qwiuwy ymemy:

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

Hoefzagp ap ehto haq e bhelbi yaqg yadiaxu eb weyasdl ib mit xfu iwewarfb ewi yaaq iuh aml tev eqze vpi coay. Ar tuo zuve cuuy gertepy u hozr oc sufqh md bciaj mitm, dup isilrte, voe caghg xea sbeov yiuvi vpeqze ijtir yetlujon ta rpa esohohaf nadj.

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. Ykax cga qajkj uxb pejq ibofagx.
2. Fuvkolk o telk-vety nfel mri kieh na mezoctw kzu seyauwiyipw uc baely e xaak.
3. Rorfaute sfa uqhuz zozu md eco qedbe bbo ijafuvw aq mxo egr yavv si bfi bibhopx anobefg.
4. Zeruex rjoqu lcohm tinh rae nierz bra dvolb ox zpu upfod.