들어가며
Swift는 따로 우선순위 큐(Periority Queue)를 제공하지 않습니다. 오늘은 우선순위 큐에 대해서 알아보고, 직접 Swift로 구현해보도록 하겠습니다.
Periority Queue 자료구조
우선순위 큐(Periority Queue)는 큐(Queue)에서 우선순위라는 개념이 도입된 자료구조입니다. 우선순위에 의해서 우선순위가 큰 요소를 먼저 큐에서 내보내게 됩니다. 이러한 자료구조 특징에 따라서 알고리즘 문제풀이에서 자주 사용됩니다.
기존의 큐에대한 자료구조는 하단의 링크를 통해서 알아볼 수 있습니다.
[Swift]Queue 자료구조를 구현해보자
우선순위 큐는 시간복잡도를 단축하기 위하여 큐와는 다르게 선형적 자료구조가 아니라 비선형적 자료구조의 특성을 갖습니다. 바로 힙(Heap) 자료구조입니다.
힙은 정렬 방식에 따라서 최소 힙, 최대 힙으로 나뉩니다. 위의 예시는 최대 힙의 예시입니다. 루트 노드에는 가장 큰 값이 위치하고, 트리를 이루면서 점점 작은 값이 정렬됩니다. 오직 루트 노드에서 값이 삽입되거나 삭제됩니다.
값이 삽입되거나 삭제되면, 힙 자료구조를 유지하기 위해서 내부에서 정렬조건을 맞추기 위하여 재정렬(heapify)을 수행하게 됩니다. 하단은 7이라는 원소가 삭제된 후의 재정렬을 수행한 힙 자료구조의 도시화입니다.
Heap 자료구조의 인덱스
사실상 우선순위 큐는 힙 자료구조를 통해서 구현하기에 힙 자료구조를 구현한 후 우선순위 큐로써 사용하면 됩니다.
그 전에, 힙 자료구조를 구현하기 위해서는 힙 자료구조의 인덱스에 대해서 알아볼 필요가 있습니다. 힙 자료구조에서는 인덱스를 루트 노드에서부터 마지막 노드까지 위에서 아래로, 왼쪽에서 오른쪽으로 하나씩 인덱스를 지정합니다. 또한, 부모 노드는 자식 노드를 최대 2개까지만 가질 수 있으며, 부모 노드의 인덱스는 자식 노드의 인덱스를 나눈 몫과 같다는 규칙을 갖습니다.
이러한 인덱스 규칙을 알고있어야, heapify와 swap을 수행할 수 있습니다.
Periority Queue 구현
이제부터 우선순위 큐를 구현해보도록 하겠습니다. 사실상 힙 자료구조와 동일하기에 힙 자료구조의 구현이라고도 할 수 있습니다.
힙(Max Heap) 기본 기능
우선은 최대 힙을 구현하고 이후에 최소힙으로 확장하도록 하겠습니다. 우선 원소는 배열을 통해서 저장할 수 있습니다.
struct Heap<T : Comparable> {
private var data : [T] = []
private let compare : (T, T) -> Bool
init(compare : @escaping (T, T) -> Bool) {
self.compare = compare
}
var isEmpty : Bool {
return data.isEmpty
}
var count : Int {
return data.count
}
}우선은 데이터를 저장할 data와 isEmpty, count getter를 지정했습니다.
데이터의 삽입
힙 자료구조는 데이터를 삽입하려면 기본적으로 가장 마지막 인덱스에 값을 삽입하게 됩니다. 이후에 데이터의 heapify를 수행하여 힙 자료구조의 재정렬을 수행합니다. 이러한 과정은 siftUp함수를 통해서 수행하도록 하겠습니다.
struct Heap<T : Comparable> {
...
// 원소 삽입
mutating func enqueue(_ element : T) {
data.append(element)
siftUp(from: data.count - 1)
}
// 삽입 후 재정렬
mutating func siftUp(from index : Int) {
var childIndex = index
let child = data[childIndex]
var parentIndex = (childIndex - 1) / 2
// 자식 노드의 인덱스가 0보다 크고,
// 자식이 부모보다 우선순위가 크다면 반복해서 정렬 수행
while childIndex > 0 && compare(child, data[parentIndex]) {
data[childIndex] = data[parentIndex]
childIndex = parentIndex
parentIndex = (childIndex - 1) / 2
}
data[childIndex] = child
}
}삽입된 데이터는 마지막 노드에 저장됩니다. 예를 들어, 아래와 같은 상황이 펼쳐집니다.
이때, 트리는 최대 힙 자료구조를 만족하기 위해서 heapify(siftUp)을 수행해야만 합니다. siftUp은 마지막 노드부터 아래와 같은 연산을 수행합니다.
- 자식 노드에 대한 부모 노드 인덱스를 찾는다.
- 자식 노드의 인덱스가 유효하고 자식 노드와 부모 노드의 관계가 compare 연산과 일치하지 않는 경우, 두 노드의 데이터를 서로 교환한다.
- 부모 노드에서 다시 2번 연산을 반복한다.
- 교환이 모두 종료되면, 최종적으로 지정된 자식 노드에 새로 삽입된 데이터를 지정한다.
이러한 연산을 수행하면 7은 최대 힙 자료구조에 맞는 위치에 지정됩니다. 그리고 이러한 과정은 삽입에서 의 시간복잡도가 수행되고, siftUp은 이 소요되므로 최종적으로 의 시간복잡도를 갖습니다.
데이터의 삭제 및 추출
swift에서 효율적으로 데이터를 삭제하기 위해서는 가장 마지막 노드의 데이터를 삭제해야 합니다. 따라서, 데이터를 삭제 및 추출을 위해서 루트 노드의 데이터를 마지막 노드의 데이터와 바꾸고, 데이터를 추출하고난 뒤 데이터를 재정렬하면 됩니다.
struct Heap<T : Comparable> {
...
mutating func dequeue() -> T? {
guard !elements.isEmpty else { return nil }
if elements.count == 1 { return elements.removeLast() }
let root = elements[0]
elements[0] = elements.removeLast()
siftDown(from: 0)
return root
}
...
private mutating func siftDown(from index: Int) {
var parentIndex = index
let count = elements.count
while true {
// 부모 노드의 자식 노드의 인덱스를 구함
let leftChildIndex = 2 * parentIndex + 1
let rightChildIndex = 2 * parentIndex + 2
var swapIndex = parentIndex
// 두개의 자식 노드가 부모 노드보다 큰 경우 스왑
if leftChildIndex < count && compare(elements[leftChildIndex], elements[swapIndex]) {
swapIndex = leftChildIndex
}
if rightChildIndex < count && compare(elements[rightChildIndex], elements[swapIndex]) {
swapIndex = rightChildIndex
}
// 만약 부모 인덱스와 스왑 인덱스가 같은 경우에는 자식 노드 모두 힙 구조를 만족함.
// 이때, 하위 트리는 모두 만족할 수 밖에 없으므로 재정렬 종료
if swapIndex == parentIndex { break }
// 그렇지 않다면 스왑 후 스왑된 자식 노드부터 다시 진행
elements.swapAt(parentIndex, swapIndex)
parentIndex = swapIndex
}
}
}삭제를 수행하기 위해 루트 노드를 마지막 노드와 바꾸면 아래와 같습니다.
이후에는 removeLast()를 통해서 의 시간복잡도를 통해 데이터를 삭제할 수 있지만, 역시나 힙 자료구조의 정렬 조건을 만족하지 못하기에 siftDown()을 수행합니다. 아래와 같이 연산을 수행합니다.
- 루트 노드부터 자식 노드와 compare 연산을 수행.
- 1-1. compare 연산을 만족하지 못하면 자식 노드와 부모 노드의 위치 스왑
- 1-2. 스왑된 인덱스부터 1번 연산을 다시 수행.
- 모두 compare를 만족하면 정렬 종료
이러한 연산을 수행하게 되면, 마찬가지로 트리를 순회하면서 교환을 진행하기에 의 시간복잡도를 갖게 됩니다.
최종 구현 코드
struct Heap<T : Comparable> {
private var data : [T] = []
private let compare : (T, T) -> Bool
init(compare : @escaping (T, T) -> Bool) {
self.compare = compare
}
var isEmpty : Bool {
return data.isEmpty
}
var count : Int {
return data.count
}
mutating func enqueue(_ element : T) {
data.append(element)
siftUp(from: data.count - 1)
}
mutating func dequeue() -> T? {
guard !data.isEmpty else { return nil }
if data.count == 1 { return data.removeLast() }
let root = data[0]
data[0] = data.removeLast()
siftDown(from: 0)
return root
}
private mutating func siftUp(from index : Int) {
var childIndex = index
let child = data[childIndex]
var parentIndex = (childIndex - 1) / 2
while childIndex > 0 && compare(child, data[parentIndex]) {
data[childIndex] = data[parentIndex]
childIndex = parentIndex
parentIndex = (childIndex - 1) / 2
}
data[childIndex] = child
}
private mutating func siftDown(from index : Int) {
var parentIndex = index
let count = data.count
while true {
let leftChildIndex = 2 * parentIndex + 1
let rightChildIndex = 2 * parentIndex + 2
var swapIndex = parentIndex
if leftChildIndex < count && compare(data[leftChildIndex], data[swapIndex]) {
swapIndex = leftChildIndex
}
if rightChildIndex < count && compare(data[rightChildIndex], data[swapIndex]) {
swapIndex = rightChildIndex
}
if swapIndex == parentIndex { break }
data.swapAt(parentIndex, swapIndex)
parentIndex = swapIndex
}
}
}