Algorithm Heap Sort

Heap Sort algorithm: Swift & Objective-C implementations

Heap sort algorithm is sorting algorithm that uses a data structure called heap. A Heap is a data structure similar to a binary tree (nearly completed) saved into an array. Heap Sort runs in O(n lg n) time. The main property of a heap is that it must maintain the Heap-Property. The Heap-Property depends on the type or Heap we are using. There are two types: Max-Heap and Min-Heap. The Heap-Property for them is the following one:

  • For every node of the heap, its value must be less or equal than the value of its parent (for a MAX-Heap): A[Parent(i)]>=A[i];
  • For every node of the heap, its value must be greater or equal than the value of its parent (for a MIN-Heap): A[Parent(i)]<=A[i];

Another property of a heap is that for every node, we can obtain the position in the array of the left and right child and its parent with the following formulas (if we assume that the root node position is = 1):

For every node “i”:

  • Left(i) = 2*i
  • Right(i) = 2*i+1
  • Parent(i) = i/2

The following image represents a MAX-Heap with the corresponding array of data for every position i:

Wikipedia: MAX-Heap

Wikipedia: MAX-Heap

 

How Heap Sort algorithm works?

In order to sort an array using Heap Sort algorithm, which runs in O(n lg n), we have to use a heap data structure and use the following processes:

  • Max-Heapify: for a given node, the heap is responsible of maintaining the Heap Property by exchanging the root node with the left or right child if some of them has a greater value than the parent node (for a MAX-Heap). Then, it will be called recursively in order to maintain the Heap-Property over the new exchanged child. Detailed explanation: link. It runs in O(lg n)
  • Build-Max-Heap: runs in linear time O(n) and produces a MAX-Heap from an unsorted array of data. If we call Max-Heapify process over all the nodes that are parents of node (1 at least), we will have a MAX-Heap at the end. In order to obtain the nodes that have at least one child, we can simply use the formula: Array.lenght/2 and we will get the index of the last parent node. So we can iterate from that one until the root node and call Max-Heapify in each iteration.

With these ideas clear, the detailed explanation of the heap sort is here (Wiki)

Let’s see how we can implement this algorithm with Objective-C and Swift.

Objective-C code:

Swift Code:

Efficiency & facts:

  • Running time: O(n log n)
  • In place algorithm
  • MIN-Heap is used for priority queues
  • It uses a heap data structure
  • MAX-Heap-Insert, Heap-Extract-Max, Heap-Increase-Key and Heap-Maximun procedures run in O(lg n)

Algorithm chart from bigocheatsheet.com:

Algorithm sort comparison

Algorithm sort comparison (bigocheatsheet.com)

Any improvements?

Hey reader! This post only tries to give some basic idea and an easy implementation of the algorithm (not a detailed explanation of how it works). If you have a better approach, some fix or some clarification to make, you are welcome!!! We can improve this together.

You can make comments on the code via Gist:

  • Swift code: link
  • Objective-C code: link

Have a nice day 🙂

About @marioeguiluz

iOS Freelancer, Entrepreneur and Mobile App Expert

Categories: Algorithm, Development, Objective-C, Sort, Swift

Leave a Reply

Your email address will not be published. Required fields are marked *