[Data Structure] Priority Queue

"우선순위 큐"(Priority Queue)는 다음과 같은 2개의 Main Operation을 명세하는 ADT이다.

• enqueue(push): 원소를 추가한다.
• dequeue(pop): 우선순위가 높은 원소를 제거한다.  

지난 포스팅에서 다루었던 "큐"(Queue)는 먼저 들어온 데이터가 먼저 나가는 FIFO의 형태라면, 

"우선순위 큐"(Priority Queue)는 먼저 들어온 데이터가 아닌, 우선순위가 높은 데이터가 먼저 나가는 ADT이다.

 

흔히들 "우선순위 큐는 Heap이다"라고 생각하는데, 이는 잘못된 오류이다. 

우선순위 큐는 ADT일뿐 위에 말한 2개의 Operation만 제공하면 된다. 즉, 스택이 배열, 연결리스트 등으로 다양한 방법으로 구현할 수 있는 것처럼 우선순위 큐도 다양한 방법으로 구현이 가능하다. 

 

즉, 우선순위 큐를 구현해 사용하는 자료구조가 Heap일 뿐이며, 배열과 같은 다른 자료구조로도 구현이 가능하다. 하지만, Heap에서 삽입, 삭제가 O(logN)으로 동작해 가장 효율적이기에 Heap으로 우선순위 큐를 구현한다. 

 

배열 & 연결리스트로 구현 

그렇다면 배열 혹은 연결리스트로 구현하게 되면 어떻게 될까? 

 

만약 배열 혹은 연결리스트를 정렬하지 않는 경우라고 가정해 보자. 

• enqueue: 삽입의 경우, 마지막에 삽입하면 되기에, O(1)이 소요된다. 
• dequeue: 삭제의 경우, 가장 우선순위가 높은 원소를 탐색해야 하기에 O(N)이 소요된다.

반대로, 배열 혹은 연결리스트를 정렬하는 경우라고 가정해보자.

• enqueue: 삽입할 위치를 찾아야 하기 때문에, O(N)이 소요된다. 
• dequeue: 이미 정렬되어 있기에 마지막 위치에서만 삭제하면 된다. 즉, O(1)이 소요된다. 

즉, 배열 혹은 연결리스트로 구현했을 때, 어떤 방법이든 하나의 Operation에서 O(N)이 소요된다. 

하지만, 힙의 경우, 둘 다 O(logN)으로 수행하기에 힙이 더 효율적이다. 

 

Heap 

"힙"(Heap)은 완전 이진 트리를 기본으로 한 자료구조이며, 부모 노드와 자식 노드 간의 키값 사이에는 대소 관계가 성립한다.

이 대소관계의 방향에 따라 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 구분된다.

• 최대 힙(Max Heap) : 부모 노드의 키값이 항상 자식 노드의 키값보다 크다.
• 최소 힙(Min Heap) : 부모 노드의 키값이 항상 자식 노드의 키값보다 작다.

 

 

힙에서는 모든 노드를 대소관계에 따라 정렬하는 것이 아닌, 부모노드와 자식 노드와의 대소관계에만 성립한다.

 

Insert 

우선, 최대 힙에서 37인 노드가 삽입되는 과정을 살펴보자. 

우선, 완전 이진트리를 기반으로 하기 때문에, 10의 왼쪽 자식에 37 노드를 삽입한다. 

 

이후, 부모와의 대소관계를 비교해, 부모보다 키값이 큰 경우, swap 한다.

이를, 루트노드에 도달했거나, 다음과 같이 더 이상 swap이 일어나지 않을 때까지 반복한다.

 

예시에선 37은 100보다 작기 때문에, 해당 위치에서 Insert를 종료한다. 

 

시간 복잡도 

이때, swap은 O(1)이 소요되며, 이 swap은 최대 트리의 높이만큼 발생한다.

완전 이진트리이기에, 트리의 높이는 $log_2N$이 된다. 

 

즉, 힙에서 삽입은 O($log_2N$)이 된다. 

 

 

pop 

삭제의 경우에는 다음과 같이 수행된다. 

우선적으로, 가장 큰 노드인 루트노드를 pop 한다. 

 

이후, 완전 이진트리에서 가장 마지막 노드를 루트 노드에 위치시킨다. 

 

 

다음으로 자식 노드 중, 자기보다 큰 값을 선택해 swap을 진행한다. 

만약 자식 노드가 2개라면, 자기 보다 큰 값 중 최댓값을 가진 자식 노드를 선택한다. 

첫 번째의 경우에는 19와 36중 36이 더 크기 때문에 36과 5가 swap이 일어난다. 

 

이 과정을  더 이상 변경이 없을 때까지 반복한다. 

 

시간 복잡도 

이때, swap은 O(1)이 소요되며, 이 swap은 최대 트리의 높이만큼 발생한다.

따라서, 힙에서 삭제는 O($log_2N$)이 된다. 

 

 

구현

우선순위 큐는 앞서 살펴보았듯, 힙 자료구조를 통해 가장 효율적으로 구현할 수 있기에, 

힙을 이용한 우선순위 큐만 구현해 보자. 

 

