Swift Heap Data Structure

Filed Under: Swift

In this tutorial, we’ll be discussing and implementing Heap data structures in Swift.

Swift Heap

Heap can be either a max heap or a min heap.
In a max heap, the root node is the largest element and all the child nodes must be smaller than the parent. Min-heap works just the opposite way.
A heap is a specialized tree-based data structure.
The Heap data structure can be used to efficiently find the kth smallest (or largest) element in an array.

Heap Property:
If P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C.

Nodes at the top are highest priority ones.

An illustration of a min heap is:
swift heap data structure illustration

Heapify

Removing an element requires a rearrange of the heap data structure. This is termed as heapifying.

For example, if you delete the root node of the heap. For that, we need to swap it with the lowest node with the root node and then check the heap property recursively throughout.

heapifyUp() starts from the bottom and checks the heap properties all the way up.

heapifyDown() does just the opposite

Children of a node at N would be positioned at 2n+1 and 2n+2 in a max heap.

Let’s launch our XCode playground and create our heap using Swift.
We’ll build a heap structure using an array.

Building a Heap


struct Heap<T> {
    var elements = [T]()
    
    var isEmpty: Bool { return elements.isEmpty }
    var count: Int { return elements.count }
    var isOrdered: (T, T) -> Bool
    
    public init(sort: @escaping (T, T) -> Bool) {
        self.isOrdered = sort
    }

}

An escaping closure is passed which is used to save the function values. It compares the two values passed.

Add the following functions in the struct to get the indexes of the parent, left and right nodes:


func parentOf(_ index: Int) -> Int {
        return (index - 1) / 2
    }
    func leftOf(_ index: Int) -> Int {
        return (2 * index) + 1
    }
    func rightOf(_ index: Int) -> Int {
        return (2 * index) + 2
    }

heapifyDown():


mutating func heapifyDown(index: Int, heapSize: Int) {

        var parentIndex = index
        
        while true {
            let leftIndex = self.leftOf(parentIndex)
            let rightIndex = leftIndex + 1
            
            var first = parentIndex
            if leftIndex < heapSize && isOrdered(elements[leftIndex], elements[first]) {
                first = leftIndex
            }
            if rightIndex < heapSize && isOrdered(elements[rightIndex], elements[first]) {
                first = rightIndex
            }
            if first == parentIndex { return }
            
            elements.swapAt(parentIndex, first)
            parentIndex = first
        }
    }

mutating func shiftDown() {
        heapifyDown(index: 0, heapSize: elements.count)
    }

heapifyDown() is used while removing elements. heapifyUp() is used while inserting.

The following function is used to build the heap from the array:


mutating func buildHeap(fromArray array: [T]) {
        elements = array
        for i in stride(from: (elements.count/2 - 1), through: 0, by: -1) {
            heapifyDown(index: i, heapSize: elements.count)
        }
    }

heapifyUp():


mutating func heapifyUp(index: Int) {
        var nodeIndex = index
        
        while true {
            let parentIndex = self.parentOf(nodeIndex)
            
            var first = parentIndex
            if parentIndex >= 0 && isOrdered(elements[nodeIndex], elements[first]) {
                first = nodeIndex
            }
            if first == parentIndex { return }
            

            elements.swapAt(parentIndex, first)
            nodeIndex = first
        }
    }

The following functions are used to insert and remove the elements from the heap:

Insert:


mutating func insert(value: T) {
        self.elements.append(value)
        
        heapifyUp(index: self.elements.count - 1)
    }
    

Remove:


    public mutating func remove(at index: Int) -> T? {
        let temp: T
        
        if index < 0 && count - 1 <= index {
            return nil
        }
        temp = elements[index]
        elements[index] = elements[count - 1]
        elements.removeLast()
        shiftDown()
        return temp
    }

Let’s use a sample input to test the above structure we’ve created:


let array: [Int] = [12,3,6,15,45,1,2]
var heap = Heap<Int>(sort: >)
heap.buildHeap(fromArray: array)
heap.insert(value: 23)
print(heap.elements)
print(heap.remove(at: 0))
print(heap.elements)

swift heap output

This brings an end to this tutorial on Swift Heap.

Leave a Reply

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

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages