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:
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”:
The following image represents a MAX-Heap with the corresponding array of data for every position i:
Wikipedia: MAX-Heap
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:
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
////////////////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]); */ |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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) |
Algorithm chart from bigocheatsheet.com:
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:
Have a nice day 🙂
Categories: Algorithm, Development, Objective-C, Sort, Swift
Leave a Reply