Heap Sort algorithm: Swift & Objective-C implementations

14 May, 2015 No comments Article

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

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:

////////////////HEAP SORT////////////////
int leftLeafIndex(int rootIndex){
    int heapIndex = rootIndex+1;
    return heapIndex*2-1;
}

int rightLeafIndex(int rootIndex){
    int heapIndex = rootIndex+1;
    return heapIndex*2+1-1;
}

int heapLastIndex (NSMutableArray* A){
    return (int)A.count-1;
}

void maxHeapify(NSMutableArray* A, int indexRoot){
    if(leftLeafIndex(indexRoot)>heapLastIndex(A)){
        return;
    }
    
    int rootValue =[A[indexRoot] intValue];
    int largestIndex = indexRoot;
    int largestValue = rootValue;
    
    int leftLeafValue = [A[leftLeafIndex(indexRoot)] intValue];
    if(leftLeafValue>rootValue) {
        largestIndex = leftLeafIndex(indexRoot);
        largestValue = leftLeafValue;
    }
    if(rightLeafIndex(indexRoot)<=heapLastIndex(A)){
        int rightLeafValue = [A[rightLeafIndex(indexRoot)] intValue];
        if(rightLeafValue>largestValue) {
            largestIndex = rightLeafIndex(indexRoot);
            largestValue = rightLeafValue;
        }
    }
    
    if(largestIndex != indexRoot){
        [A exchangeObjectAtIndex:indexRoot withObjectAtIndex:largestIndex];
        maxHeapify(A, largestIndex);
    }
}

void buildMaxHeap(NSMutableArray* A){
    if(A.count<2) return;
    int lastParentIndex = (int)A.count/2;
    for (int parentIndex = lastParentIndex; parentIndex >= 0; parentIndex--) {
        maxHeapify(A, parentIndex);
    }
}

NSMutableArray* heapSort(NSMutableArray* unsortedA){
    if(unsortedA.count<2) return unsortedA;
    buildMaxHeap(unsortedA);
    NSMutableArray* sortedA = [NSMutableArray new];
    for (int i = (int)unsortedA.count-1; i>0; i--) {
        [sortedA insertObject:unsortedA[0] atIndex:0];
        [unsortedA exchangeObjectAtIndex:0 withObjectAtIndex:unsortedA.count-1];
        [unsortedA removeLastObject];
        maxHeapify(unsortedA, 0);
    }
    [sortedA insertObject:unsortedA[0] atIndex:0];
    return sortedA;
}

//Example of use to sort an array:
/*
        NSMutableArray * unsortedArray = [@[@4,@1,@3,@2,@16,@9,@10,@14,@8,@7] mutableCopy];
        NSMutableArray * sortedArray = heapSort(unsortedArray);
        NSLog(@"%@",[sortedArray description]);
*/

////////////////HEAP SORT////////////////

int leftLeafIndex(int rootIndex){

int heapIndex = rootIndex+1;

return heapIndex*2-1;

}

int rightLeafIndex(int rootIndex){

int heapIndex = rootIndex+1;

return heapIndex*2+1-1;

}

int heapLastIndex (NSMutableArray* A){

return (int)A.count-1;

}

