Implementing Heaps Fast AF

A heap is a data structure that follows a specific set of rules in order to maintain a specific ordering among its elements. Heaps are commonly used in a variety of algorithms, including sorting and priority queues. In this tutorial, we will implement a heap in Swift and discuss the underlying principles of how it works.

Implementation

To begin, we need to create a class that will represent our heap. We will start by declaring a simple structure to hold our elements:

struct Heap<T> {
    var elements: [T]
}

Next, we need to define the rules that determine the order of our elements. In a heap, elements are either greater than or less than their children, depending on whether we are implementing a min-heap or a max-heap. For this tutorial, we will implement a min-heap, where the parent element is always less than its children.

To enforce this rule, we will define a function that compares two elements and returns true if the first element is less than the second:

struct Heap<T> {
    var elements: [T]
    
    func isLessThan(_ a: T, _ b: T) -> Bool {
        // Add code to compare a and b and return true if a is less than b
    }
}

Next, we will define a function to add an element to our heap. This function will insert the element at the end of the heap and then rearrange the elements to maintain the heap property.

To do this, we will use a process called “bubbling up.” We start at the newly inserted element and compare it to its parent. If it is less than its parent, we swap the two elements. We then continue this process until we reach the root of the heap or the element is no longer less than its parent.

Here is the code for the add function:

struct Heap<T> {
    var elements: [T]
    
    func isLessThan(_ a: T, _ b: T) -> Bool {
        // Add code to compare a and b and return true if a is less than b
    }
    
    mutating func add(_ element: T) {
        elements.append(element)
        
        var currentIndex = elements.count - 1
        while currentIndex > 0 {
            let parentIndex = (currentIndex - 1) / 2
            if isLessThan(elements[currentIndex], elements[parentIndex]) {
                elements.swapAt(currentIndex, parentIndex)
                currentIndex = parentIndex
            } else {
                break
            }
        }
    }
}

Now that we can add elements to our heap, let’s implement the function to remove the minimum element. This function will remove the root element and replace it with the last element in the heap. Then, we will rearrange the elements to maintain the heap property.

To do this, we will use a process called “sinking down.” We start at the root element and compare it to its children. If it is greater than one of its children, we swap it with the lesser child. We then continue this process until the element is no longer greater than one of its children.

Here is the code for the removeMin function:

struct Heap<T> {
    var elements: [T]
    func isLessThan(_ a: T, _ b: T) -> Bool {
        // Add code to compare a and b and return true if a is less than b
    }

    mutating func add(_ element: T) {
        elements.append(element)
    
        var currentIndex = elements.count - 1
        while currentIndex > 0 {
            let parentIndex = (currentIndex - 1) / 2
            if isLessThan(elements[currentIndex], elements[parentIndex]) {
                elements.swapAt(currentIndex, parentIndex)
                currentIndex = parentIndex
            } else {
                break
            }
        }
    }

    mutating func removeMin() -> T? {
        guard elements.count > 0 else {
            return nil
        }
    
        if elements.count == 1 {
            return elements.removeFirst()
        }
    
        let min = elements[0]
        elements[0] = elements.removeLast()
    
        var currentIndex = 0
        while currentIndex < elements.count {
            let leftChildIndex = currentIndex * 2 + 1
            let rightChildIndex = currentIndex * 2 + 2
        
            var minChildIndex: Int
            if rightChildIndex < elements.count {
                minChildIndex = isLessThan(elements[leftChildIndex], elements[rightChildIndex]) ? leftChildIndex : rightChildIndex
            } else if leftChildIndex < elements.count {
                minChildIndex = leftChildIndex
            } else {
                break
            }
        
            if isLessThan(elements[minChildIndex], elements[currentIndex]) {
                elements.swapAt(minChildIndex, currentIndex)
                currentIndex = minChildIndex
            } else {
                break
            }
        }
    
        return min
    }
}

Conclusion

In this tutorial, we learned how to implement a min-heap in Swift. We discussed the underlying principles of how a heap works and implemented the functions to add and remove elements from the heap.

If you want to learn more about heaps, you can check out the following resources:

• The Swift Standard Library includes a heap data structure in the form of the `Heap` type. You can find more information about it in the
  [documentation](https://developer.apple.com/documentation/swift/heap)
• Wikipedia has a thorough explanation of the different types of heaps and their use cases in
  [this article](https://en.wikipedia.org/wiki/Heap_(data_structure)).

I hope this tutorial was helpful in understanding how to implement and use a heap in your own projects. Happy coding