자료 구조 - 우선순위 큐
우선순위 큐란?
- 우선순위 큐(priority queue)
- 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 출력되는 자료구조
- 배열, 연결 리스트, 힙 등으로 구현 가능하나 힙(heap)이 가장 효율적인 구조임
- 우선순위 큐는 보통 최소 우선순위 큐와 최대 우선순위 큐로 나뉜다.
- 최소 우선순위 큐
- 가장 우선순위가 낮은 요소를 먼저 삭제
- 최대 우선순위 큐
- 가장 우선순위가 높은 요소를 먼저 삭제
- 최소 우선순위 큐
추상자료형
- 최대 우선순위 큐 예시
데이터 : 우선순위를 가진 요소들의 모음
연산
- insert(item)
- remove() : 우선순위가 가장 높은 요소 삭제하고 반환
- find() : 우선순위가 가장 높은 요소를 삭제하지 않고 반환
- isEmpty()
- isFull()
- display()
구현 방법
배열 이용
정렬되지 않은 배열
- 삽입은 O(1)
- 삭제는 O(n)
- 순회해서 가장 우선순위 높은 요소를 찾아야 함
정렬된 배열
- 삽입은 O(n)
- 삽입 위치 찾는 건 O(logn)
- 삭제는 O(1)
- 맨 뒤가 가장 우선순위 높은 요소
연결리스트 이용
- 배열과 비슷
- 우선순위가 높은 요소를 헤드 포인터 다음에 오게 맨 앞에 둠
힙 이용
- 힙은 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다.
- 요소들이 반 정렬된 상태의 자료구조이다.
힙(Heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 큰 완전 이진 트리이다. (최대 힙)
- 최소 힙의 경우는 반대
- 중복된 값을 허용한다.
- 여기선 최대 힙을 예시로 본다.
힙의 구현
- 완전 이진 트리이므로 중간에 비어 있는 요소가 없어 배열을 자료구조로 이용 가능하다.
- 구현을 쉽게 하기 위해 0번 인덱스는 비워둔다.
인덱스 구하기
- 이진 트리 특성을 생각해보자.
- 특정 노드의 왼쪽 자식의 인덱스는 부모의 인덱스*2 이고,
- 오른쪽 자식 인덱스는 부모 인덱스*2 + 1 이다.
- 부모의 인덱스는 자식 인덱스 / 2 이다.
힙 기본 틀 구현
- 힙에 저장할 노드 클래스 HeapNode라 하고, int 타입의 키를 가지게 한다.
- 최대힙으로 구현한다.
class HeapNode {
private:
int key;
public:
HeapNode(int k=0) : key(k) { }
void setKey(int k) { key = k; }
int getKey() { return key; }
void display() { printf("%4d ", key); }
};
- 위 노드를 바탕으로 Heap을 구현한다.
- getParent, getLeft, getRight 을 먼저 구현하고 이를 통해 insert, remove를 구현한다.
힙 노드 추가 연산
- 추가는 힙 사이즈 끝에 노드를 먼저 추가하고,
- 노드를 부모 노드와 비교해 키 값이 크면 부모와 바꾸고 아니면 멈추는 방식이다.
void MaxHeap::insert(HeapNode node)
{
array[++size] = node;
int idx = size;
while(idx != 1) {
if(getParent(idx) < array[idx] ) {
HeapNode temp = array[idx];
array[idx] = getParent(idx);
getParent(idx) = temp;
}
idx /= 2;
}
}
힙 노드 삭제 연산
- 삭제는 먼저 사이즈 끝의 노드와 첫 노드를 서로 바꾼다.
- 바꾼 첫 노드를 자식 노드들과 비교하며 적당한 위치로 바꿔가면 된다.
- 두 자식 노드보다 키 값이 크다면 멈추고, 둘 중 하나 보다 작다면 큰 자식과 바꾼다.
void MaxHeap::remove()
{
int idx = 1;
array[idx] = array[size--];
while (true)
{
if(getLeftChild(idx) < array[idx] && getRightChild(idx) < array[idx]) break;
HeapNode temp = array[idx];
if (getLeftChild(idx) < getRightChild(idx)) {
array[idx] = getRightChild(idx);
getRightChild(idx) = temp;
idx = idx*2 + 1;
} else {
array[idx] = getLeftChild(idx);
getLeftChild(idx) = temp;
idx = idx*2;
}
}
}
힙의 복잡도
- 완전 이진 트리의 높이는 원소 개수의 $log_2n$ 이다.
- 추가 연산 시 부모와 비교하며 교환하는 방식이 반복된다.
- 따라서 최대 연산 횟수는 완전 이진 트리의 높이와 같아지므로, 시간 복잡도는 $log_2n$이다.
- 삭제의 경우도 마찬가지다.
힙 정렬
- 정렬의 한 방식이다.
- 모든 요소를 힙에 넣은 뒤 다시 순서대로 빼주면 정렬된 상태로 나올 것이다.
- 시간 복잡도는 $nlog_2n + nlog_2n$ -> $nlog_2n$ 이다.
STL의 우선순위 큐
-
헤더 파일에 priority_queue 클래스가 있다. - 정렬 기준을 STL에서 제공하는 객체? 바꾸고 싶다면
헤더를 추가한다.
#include <queue>
#include <functional>
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
int n = 1;
maxHeap.push(n);
int a = maxHeap.top();
maxHeap.pop();
허프만 코드
- 문서에 있는 각 알파벳의 빈도가 알려져 있는 경우 이진트리를 이용해 문서를 압축하고 용량을 줄일 수 있다.
- 이런 종류의 이진트리를 허프만 코딩 트리 라고 부른다.
- 데이터를 압축할 때는 ASCII 코드와 같은 고정 길이 코드를 사용하지 않고 가변 길이 코드를 흔히 사용한다.
- 빈도수가 높은 글자에 짧은 비트열을 사용하고, 낮은 글자에 긴 비트열을 사용하는 방식이다.
- 허프만 트리는 가장 낮은 빈도수의 루트 2개를 묶어 이진트리를 만드는 방법을 반복한다.
- 낮은 빈도수를 계속 봅아내는 곳에서 최소 힙이 사용된다.
문제
- 힙을 이요하지 않고 정렬되지 않은 1차원 배열을 이용해 우선순위 큐 만들기
- 정렬 연결 리스트를 이용하여 우선순위 큐 만들기
- 배열로 표현된 완전 이진트리가 힙 조건을 만족하는지 검사하는 함수를 순환적으로 만들기
- 3을 반복적인 방법으로 만들어 보기
Leave a comment