우선순위 큐(Priority Queue)
- 우선순위 큐는 힙(heap)을 이용해 가장 높은 우선순위의 요소를 가장 처음에 위치시키는 큐(queue)이다.
→ 그렇다면 힙(heap)이란 무엇일까
힙은 완전이진트리를 사용해서, 데이터들을 반정렬 상태로 유지하는 자료구조이다.
(배열을 사용해서 parent, child의 노드를 통해 insert, pop 했던 그런…)
어짜피 우선순위 큐의 대부분의 요소는 힙을 기반으로 이루어져있으므로, 한꺼번에 살펴보도록 하자.
struct priorityQueue<T> {
...
}일단 queue는 구조체로 구현된다. class가 아닌 struct로 구현하는게 좋은 이유는 대충은 알겠지만, 명확하게 짚자면, 이런 부분들 때문에 구조체로 만들어진다.
또한, T를 붙혀서 제네릭 타입이라는 것을 명시해준다.
Generic 타입을 사용하면, 타입에 의존하지 않는 범용 코드를 작성할 수 있다는 장점이 있다.
var nodes = Array<T>()
let sort:(T,T) -> Bool
init(sort: @escaping (T,T) -> Bool) {
self.sort = sort
}실제 배열이 되는 nodes 또한 제네릭 타입으로 명시하고, sort라는 클로저를 생성자의 인자로 받는다.
이를 통해 Priority Queue가 생성될 때 우선순위가 되는 기준 또한 유동적으로 설정할 수 있다.
→ 여기서 @escaping이 쓰인 이유가 궁금해서 찾아봤다.
보통 escaping closure는 비동기처리에만 쓰인다고 알고 있었는데, 그것 외에도, 클로저가 함수 외부의 다른 변수(let sort)에 저장될 때 또한 escaping closure로 받아주어야 한다고 한다.
var isEmpty: Bool {
return nodes.isEmpty
}
var count: Int {
return nodes.count
}isEmpty와 count같은 경우 computed property로 구현한다. 때문에 타입을 명시해주고, get-only이기 때문에 return을 제외한 다른 요소들은 생략해준다.
→ 그렇다면 function이 아닌 computed property를 사용하는 이유는 무엇일까.
이유는 해당 속성의 값을 동적으로 계산하기 위해서이다. 함수를 사용하면 항상 함수를 실행해야 값이 반환되는데, computed property는 값을 직접 저장하는 것이 아닌 getter를 통해 속성의 값을 확인할 수 있어 더 효율적이다. - 코드 또한 간결하고 직관적이게 된다.
func leftChild(of parentIndex: Int) -> Int {
return parentIndex * 2 + 1
}
func rightChild(of parentIndex: Int) -> Int {
return parentIndex * 2 + 2
}
func parentIndex(of childIndex: Int) -> Int {
return (childIndex - 1) / 2
}
완전 이진트리의 개념을 사용하기 때문에, leftChild, rightChild, parent의 index를 구해주는 함수를 구현해준다. 이진트리이기 때문에 이를 활용해서 childIndex = parentIndex*2 + 1 or + 2로 계산해주면 쉽다.
mutating func shiftUp(from index: Int) {
var child = index
var parent = parentIndex(of: child)
while child > 0 && sort(nodes[child], nodes[parent]) {
nodes.swapAt(child, parent)
child = parent
parent = parentIndex(of: child)
}
}
mutating func push(_ element: T) {
nodes.append(element)
shiftUp(from: count-1)
}push 부분 구현에서는, left, right를 따질 필요가 없으므로, append가 된 element가 parent의 sort() 기준을 만족시킬때까지 swap을 해주면 끝이다. (혹은 현재 위치가 정상이 아닐 때까지)
mutating func shiftDown(from index: Int) {
var parent = index
while true {
let left = leftChild(of: parent)
let right = rightChild(of: parent)
var candidate = parent
if left < count && sort(nodes[left], nodes[candidate]) {
candidate = left
}
if right < count && sort(nodes[right], nodes[candidate]) {
candidate = right
}
if candidate == parent {
return
}
nodes.swapAt(candidate, parent)
parent = candidate
}
}
mutating func pop() -> T? {
guard !isEmpty else { return nil }
nodes.swapAt(0, count-1)
defer { shiftDown(from: 0) }
return nodes.removeLast()
}pop부분 구현에서는 먼저, top node가 pop이 되면 완전 이진트리 자체가 깨져버린다. 그래서
- top node와 last node를 먼저 swap하여 위치를 바꾸고
- pop()을 진행해서 바뀐 last node를 방출한 뒤
- top node의 위치에 있던 last node를 원래 위치로 바꾸어주는 동작을 거친다.
이 때는, push부분과는 다르게 parent위치에서 child쪽으로 내려가는 것이므로, left, right 둘 중 어느 곳으로 갈 것인지 판별을 해주어야 한다.
그래서 먼저 left의 조건에 만족하면 candidate(기준점)을 leftChild와 바꾸고, 바꾼 candidate가 right의 조건에도 만족하면 right로 바꾸는 방식으로 판별을 한다.
이 때, pop() 함수에서 defer을 사용하여 shiftDown을 진행하는데, defer 함수에 들어있는 부분은 return이 실행된 다음에 실행되기 때문에, removeLast()가 된 후 이루어져야하는 정렬같은 경우에는 defer를 사용하는 것이 가장 명료한 방법이라고 생각했다.
참조
