Heap data structure

July 18, 2024 • 4 min read • #swift, #interview

A heap is a specialized tree-based data structure that satisfies the heap property. There are two types of heaps:

Max-Heap: In a max-heap, the key at the root must be the maximum among all keys present in the binary heap. The same property must be recursively true for all nodes in the binary tree.
Min-Heap: In a min-heap, the key at the root must be the minimum among all keys present in the binary heap. The same property must be recursively true for all nodes in the binary tree.

Heaps are commonly used to implement priority queues, where the highest (or lowest) priority element is always at the root.

Operations

Insert: Add a new key to the heap.
Extract-Max / Extract-Min: Remove the maximum (or minimum) key from the heap.
Peek: Get the maximum (or minimum) key without removing it.
Heapify: Ensure the heap property is maintained.

Example Implementation in Swift

Here is an example implementation of a Min-Heap in Swift:

import Foundation

struct MinHeap {
    private var heap: [Int] = []

    var isEmpty: Bool {
        return heap.isEmpty
    }

    var count: Int {
        return heap.count
    }

    func peek() -> Int? {
        return heap.first
    }

    mutating func insert(_ value: Int) {
        heap.append(value)
        heapifyUp(from: heap.count - 1)
    }

    mutating func extractMin() -> Int? {
        guard !heap.isEmpty else { return nil }
        if heap.count == 1 {
            return heap.removeFirst()
        } else {
            let min = heap[0]
            heap[0] = heap.removeLast()
            heapifyDown(from: 0)
            return min
        }
    }

    private mutating func heapifyUp(from index: Int) {
        var childIndex = index
        let childValue = heap[childIndex]
        var parentIndex = (childIndex - 1) / 2

        while childIndex > 0 && childValue < heap[parentIndex] {
            heap[childIndex] = heap[parentIndex]
            childIndex = parentIndex
            parentIndex = (childIndex - 1) / 2
        }

        heap[childIndex] = childValue
    }

    private mutating func heapifyDown(from index: Int) {
        let count = heap.count
        var parentIndex = index

        while true {
            let leftChildIndex = 2 * parentIndex + 1
            let rightChildIndex = 2 * parentIndex + 2
            var optionalParentIndex = parentIndex

            if leftChildIndex < count && heap[leftChildIndex] < heap[optionalParentIndex] {
                optionalParentIndex = leftChildIndex
            }

            if rightChildIndex < count && heap[rightChildIndex] < heap[optionalParentIndex] {
                optionalParentIndex = rightChildIndex
            }

            if optionalParentIndex == parentIndex {
                return
            }

            heap.swapAt(parentIndex, optionalParentIndex)
            parentIndex = optionalParentIndex
        }
    }
}

// Example Usage
var minHeap = MinHeap()
minHeap.insert(3)
minHeap.insert(1)
minHeap.insert(6)
minHeap.insert(5)
minHeap.insert(2)
minHeap.insert(4)

print("Min-Heap elements in ascending order:")
while !minHeap.isEmpty {
    print(minHeap.extractMin()!)
}

The output of the above code should be

Min-Heap elements in ascending order:
1
2
3
4
5
6

Explanation

Insert Operation: The insert function adds a new element to the heap and then ensures the heap property by moving the new element up (heapifyUp).
Extract-Min Operation: The extractMin function removes the root element (the minimum element in a min-heap) and then ensures the heap property by moving the new root element down (heapifyDown).

This implementation ensures that both insertion and extraction operations maintain the min-heap property, allowing efficient access to the minimum element.

Operations

Example Implementation in Swift

Explanation

Further Reading