void maxHeapify(NSMutableArray* A, int indexRoot){

if(leftLeafIndex(indexRoot)>heapLastIndex(A)){

return;

}

int rootValue =[A[indexRoot] intValue];

int largestIndex = indexRoot;

int largestValue = rootValue;

int leftLeafValue = [A[leftLeafIndex(indexRoot)] intValue];

if(leftLeafValue>rootValue) {

largestIndex = leftLeafIndex(indexRoot);

largestValue = leftLeafValue;

}

if(rightLeafIndex(indexRoot)<=heapLastIndex(A)){

int rightLeafValue = [A[rightLeafIndex(indexRoot)] intValue];

if(rightLeafValue>largestValue) {

largestIndex = rightLeafIndex(indexRoot);

largestValue = rightLeafValue;

}

if(largestIndex != indexRoot){

[A exchangeObjectAtIndex:indexRoot withObjectAtIndex:largestIndex];

maxHeapify(A, largestIndex);

}

void buildMaxHeap(NSMutableArray* A){

if(A.count<2) return;

int lastParentIndex = (int)A.count/2;

for (int parentIndex = lastParentIndex; parentIndex >= 0; parentIndex--) {

maxHeapify(A, parentIndex);

}

NSMutableArray* heapSort(NSMutableArray* unsortedA){

if(unsortedA.count<2) return unsortedA;

buildMaxHeap(unsortedA);

NSMutableArray* sortedA = [NSMutableArray new];

for (int i = (int)unsortedA.count-1; i>0; i--) {

[sortedA insertObject:unsortedA[0] atIndex:0];

[unsortedA exchangeObjectAtIndex:0 withObjectAtIndex:unsortedA.count-1];

[unsortedA removeLastObject];

maxHeapify(unsortedA, 0);

}

[sortedA insertObject:unsortedA[0] atIndex:0];

return sortedA;

}

//Example of use to sort an array:

NSMutableArray * unsortedArray = [@[@4,@1,@3,@2,@16,@9,@10,@14,@8,@7] mutableCopy];

NSMutableArray * sortedArray = heapSort(unsortedArray);

NSLog(@"%@",[sortedArray description]);

Swift Code:

//Safe bounds check for Array
//http://stackoverflow.com/questions/25329186/safe-bounds-checked-array-lookup-in-swift-through-optional-bindings
extension Collection {
    /// Returns the element at the specified index iff it is within bounds, otherwise nil.
    subscript (safe index: Index) -> Iterator.Element? {
        return index >= startIndex && index < endIndex ? self[index] : nil
    }
}

//Helper function to exchange position in one array
//From: http://stackoverflow.com/questions/24077880/swift-make-method-parameter-mutable
func exchange<T>(_ data: inout [T], i:Int, j:Int) {
    let temp:T = data[i]
    data[i] = data[j]
    data[j] = temp
}

//Heap Sort methods
func leftLeafIndex(_ rootIndex:Int)->Int{
    let heapIndex = rootIndex+1
    return heapIndex*2-1
}

func rightLeafIndex(_ rootIndex:Int)->Int{
    let heapIndex = rootIndex+1
    return heapIndex*2
}

func heapLastIndex<T:Comparable>(_ A:Array<T>)->Int{
    return A.count-1
}

func parentOfNode<T:Comparable>(_ A:Array<T>, indexNode:Int)->Int{
    return indexNode/2
}

func maxHeapify<T:Comparable>(_ A:inout Array<T>,indexRoot:Int){
    if leftLeafIndex(indexRoot)>heapLastIndex(A) {return}
    let rootValue = A[indexRoot] as T
    var largestIndex = indexRoot
    var largestValue = rootValue
    
    if let leftLeafValue:T = A[safe:leftLeafIndex(indexRoot)] {
        if leftLeafValue > largestValue {
            largestValue = leftLeafValue
            largestIndex = leftLeafIndex(indexRoot)
        }
    }
    
    if let rightLeafValue:T = A[safe:rightLeafIndex(indexRoot)] {
        if rightLeafValue > largestValue {
            largestValue = rightLeafValue
            largestIndex = rightLeafIndex(indexRoot)
        }
    }
    
    
    if largestIndex != indexRoot {
        exchange(&A, i: indexRoot, j: largestIndex)
        maxHeapify(&A,indexRoot: largestIndex)
    }}

func buildMaxHeap<T:Comparable>(_ A:inout Array<T>){
    if A.count<2 {return}
    var lastParentIndex:Int = A.count/2
    while lastParentIndex >= 0 {
        maxHeapify(&A, indexRoot: lastParentIndex)
        lastParentIndex -= 1;
    }
    
}

func heapSort<T:Comparable>(_ A:Array<T>)->Array<T>{
    var A = A
    if A.count<2 {return A}
    buildMaxHeap(&A)
    var sortedA:Array<T> = []
    while A.count>1 {
        sortedA.insert(A[0], at: 0)
        exchange(&A, i: 0, j: A.count-1)
        A.removeLast()
        maxHeapify(&A, indexRoot: 0)
    }
    sortedA.insert(A[0], at: 0)
    return sortedA
}

// Heap Sort MAX-Priority Queue
func maxNode<T:Comparable>(_ A:Array<T>)->T{
    return A[0]
}

func extractMaxNode<T:Comparable>(_ A:inout Array<T>)->T{
    let max = A[0]
    A[0] = A[A.count-1]
    A.removeLast()
    maxHeapify(&A, indexRoot: 0)
    return max
}

func increaseNode<T:Comparable>(_ A:inout Array<T>, index:Int, value:T){
    var index = index
    if A[index] > value {return}
    A[index] = value
    while (index >= 0 && A[parentOfNode(A,indexNode: index)]<value){
        exchange(&A, i: index, j: parentOfNode(A, indexNode: index))
        index = parentOfNode(A, indexNode: index)
    }
}

func insertNode<T:Comparable>(_ A:inout Array<T>, value:T){
    A.append(value)
    increaseNode(&A, index: A.count-1, value: value)
}

//Main
var unsortedArray2:Array<Int> = [4,1,3,2,16,9,10,14,8]
print("Unsorted array :" + unsortedArray2.description)

let sortedArray2 = heapSort(unsortedArray2)
print("Sorted array with heap sort :" + sortedArray2.description)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

//Safe bounds check for Array

//http://stackoverflow.com/questions/25329186/safe-bounds-checked-array-lookup-in-swift-through-optional-bindings

extension Collection {

/// Returns the element at the specified index iff it is within bounds, otherwise nil.

subscript (safe index: Index) -> Iterator.Element? {

return index >= startIndex && index < endIndex ? self[index] : nil

}

//Helper function to exchange position in one array

//From: http://stackoverflow.com/questions/24077880/swift-make-method-parameter-mutable

func exchange<T>(_ data: inout [T], i:Int, j:Int) {

let temp:T = data[i]

data[i] = data[j]

data[j] = temp

}

//Heap Sort methods

func leftLeafIndex(_ rootIndex:Int)->Int{

let heapIndex = rootIndex+1

return heapIndex*2-1

}

func rightLeafIndex(_ rootIndex:Int)->Int{

let heapIndex = rootIndex+1

return heapIndex*2

}

func heapLastIndex<T:Comparable>(_ A:Array<T>)->Int{

return A.count-1

}

func parentOfNode<T:Comparable>(_ A:Array<T>, indexNode:Int)->Int{

return indexNode/2

}

func maxHeapify<T:Comparable>(_ A:inout Array<T>,indexRoot:Int){

if leftLeafIndex(indexRoot)>heapLastIndex(A) {return}

let rootValue = A[indexRoot] as T

var largestIndex = indexRoot

var largestValue = rootValue

if let leftLeafValue:T = A[safe:leftLeafIndex(indexRoot)] {

if leftLeafValue > largestValue {

largestValue = leftLeafValue

largestIndex = leftLeafIndex(indexRoot)

}

if let rightLeafValue:T = A[safe:rightLeafIndex(indexRoot)] {

if rightLeafValue > largestValue {

largestValue = rightLeafValue

largestIndex = rightLeafIndex(indexRoot)

}

if largestIndex != indexRoot {

exchange(&A, i: indexRoot, j: largestIndex)

maxHeapify(&A,indexRoot: largestIndex)

}}

func buildMaxHeap<T:Comparable>(_ A:inout Array<T>){

if A.count<2 {return}

var lastParentIndex:Int = A.count/2

while lastParentIndex >= 0 {

maxHeapify(&A, indexRoot: lastParentIndex)

lastParentIndex -= 1;

}

func heapSort<T:Comparable>(_ A:Array<T>)->Array<T>{

var A = A

if A.count<2 {return A}

buildMaxHeap(&A)

var sortedA:Array<T> = []

while A.count>1 {

sortedA.insert(A[0], at: 0)

exchange(&A, i: 0, j: A.count-1)

A.removeLast()

maxHeapify(&A, indexRoot: 0)

}

sortedA.insert(A[0], at: 0)

return sortedA

}

// Heap Sort MAX-Priority Queue

func maxNode<T:Comparable>(_ A:Array<T>)->T{

return A[0]

}

func extractMaxNode<T:Comparable>(_ A:inout Array<T>)->T{

let max = A[0]

A[0] = A[A.count-1]

A.removeLast()

maxHeapify(&A, indexRoot: 0)

return max

}

func increaseNode<T:Comparable>(_ A:inout Array<T>, index:Int, value:T){

var index = index

if A[index] > value {return}

A[index] = value

while (index >= 0 && A[parentOfNode(A,indexNode: index)]<value){

exchange(&A, i: index, j: parentOfNode(A, indexNode: index))

index = parentOfNode(A, indexNode: index)

}

func insertNode<T:Comparable>(_ A:inout Array<T>, value:T){

A.append(value)

increaseNode(&A, index: A.count-1, value: value)

}

//Main

var unsortedArray2:Array<Int> = [4,1,3,2,16,9,10,14,8]

print("Unsorted array :" + unsortedArray2.description)

let sortedArray2 = heapSort(unsortedArray2)

print("Sorted array with heap sort :" + sortedArray2.description)

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 (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: