Chapters

Hide chapters

Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

32. Heapsort
Written by Vincent Ngo

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

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:

Max heap 4 1 5 8 10 > > > > Min heap 4 8 5 2 1 > > > >

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:

5 2 8 56 64 00 73 7 0

8 1 3 55 1 6 36 47 20

21 1 93 6 96 65 6 1 0

5 80 2 69 91 4 3 68 7 6 83 7 83 23 3 3 7 04

9 48 0 76 1 2 2 51 0 3 9 65 47 6 5 95 29 99

5 2 60 7 0 9 03 91 34 3 9 6 71 1 2 04 10 77 1 8 1 1 4 11 82 39 93 78 7 1 3 9 6 24 25 25 1 7 5 1 55 34 99 41 5 3 77 9 8 7 9 30 60 88 8 5 2 53 85 65 13 2 1 7 1 97 1 5 8 26 55 78 2 8 15 06 24 05 4 1 6 3 9 1 39 6 9 39 30 67 7 20 87 99 90 7 9 3 9 6 6 0 1 25 4 70 66 68 2 5 1 1 9 43 15 56 67

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
  }
}
let heap = Heap(sort: >, elements: [6, 12, 2, 26, 8, 18, 21, 9, 5])
print(heap.sorted())
[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.

Key points

  • Heapsort leverages the max heap data structure to sort elements in an array.
  • Heapsort sorts its elements by following a simple pattern:
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now