전체적인 코드는 여기에서 확인할 수 있다. 

 

Heap 구현 

우선, 완전 이진트리를 배열로 구현해 보자. 

우선, 배열에 저장하게 되면 부모와 자식 노드 사이의 인덱스에는 다음과 같은 관계가 성립한다.

• 부모 노드 인덱스 : 현재 노드 인덱스 / 2
• 왼쪽 자식 인덱스 : 현재 노드 인덱스 * 2 
• 오른쪽 자식 인덱스 : 현재 노드 인덱스 * 2 + 1  

 

대부분은 다음과 같이 0번 인덱스는 비우고 표현을 하게 되지만, 다음과 같이 0번 인덱스를 채우는 방법도 가능하다. 

 

 

• 부모 노드 인덱스 : (현재 노드 인덱스 - 1) / 2
• 왼쪽 자식 인덱스 : 현재 노드 인덱스 * 2 + 1
• 오른쪽 자식 인덱스 : 현재 노드 인덱스 * 2 + 2

해당 포스팅에선 0번 인덱스를 채우는 방식으로 구현했다. 

우선, Swift에선 동적배열을 지원하며, 제네릭 타입으로 구현했다.  따라서, 내부적으로 0번 인덱스에 dummy data를 채우기 위해선 다음과 같은 추가적인 로직이 필요하다. 

func insert(_ element: T) {
	...
	if isEmpty { nodes.append(element) }
	nodes.append(element)
}

따라서, 0번 인덱스부터 채우는 방법으로 구현했다. 

 

이를 코드로 옮기게 되면 다음과 같다. 

public struct Heap<T: Comparable> {
	private var nodes = [T]()
	
	public var isEmpty: Bool {
		nodes.isEmpty
	}
	
	public var count: Int {
		nodes.count
	}
	
	public var top: T? {
		nodes.first
	}
	...
}

func getParent(of node: Int) -> Int {
	return (node - 1) / 2
}

func getChilds(of node: Int) -> (left: Int, right: Int) {
	return (node * 2 + 1, node * 2 + 2)
}

 

다음으로,  maxHeap과 minHeap인지 생성자 단계에서 파라미터로 전달받는다. 

public enum HeapType {
	case max
	case min
}

public struct Heap<T: Comparable> {
	private var nodes = [T]()
	private let sort: (T, T) -> Bool
	
	...
	
	public init(type: HeapType) {
		switch type {
			case .min:
				self.sort = { $0 < $1 }
			case .max:
				self.sort = { $0 > $1 }
		}
	}
}

 

Insert(_:)

mutating func insert(_ element: T) {
	nodes.append(element)
	shiftUp()
}

앞서 heap의 삽입과정을 살펴보았듯이, 완전 이진 트리에 의해 마지막에 삽입을 한다. 

mutating func shiftUp() {
	var now = nodes.count - 1
	var parent = getParent(of: now)
	
	// now가 0인 경우는 트리의 루트에 도착한 경우, 부모 값과 비교해서 바꿔야 하는 경우
	while now > 0 && sort(nodes[now], nodes[parent]) {
		nodes.swapAt(now, parent)
		now = parent
		parent = getParent(of: now)
	}
}

이후, 부모와 대소관계를 비교해 swap 하는 상황이라면 swap을 진행한다.

 

pop()

mutating func pop() -> T? {
	guard !isEmpty else { return nil }
	
	defer {
		nodes.swapAt(0, nodes.count - 1)
		nodes.removeLast()
		shiftDown()
	}
	
	return nodes[0]
}

 

삭제 과정은 첫 번째 노드와 마지막 노드를 swap 한 후, 마지막 원소를 삭제했다. 

mutating func shiftDown() {
	var now = 0
	while true {
		let (left, right) = getChilds(of: now)
		var candidate = now
		
		if left < nodes.count && sort(nodes[left], nodes[candidate]) {
			candidate = left
		}
		
		if right < nodes.count && sort(nodes[right], nodes[candidate]) && sort(nodes[right], nodes[left]) {
			candidate = right
		}
		
		if candidate == now { return }
		nodes.swapAt(now, candidate)
		now = candidate
	}
}

이후, 자식과 대소관계를 비교해 swap 하는 상황이라면 swap을 진행한다.

 

Priority Queue 구현 

앞서 말했듯 우선순위 큐는 힙이 전부일 정도로 힙만 구현하면 정말 간단해진다. 

public enum PriorityQueueType {
	case max
	case min
}

public struct PriorityQueue<T: Comparable> {
	private var heap: Heap<T>
	
	public var isEmpty: Bool {
		heap.isEmpty
	}
	
	public var top: T? {
		heap.top
	}
	
	public var count: Int {
		heap.count
	}
	
	public init(type: PriorityQueueType) {
		switch type {
			case.max:
				self.heap = Heap<T>(type: .max)
			case .min:
				self.heap = Heap<T>(type: .min)
		}
	}
}

public extension PriorityQueue {
	mutating func enqueue(_ element: T) {
		heap.insert(element)
	}
	
	mutating func dequeue() -> T? {
		return heap.pop()
	}
}