How do I implement a heap in Swift?

A heap is a specialized tree-based data structure that satisfies the heap property. In Swift, you can implement a binary heap, which can be used for priority queues. Here's how you can create a min-heap and a max-heap in Swift.

Min-Heap Implementation

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

        public var isEmpty: Bool {
            return elements.isEmpty
        }

        public var count: Int {
            return elements.count
        }

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

        public mutating func insert(_ value: Int) {
            elements.append(value)
            bubbleUp(from: elements.count - 1)
        }

        public mutating func remove() -> Int? {
            guard !isEmpty else { return nil }
            if elements.count == 1 { return elements.removeLast() }
            let root = elements[0]
            elements[0] = elements.removeLast()
            bubbleDown(from: 0)
            return root
        }

        private mutating func bubbleUp(from index: Int) {
            var childIndex = index
            let childValue = elements[childIndex]
            var parentIndex = (childIndex - 1) / 2
            while childIndex > 0 && childValue < elements[parentIndex] {
                elements[childIndex] = elements[parentIndex]
                childIndex = parentIndex
                parentIndex = (childIndex - 1) / 2
            }
            elements[childIndex] = childValue
        }

        private mutating func bubbleDown(from index: Int) {
            let count = elements.count
            var parentIndex = index
            let parentValue = elements[parentIndex]

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

                if leftChildIndex < count && elements[leftChildIndex] < elements[candidateIndex] {
                    candidateIndex = leftChildIndex
                }
                if rightChildIndex < count && elements[rightChildIndex] < elements[candidateIndex] {
                    candidateIndex = rightChildIndex
                }
                if candidateIndex == parentIndex { return }
                elements[parentIndex] = elements[candidateIndex]
                parentIndex = candidateIndex
            }
        }
    }
    

Max-Heap Implementation

    struct MaxHeap {
        private var elements: [Int] = []

        public var isEmpty: Bool {
            return elements.isEmpty
        }

        public var count: Int {
            return elements.count
        }

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

        public mutating func insert(_ value: Int) {
            elements.append(value)
            bubbleUp(from: elements.count - 1)
        }

        public mutating func remove() -> Int? {
            guard !isEmpty else { return nil }
            if elements.count == 1 { return elements.removeLast() }
            let root = elements[0]
            elements[0] = elements.removeLast()
            bubbleDown(from: 0)
            return root
        }

        private mutating func bubbleUp(from index: Int) {
            var childIndex = index
            let childValue = elements[childIndex]
            var parentIndex = (childIndex - 1) / 2
            while childIndex > 0 && childValue > elements[parentIndex] {
                elements[childIndex] = elements[parentIndex]
                childIndex = parentIndex
                parentIndex = (childIndex - 1) / 2
            }
            elements[childIndex] = childValue
        }

        private mutating func bubbleDown(from index: Int) {
            let count = elements.count
            var parentIndex = index
            let parentValue = elements[parentIndex]

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

                if leftChildIndex < count && elements[leftChildIndex] > elements[candidateIndex] {
                    candidateIndex = leftChildIndex
                }
                if rightChildIndex < count && elements[rightChildIndex] > elements[candidateIndex] {
                    candidateIndex = rightChildIndex
                }
                if candidateIndex == parentIndex { return }
                elements[parentIndex] = elements[candidateIndex]
                parentIndex = candidateIndex
            }
        }
    }