우선순위 큐
- 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.
ex) 응급실에서 접수한 순서대로 치료 하는 것이 아니라 더 위급한 환자를 먼저 치료하는 상황
- 데이터와 우선순위가 함께 저장되는 것이 아니라, 데이터를 근거로 우선순위를 판단한다.
우선순위 큐를 구현하는 방법은 세 가지로 구분할 수 있다.
- 배열을 기반으로 구현하는 방법
- 연결 리스트를 기반으로 구현하는 방법
- 힙 (heap)을 이용하는 방법
배열이나 연결리스트를 이용하면 우선 순위 큐를 매우 간단히 구현할 수 있다. 데이터의 우선순위가 높을수록 배열의 앞쪽에 데이터를 위치시킨다. 이렇게 하면 우선순위가 높은 데이터를 반환하거나 삭제하는 것은 어려운 일이 아니다.
하지만 다음과 같은 단점이 발생한다.
배열으로 구현을 했다고 생각해보면,
1. 삽입 및 삭제 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산이 필요하다.
2. 최악의 경우(우선 순위가 가장 낮은 데이터를 저장하는 경우)에 삽입 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야 할 수도 있다.
연결 리스트로 구현했을 경우에도 위 2번과 같은 단점이 똑같이 발생한다.
그래서 우선순위 큐는 단순 배열도 연결 리스트도 아닌 '힙' 을 이용해서 구현하는 것이 효율적이다.
힙 (Heap)
- 힙은 완전 이진 트리*의 일종이다.
- 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
- 힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다. 모든 요소를 고려하여 우선순위를 정하는 것이 아니라 '부모 노드는 자식노드보다 우선순위가 높다'는 조건만 만족 시키며 채워나가기 때문이다. (형제간 우선순위는 고려하지 않음)
- 위 조건을 생각해보면 루트 노드는 항상 우선순위가 제일 높은 노드라는 것을 알 수 있다. 즉, 최댓값 혹은 최솟값을 찾을 때 루트 노드를 빼주면 되므로 시간복잡도는 O(1) 이다.
- 삽입, 삭제 연산 시에도 부모 노드가 자식 노드보다 우선순위가 높은지만 체크하면 되므로 트리의 깊이만큼만 비교를 하면 되기 때문에 O(logN)의 시간복잡도를 가진다.
- 힙 트리에서는 중복된 값을 허용한다. (이진탐색트리는 중복값 허용 하지 않음)
* 완전 이진 트리란?
새로운 노드를 삽입할 때 위에서 아래로, 왼쪽에서 오른쪽 순서로 삽입하는 트리이다.
힙의 종류
- 최대 힙 (max heap)
부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리
- 최소 힙 (min heap)
부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리
힙의 시간복잡도
완전 이진 탐색 트리의 시간 복잡도는 O(log N)
힙도 최악의 경우 leaf node 혹은 root node까지 탐색을 해야할 수 있으므로 시간 복잡도는 O(log N) 이다.
힙의 구현
힙은 완전 이진 트리이기에 보통 배열로 구현 한다.
노드에 고유 번호를 부여한다. 각 노드의 고유 번호가 데이터가 저장될 배열의 인덱스 값이 된다.
구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용하지 않는다. 따라서 배열의 인덱스 0은 비워둔다.
부모/자식 인덱스 구하기
- 이전 트리 포스팅에서도 한 번 다뤘듯이 n번째 원소의 부모는 n/2, 왼쪽 자식은 2n, 오른쪽 자식은 2n+1 이다.
삽입
- 루트부터 집어넣기 시작해서 왼쪽 자식부터 채운다. 우선 데이터를 맨 끝에 삽입한 후 부모와 비교하면서 자리를 찾는 식이다.
삭제
- 루트를 삭제한 후, 맨 끝 노드를 루트 자리로 올려서 자식들 중 우선 순위가 더 높은 자식과 비교해가며 제자리를 찾아가는 식이다.
java 코드
public class Heap {
int numOfData;
int heapArr[];
public Heap(int length) {
heapArr = new int[length + 1];
}
public boolean dataPriorityCompare(int num1, int num2){
return num1 > num2;
}
public boolean isEmpty() {
return numOfData == 0;
}
public int getParentIdx(int idx) {
return idx/2;
}
public int getLChildIdx(int idx) {
return idx*2;
}
public int getRChildIdx(int idx) {
return getLChildIdx(idx) + 1;
}
public int getHiPriChildIdx(int idx) {
if( getLChildIdx(idx) > numOfData ) {
return 0;
} else if(getLChildIdx(idx) == numOfData) {
return getLChildIdx(idx);
} else {
if(dataPriorityCompare(heapArr[getLChildIdx(idx)], heapArr[getRChildIdx(idx)]))
return getLChildIdx(idx);
else
return getRChildIdx(idx);
}
}
public void insert(int data) {
int idx = numOfData + 1;
while(idx != 1) {
if(dataPriorityCompare(data, heapArr[getParentIdx(idx)])) {
heapArr[idx] = heapArr[getParentIdx(idx)];
idx = getParentIdx(idx);
} else
break;
}
heapArr[idx] = data;
numOfData +=1 ;
}
public int delete() {
int retData = heapArr[1];
int lastElem = heapArr[numOfData];
int parentIdx = 1;
int childIdx;
while((childIdx = getHiPriChildIdx(parentIdx)) > 0) {
if(dataPriorityCompare(lastElem, heapArr[childIdx]))
break;
heapArr[parentIdx] = heapArr[childIdx];
parentIdx = childIdx;
}
heapArr[parentIdx] = lastElem;
numOfData -= 1;
return retData;
}
public void print() {
for(int elem : heapArr)
if(elem != 0)
System.out.println(elem);
}
}
출처 : 윤성우의 열혈 자료구조
C 코드를 JAVA로 바꾼 것입니다.
책 안에 더 자세한 설명이 있습니다.