우선순위 큐

안녕하세요. 그린입니다🟢

이번 포스팅에서는 우선순위 큐를 Swift로 구현하는것에 대해 알아보겠습니다🧑🏻‍💻

 

먼저 우선순위 큐가 무엇인지? 간단히 알아보겠습니다!

우선순위 큐

 : 우선순위를 가진 자료들의 큐로 순위가 높은 자료가 먼저 실행 (FIFO)

 -> 힙구조

 -> 완전이진트리 (힙은 완전이진트리)

 -> 완전이진트리: 마지막 노드 레벨외 나머지 노드 레벨이 전부 채워진 형태의 이진트리

 -> 힙활용: 최대,최소 계산 / 힙정렬(우선순위큐)

 -> 스위프트에서는 배열로 표현하는게 효율적

 -> 노드 레벨이 올라갈수록 노드 수 2배씩 증가

 -> 부모노드 i / 자식노드: 2i+1 / 2i+2

 -> 트리는 O(log n) / 배열은 O(1)

 

Swift 코드로 구현하기

import Foundation

struct Heap<T: Comparable> {
    var nodes: [T] = []
    let sort: (T,T) -> Bool
    
    init(sort: @escaping (T,T) -> Bool) {
        self.sort = sort
    }
    
    // Heap에 데이터 추가 (push)
    mutating func insert(_ element: T) {
        let count = nodes.count
        nodes.append(element)
        
        up(count - 1)
    }
    
    // Heap에서 데이터 꺼내면서 삭제 (pop)
    mutating func delete() -> T? {
        if nodes.isEmpty {
            return nil
        }
        if nodes.count == 1 {
            return nodes.removeFirst()
        }
        nodes.swapAt(0, nodes.count - 1)
        
        let result = nodes.removeLast()
        down(0)
        
        return result
    }
    
    // Heap에서 특정 데이터 삭제
    mutating func remove(_ element: T) {
        if let index = nodes.firstIndex(of: element) {
            nodes.swapAt(index, nodes.count - 1)
            nodes.removeLast()
            up(index)
            down(index)
        }
    }
    
    // Heap에서 데이터 전체 삭제
    mutating func removeAll(_ element: T) {
        var count = nodes.count
        remove(element)
        while nodes.count < count {
            remove(element)
            count = nodes.count
        }
    }
    
    // Heap에서 첫 데이터 pop
    func peek() -> T? {
        return nodes.first
    }
    
    // Heap 데이터 아래방향으로 비교 정렬
    mutating func down(_ index: Int) {
        var index = index
        let count = nodes.count
        while 2 * index + 1 < count {
            var i = 2 * index + 1
            if i < (count - 1) && sort(nodes[i], nodes[i + 1]) {
                i += 1
            }
            if !sort(nodes[index], nodes[i]) {
                break
            }
            nodes.swapAt(index, i)
            index = i
        }
    }
    
    // Heap 데이터 윗방향으로 비교 정렬
    mutating func up(_ index: Int) {
        var index = index
        while index > 0 && !sort(nodes[(index - 1) / 2], nodes[index]) {
            nodes.swapAt((index - 1) / 2, index)
            index = (index - 1) / 2
        }
    }
}

var queue: Heap<Int> = Heap<Int>() {
    return $0 > $1
}
queue.insert(3)
queue.insert(5)
queue.insert(2)
queue.insert(1)
queue.insert(6)
queue.insert(7)
queue.insert(4)
// nodes: [7, 5, 6, 1, 3, 2, 4] -- 결과값

위와 같이 코드로 구현을 해봤습니다.

데이터들이 들어올때 부모 노드와 비교하여줍니다. 그리고 추가/삭제 등이 일어날때 해당되는 up/down 메서드를 통해 비교 탐색하며 스왑해주며 우선순위 큐에 맞게 다시 정렬해줍니다.

최종 아래에 값들을 추가해주고 찍어보면 우선순위대로 노드 레벨간 지정이 되있음을 확인할 수 있습니다.