[Algorithm] Heap

2024.02.12 수정
아래 글 구현으로 하면 일부 문제를 통과할 수 없습니다.
ex) https://www.acmicpc.net/problem/1162
쉬프트 다운 할 때 sorted, filter를 연속으로 사용하는 부분에서 시간 초과의 원인이 되네요
다음과 같이 수정하면 통과할 수 있습니다.

final class Heap<T: Comparable> {
    private var nodes: [T] = []
    private let sort: (T, T) -> Bool
    
    init(_ sort: @escaping ((T, T) -> Bool)) {
        self.sort = sort
    }
    
    var isEmpty: Bool {
        nodes.isEmpty
    }
    
    func insert(_ data: T) {
        var index = nodes.count
        nodes.append(data)
        
        while index >= 0, sort(nodes[index], nodes[(index-1) / 2]) {
            nodes.swapAt(index, (index - 1) / 2)
            index = (index-1) / 2
        }
    }
    
    func delete() -> T {
        if nodes.count == 1 {
            return nodes.removeLast()
        }
        
        let data = nodes.first!
        nodes.swapAt(0, nodes.count - 1)
        nodes.removeLast()
        
        let limit = nodes.count
        var index = 0
        
        while index < limit {
            let leftChild = index * 2 + 1
            let rightChild = leftChild + 1
            var candidate = index

            if leftChild < limit && sort(nodes[leftChild], nodes[candidate]) {
                candidate = leftChild
            }

            if rightChild < limit && sort(nodes[rightChild], nodes[candidate]) {
                candidate = rightChild
            }

            if candidate == index {
                break
            }
            nodes.swapAt(index, candidate)
            index = candidate
        }
        
        return data
    }
}

Swift로 우선순위 큐를 구현하려면 직접 힙을 구현해야한다.
여기 Swift로 구현한 힙이 있습니다. 찾은 자료중 가장 깔끔한것 같아요.

final class Heap<T: Comparable> {
    private var nodes: [T] = []
    private let sort: (T, T) -> Bool
    
    init(sort: @escaping ((T, T) -> Bool)) {
        self.sort = sort
    }
    
    var isEmpty: Bool {
        nodes.isEmpty
    }
    
    func insert(_ data: T) {
        var index = nodes.count
        nodes.append(data)
        
        while index >= 0, sort(nodes[index], nodes[(index-1) / 2]) {
            nodes.swapAt(index, (index - 1) / 2)
            index = (index-1) / 2
        }
    }
    
    func delete() -> T {
        if nodes.count == 1 {
            return nodes.removeFirst()
        }
        
        let data = nodes.first!
        nodes.swapAt(0, nodes.count - 1)
        nodes.removeLast()
        
        let limit = nodes.count
        var index = 0
        
        while index < limit {
            let leftChild = index * 2 + 1
            let rightChild = leftChild + 1
            
            let children = [leftChild, rightChild]
            .filter { $0 < limit && sort(nodes[$0], nodes[index]) }
            .sorted { sort(nodes[$0], nodes[$1]) }
            
            if children.isEmpty { break }
            nodes.swapAt(index, children.first!)
            index = children.first!
        }
        
        return data
    }
}

let heap = Heap<Int>(sort: < )