[알고리즘 /Swift] 우선순위 큐

0. 스위프트에는 왜 우선순위 큐가 없을까?

스위프트는 우선순위 큐가 기본적으로 없다. 정확히 말하자면 개념이 없다기 보다 구현이 안되어 있다.

iOS 단독 언어인 주제에 구현되어있지 않다니... 이 이자식!

파이썬은 멀티 쓰레드 버전 / Unsafe 멀티 쓰레드 버전 구분되어 있어서 때에 따라서 다르게 쓰는데

스위프트는 없다. 

그럼 직접 구현해야지 뭐... 힙을 이용해서 구현해보자.

1. 코드

import Foundation

struct Heap<T> {
    var nodes = [T]()
    var isEmpty: Bool {
        nodes.isEmpty
    }
    var sort: (T, T) -> Bool
    
    mutating func insert(_ ele: T) {
        nodes.append(ele)
        
        swapUp(nodes.count - 1)
    }
    
    mutating private func swap(_ index1: Int, _ index2: Int) {
        guard index1 < nodes.count, index2 < nodes.count else { return }
        
        let temp = nodes[index1]
        nodes[index1] = nodes[index2]
        nodes[index2] = temp
    }
    
    mutating private func swapUp(_ index: Int) {
        guard index < nodes.count else { return }
        var index = index
        
        while index != 0 {
            let parent = index / 2
            
            if sort(nodes[index], nodes[parent]) {
                swap(parent, index)
                index = parent
            } else {
                return
            }
        }
    }
    
    mutating func pop() -> T? {
        swap(0, nodes.count - 1)
        
        defer {
            nodes.removeLast()
            swapDown(0)
        }
        
        return nodes.last
    }
    
    mutating func swapDown(_ index: Int) {
        var index = index
        
        while true {
            let right = (index + 1) * 2
            let left = right - 1
            var target = index
            if left < nodes.count && sort(nodes[left], nodes[target]) {
                target = left
            }
            
            if right < nodes.count && sort(nodes[right], nodes[target]) {
                target = right
            }
            
            if target == index {
                return
            } else {
                swap(target, index)
                index = target
            }
        }
    }
}