우선순위 큐
때로는 여러 개의 항목 중에서 최소 값 / 최대 값을 찾아야 할 필요가 있다. 우선순위 큐는 이런 연산을 지원하는 데이터 구조로 Insert, DeleteMin, DeleteMax 등의 연산을 사용할 수 있도록 한다.
작은 키 값을 갖는 항목일수록 높은 우선순위를 갖는 우선순위 큐를 오름차순 우선순위 큐라고 한다.
큰 키 값을 갖는 항목일수록 높은 우선순위를 갖는 우선순위 큐를 내림차순 우선순위 큐라고 한다.
적용사례
- 데이터 압축 : 허프만 코딩
- 최단 거리 알고리즘 : 다익스트라
- 최소 신장 트리 알고리즘: 프림
- 이벤트 지향 시뮬레이션: 줄 서 있는 고객들
- 선택 문제: k번째 작은 항목 찾기
구현
- 정렬되지 않은 배열 구현 : 삽입 O(1), DeleteMin O(n)
- 정렬되지 않은 리스트 구현 : 삽입 O(1), DeleteMin O(n)
- 정렬된 배열 구현 : 삽입 O(n), DeleteMin O(1)
- 정렬된 리스트 구현 : 삽입 O(n), DeleteMin O(1)
- 이진 탐색 트리 구현 : 평균 O(logn)
- 균형 이진 탐색 트리 구현 : 최악 O(logn)
- 이진 힙 구현 : 검색, 삽입, 삭제 O(logn), 최소 값, 최대 값 찾기 O(1)
Heap
몇 가지 특수한 속성을 가진 트리로, 노드의 값이 그 자식 노드의 값보다 ≥ 혹은 ≤ 한다는 것이다. 이를 힙 속성이라고 한다. 또한 트리의 높이가 h > 0 일 때 모든 리프 노드들이 h 혹은 h - 1 레벨에 있어야 한다는 것이다. 즉 힙은 완전 이진 트리여야 한다.
최소 힙 : 노드의 값이 자식 노드의 값보다 작거나 같아야만 한다.
최대 힙 : 노드의 값이 자식 노드의 값보다 크거나 같아야만 한다.
힙을 표현하기 : 배열을 사용하는 것. 힙이 완전 이진 트리를 구성하므로 공간 낭비가 거의 없다.
public class Heap {
public int[] arr;
public int count;
public int capacity;
public int heapType;
public Heap(int capacity, int heapType){
this.heapType = heapType;
this.count = 0;
this.capacity = capacity;
this.arr = new int[capacity];
}
public int getParent(int i){
if(i <= 0 || i >= this.count){
return -1;
}
return (i - 1) / 2;
}
public int leftChild(int i){
int left = 2 * i + 1;
if(left >= this.count){
return -1;
}
return left;
}
public int rightChild(int i){
int left = 2 * i + 2;
if(right >= this.count){
return -1;
}
return right;
}
public int getMaximum(){
if(this.count == 0){
return -1;
}
return this.arr[0];
}
// 마지막 항목을 루트 노드로 바꾸고 힙 재조정
// 시간복잡도 O(logn), 최악의 경우 루트에서 리프까지
public int deleteMax(){
if(this.count == 0){
return -1;
}
int data = this.arr[0];
this.arr[0] = this.arr[this.count - 1];
this.count--;
percolateDown(0);
return data;
}
public void percolateDown(int i){
int l, r, max, temp;
l = leftChild(i);
r = rightChild(i);
if(l != -1 && this.arr[l] > this.arr[i])
max = l;
else
max = i;
if(r != -1 && this.arr[r] > this.arr[max])
max = r;
if(max != i){
temp = this.arr[i];
this.arr[i] = this.arr[max];
this.arr[max] = temp;
percolateDown(max);
}
}
// 새 항목을 힙의 끝에 위치, 위로 힙 만들기
// 시간복잡도 O(logn)
public void insert(int data){
int i;
int temp;
if(this.count == this.capacity){
resizeHeap();
}
this.count++;
i = this.count - 1;
this.arr[i] = data;
while(i >= 0 && data > this.arr[(i - 1) / 2]){
temp = this.arr[i];
this.arr[i] = this.arr[(i - 1) / 2];
this.arr[(i - 1) / 2] = temp;
i = (i - 1) / 2
}
}
}
배열을 힙으로 만들기
간단한 방법은 n개의 항목을 입력받아 이들을 빈 힙에 위치 시키는 것. O(nlogn)
다른 방법은 리프 노드는 고려하지 않고 리프가 아닌 가장 처음 노드를 찾아 감소시키면서 힙을 만들어준다. 보다 효율적.
void buildHeap(Heap h, int A[]. int n){
if(h == null) return;
while(n > this.capacity){
h.resizeHeap();
}
for(int i = 0; i < n; i++){
h.arr[i] = A[i];
}
for(int i = (n - 1) / 2; i >= 0; i--){
h.percolateDown(i);
}
}
힙 정렬
힙 정렬 알고리즘은 모든 항목을 정렬되지 않은 배열로부터 힙에 삽입해서 힙의 루트로부터 힙이 빌 때 까지 항목들을 제거한다. 힙 정렬은 정렬될 배열과 같은 장소에서 이루어질 수 있다. 항목을 삭제하는 대신 첫 번째 항목과 마지막 항목을 교체하고 힙 크기(배열 크기)를 감소시킨다. 그 다음 첫 번째 항목을 힙으로 만든다. 이 과정을 남은 항목이 한 개일 때까지 반복한다.
void heapSort(int A[], int n){
heap h = new Heap(n, 0);
int oldSize, temp;
buildHeap(h, A, n);
oldSize = h.count;
for(int i = h.count - 1; i > 0; i--){
temp = h.arr[0];
h.arr[0] = h.arr[i];
h.arr[i] = temp;
h.count--;
h.percolateDown(0);
}
h.count = oldSize;
}
void heapSort(int A[], int n){
buildHeap(h, A, n);
for(int i = h.count - 1; i > 0; i--){
A[i] = h.deleteMax();
}
}
항목을 힙으로부터 삭제할 때 값이 정렬된다. 삽입 알고리즘과 삭제 알고리즘의 시간 복잡도가 모두 O(logn)이므로 힙 안의 항목 수가 n일 때, 힙 정렬 알고리즘의 시간 복잡도는 O(nlogn)이다.