[iOS CS Study] 우선순위 큐(Priority Queue)

21.06.26

공부한 것을 정리하는 용도의 글이므로 100% 정확하지 않을 수 있습니다.
참고용으로만 봐주시고, 내용이 부족하다고 느끼신다면 다른 글도 보시는 것이 좋습니다.
+ 틀린 부분, 수정해야 할 부분은 언제든지 피드백 주세요. 😊

                                                 by. ryalya

들어가기 전
이전 글에서 스택&큐에서 큐에 대해 간단하게 알아보았었다.

간단하게 다시 리마인딩해보자면, Queue는 아래와 같다.

 - FIFO(First-in First-out) = 선입선출
 - 넣은 순서 그대로 나옴. (먼저 들어간 데이터가 먼저 나감)
 - Linked List의 구현체.
 - 대표적인 예시로는 은행 창구 대기줄
 - 입구와 출구가 따로 있다고 생각하면 쉽다.

Priority Queue란?

위에서 리마인딩 했듯이, Queue는 FIFO(선입선출) 형식의 자료구조이다.
하지만, Priority Queue(우선순위 큐)는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나온다.

일반적인 Queue는 아래와 같이 선형적인 구조를 가지고 있다.

하지만 Priority Queue의 구조는 아래와 같이 트리 구조로 봐야 한다.

자료구조 heap에서 heap은 우선순위 큐를 위하여 만들어진 자료구조라고 했었다.

이는 우선순위 큐가 힙(Heap)이라는 자료구조로 구현할 수 있기 때문이다.

그런데 배열이나 링크드리스트로도 우선순위 큐를 구현할 수 있는데 왜 힙으로 구현해야 한다는 걸까?

ChanBLOG에서 본 내용이 이해가 잘 되어 그대로 가져왔다. 😊

배열 / 링크드리스트로 우선순위 큐를 구현하지 않는 이유

❌ 배열

우선 순위가 높은 순서대로 배열의 가장 앞부분부터 넣는다면, 우선순위가 높은 데이터를 반환하는 것은 맨 앞의 인덱스를 바로 이용하면 되므로 어렵지 않다.

하지만 우선순위가 중간인 것이 들어가야 하는 삽입 과정에서는 뒤의 데이터까지 인덱스를 모두 한 칸씩 뒤로 밀어야 하는 단점이 있다.

최악의 경우 삽입해야 하는 위치를 찾기 위해 모든 인덱스를 탐색해야 한다.

즉 이 때의 시간 복잡도는 자료가 n개라고 할 때 O(n) 이 되는데
→ 배열로 구현 시 시간 복잡도 : 삭제는 O(1), 삽입은 O(n)

❌ 링크드리스트

우선 순위가 높은 순서대로 연결을 시키면, 우선순위가 높은 데이터의 반환은 배열과 마찬가지로 쉽다.

하지만 연결리스트 또한 삽입의 과정 또한 배열과 마찬가지로 그 위치를 찾아야 한다.

최악의 경우 맨 끝에까지 가게 됨.
→ 연결리스트로 구현 시 시간 복잡도 : 삭제는 O(1), 삽입은 O(n)

⭕️ 힙

힙의 경우 삭제나 삽입 과정에서 모두 부모와 자식 간의 비교만 계속 이루어진다.

이진 트리의 높이가 하나 증가할 때마다 저장 가능한 자료의 갯수는 2배 증가하며, 비교 연산 횟수는 1회 증가.

즉, 삭제나 삽입 모두 최악의 경우에는 O(log2n) 의 시간 복잡도를 가짐.
→ 연결리스트로 구현 시 시간 복잡도 : 삭제는 O(log2n), 삽입은 O(log2n)

이처럼 배열이나 연결 리스트가 삭제에서는 시간 복잡도의 우위를 점할지라도, 삽입의 시간 복잡도가 힙 기반이 월등하기 때문에, 편차가 심한 배열과 연결리스트보다는 힙으로 구현하는 것!!!!

아래는 자료구조 우선순위 큐와 힙에서 가져온 시간복잡도를 정리한 표.

Priority Queue 구현

Priority Queue의 연산은 heap을 활용하기 때문에 heap과 같다고 생각하면 된다.

새로운 노드를 넣을땐 제일 끝에서 추가해서 자신의 부모의 인덱스인 (index-1)/2와 비교해서 거꾸로 올라오면서 힙 조건에 맞는지 비교하며 조건에 맞을 때까지 부모와 자식의 위치를 교체한다.

삭제할 때 역시 위(루트)노드를 삭제 후, 가장 마지막 노드를 루트 자리로 삽입하여 아래로 가며 힙 조건을 비교하며, 조건에 맞을 때까지 부모와 자식의 위치를 교체한다.

Swift를 이용하여 Priority Queue를 구현한 코드는 아래와 같다.
Priority Queue 우선순위 큐 에서 가져왔다.

Heap 구현

struct Heap<T: Comparable> {
    var nodes: [T] = []
    let sort: (T,T) -> Bool
    
    init(sort: @escaping (T,T) -> Bool) {
        self.sort = sort
    }

insert (push)

    // Heap에 데이터 추가 (push)
    mutating func insert(_ element: T) {
        let count = nodes.count
        nodes.append(element)
        
        up(count - 1)
    }

delete (pop)

    // 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)], 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] -- 결과값

예시 코드를 통해 구현하는 것이 어렵지 않은 것은 이해했다.

그런데 스위프트에서는 배열로 표현하는게 효율적? 이라는 말을 봤는데 이게 무슨말일까?

Reference

배열/링크드리스트로 우선순위 큐를 구현하지 않는 이유 : ChanBLOG

시간복잡도 표 : 자료구조 우선순위 큐와 힙

Priority Queue 구현 : Priority Queue 우선순위 큐