CS(ComputerScience)
우선순위 큐
GREEN.1229
2021. 5. 17. 14:49
안녕하세요. 그린입니다🟢
이번 포스팅에서는 우선순위 큐를 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 메서드를 통해 비교 탐색하며 스왑해주며 우선순위 큐에 맞게 다시 정렬해줍니다.
최종 아래에 값들을 추가해주고 찍어보면 우선순위대로 노드 레벨간 지정이 되있음을 확인할 수 있습니다.