Heap Sort | Free Chapter #1, from Data Structures and Algorithms in Swift

Hi {NAME}, You asked for it, you got it: here is your first free preview chapter from our new Advanced Swift books! This is an excerpt from Chapter 17 of our new book [Data Structures and Algorithms in Swift](, written by Kelvin Lau and Vincent Ngo. The book covers everything from basic data structures like linked lists and queues, all the way up to merge sort, weighted graphs, Dijkstra’s algorithm, and other advanced data structure concepts and algorithms. [Image](  Heap Sort Heapsort is another comparison-based algorithm that sorts an array in ascending order using a heap. If you aren't familiar with heaps, you can learn more in Chapter 12 of the full book, which covers "The Heap Data Structure". Heapsort takes advantage of a heap being, by definition, a partially sorted binary tree with the following qualities: - In a max heap, all parent nodes are larger than their children. - In a min heap, all parent nodes are smaller than their children. The diagram below shows a heap with parent node values underlined: [Image] Getting Started Download the [starter project for this tutorial]( and 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. [Image] This conversion is done by sifting down all the parent nodes so they end up in the right spot. The resulting max heap is: [Image] Which corresponds with the following array: [Image] Because the time complexity of a single sift down operation is O(log n), the total time complexity of building a heap is O(n log n). Let's look at how to sort this array in ascending order. Because the largest element in a max heap is always at the root, you start by swapping the first element at index 0 with the last element at index n - 1. As a result of this swap, the last element of the array is in the correct spot, but the heap is now invalidated. The next step is thus to sift down the new root note 5 until it lands in its correct position. [Image] Note that you exclude the last element of the heap as we no longer consider it part of the heap, but of the sorted array. As a result of sifting down 5, the second largest element 21 becomes the new root. You can now repeat the previous steps, swapping 21 with the last element 6, shrinking the heap and sifting down 6. [Image] Starting to see a pattern? Heap sort is very straightforward. As you swap the first and last elements, the larger elements make their way to the back of the array in the correct order. You simply repeat the swapping and sifting steps until you reach a heap of size 1. The array is then fully sorted. [Image] Note: This sorting process is very similar to selection sort, which is covered in Chapter 14 of the full book. 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 } } Here's what's going on: - You first make a copy of the heap. After heap sort sorts the elements array, it is no longer a valid heap. By working on a copy of the heap, you ensure the heap remains valid. - You loop through the array, starting from the last element. - You swap the first element and the last element. This moves the largest unsorted element to its correct spot. - Because the heap is now invalid, you must sift down the new root node. As a result, the next largest element will become the new root. Note that in order to support heap sort, you've added an additional parameter upTo to the siftDown method. This way, the sift down only uses the unsorted part of the array, which shrinks with every iteration of the loop. Finally, give your new method a try: let heap = Heap ( sort : >, elements: [ 6 , 12 , 2 , 26 , 8 , 18 , 21 , 9 , 5 ]) print (heap.sorted()) This should print: [2, 5, 6, 8, 9, 12, 18, 21, 26] Performance Even though you get the benefit of in-memory sorting, the performance of heap sort is O(n log n) for its best, worse and average cases. This 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. Heap sort is also not a stable sort because it depends on how the elements are laid out and put into the heap. If you were heap sorting a deck of cards by their rank, for example, you might see their suit change order with respect to the original deck. Where to Go From Here? Heap sort is a natural application of the heap data structure and you now should have a solid grasp on how heap sorting works. You will use this as a fundamental building block in future chapters as you build your algorithm repertoire. If you enjoyed what you learned in this tutorial, why not check out [the complete Data Structures and Algorithms in Swift book](, available on our store in early access? [Image]( Don't forget, the book is currently on sale for [40% off]( until this Friday, April 27. I'll be back in a little while for your next free chapter - covering getting started with Realm! - Ray To make sure you keep getting these emails, please add ray@raywenderlich.com to your address book or whitelist us. Want out of the loop? [Unsubscribe](. Our postal address: 1882 Hawksbill Rd, McGaheysville, VA 22840