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


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


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)


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:


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


    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]
        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.remove(at: 0))

swift heap output

This brings an end to this tutorial on Swift Heap.


  1. Fred Gannett says:

    Thanks for the post – helps to have some practical code when reviewing a topic.

    Just couple of things. Would be handy to know version of swift used. I tried the code in
    $ swift -v
    Apple Swift version 4.2.1 (swiftlang-1000.11.42 clang-1000.11.45.1)

    and needed to fix a couple of things.

    struct Heap {
    var elements = [T]()


    struct Heap {
    var elements: [T] = []

    and the } at the end of the first frame needs to move to the bottom of the last frame to encompass all the code into the strict definition

    The heap.swift:116:7: warning: expression implicitly coerced from ‘Int?’ to ‘Any’
    print(heap.remove(at: 0))

    can be fixed by
    print(heap.remove(at: 0)!)


Comments are closed.

Generic selectors
Exact matches only
Search in title
Search in content