1. 우선순위 큐(Priority Queue)란?
이 자료구조는 우선순위 큐라는 말에서 볼 수 있다시피 우선순위가 높은 것을 먼저 꺼내기 위하여 만들어진 자료구조이며, 힙(Heap)이라고도 부른다.
예를 들어서, 숫자 1~10을 저장하는 자료구조를 구현하고 싶은데, 이 숫자들이 랜덤으로 삽입된다고 하자.
숫자가 클 수록 우선순위가 높다고 가정하자. 그렇다면 10이 가장 먼저 꺼내지고, 그 뒤로 9, 8, 7, ... , 1 순으로 추출될 수 있을 것이다.(이것을 최대힙, Max Heap 이라 부른다.)
숫자가 작을 수록 우선순위가 높다고 가정하자. 이 경우 1이 가장 먼저 꺼내지고, 그 뒤로 2, 3, 4, ... , 10순으로 추출될 수 있을 것이다.(이것을 최소힙, Min Heap 이라 부른다.)
여기서 의문이 몇 가지 있을 수 있다.
① 배열에 데이터 저장을 하고 새로 삽입할 때마다 서로 비교하면서 정렬해주면 되는 것 아닌가?
▶ 그런데 이 방식은 그다지 효율적이지 못하다. 왜냐하면 선형으로 처음부터 비교를 하면서 해당 자료를 삽입할 위치를 찾아야 하기 때문에 O(n)의 시간이 소요되고 n이 충분히 크다면 원하는 시간 안에 해결하기 어려울 수 있다.
② 그럼 배열에 저장하되, 퀵 정렬, 이진 탐색 같은 방식을 이용하면 훨씬 빠르게 삽입 / 추출 / 탐색도 가능하지 않은가?
▶ 맞다. 우선순위 큐는 그러한 방식을 하나의 자료구조로써 구현한 것이라고 보면 된다. 그것을 힙(Heap) 이라고도 부른다. 실제로 O(logn) 수준의 시간 복잡도를 유지한다.
위의 의문점 처럼, 사실 우선순위 큐를 구현하는 방법은 다양한데 아래의 표를 보자.
| 구현 방식 | 삽입 시 시간복잡도 | 추출 시 시간복잡도 | 설명 |
| 정렬 안된 배열 | O(1) | O(n) | 삽입은 단순 삽입, 추출 시 비교하며 추출 |
| 정렬 안된 리스트 | O(1) | O(n) | 삽입은 단순 삽입, 추출 시 비교하며 추출 |
| 정렬된 배열 | O(n) | O(1) | 삽입 시 비교하며 사십, 추출은 단순 추출 |
| 정렬된 리스트 | O(n) | O(1) | 삽입 시 비교하며 사십, 추출은 단순 추출 |
| 힙(Heap) | O(logn) | O(logn) | 삽입 / 추출 시 기존 정렬 상태 유지 |
일단 우선순위 큐를 힙(Heap) 구현 시 특징 부터 알아보자.
ⓐ 완전 이진 트리 구조의 형태를 갖는다.
ⓑ 일반적으로 배열로 구현한다.
ⓒ 일종의 반 정렬 상태를 유지한다.(느슨한 정렬 상태)
위의 3가지 특징에서 알 수 있는 것은, 트리 구조이므로 전체적인 시간 복잡도를 O(logn)으로 유지할 수 있으며, 트리 구조를 배열로 구현했으니 0번 Index는 사용하지 않겠구나(편의상) 라는 것을 알 수 있다.
반 정렬 상태라는 것은, 트리 구조를 배열에 저장한 것이므로 배열로만 보았을 때는 완전히 정렬된 상태로 보이지는 않는 다는 것이다. 이해를 돕기 위해 아래의 그림을 보자.
위의 그림에서 보이듯이 숫자가 클 수록 우선 순위가 높게 저장되어 있는데 이런 형태를 최대 힙(Max Heap) 이라고 부른다. 정렬 상태를 보면 알겠지만 높은 층위에 있는 숫자가 더 크다. 즉, 자식 노드보다 부모 노드가 더 큰 숫자를 갖고 있다.
이를 배열 형태로 늘어서 보면 1번 노드부터 10번 노드까지 Index에 순서대로 넣는 형태가 된다.
일반적으로 우선순위 큐는 0번 Index는 사용하지 않는다. 트리 구조의 특성에 따른 것으로, Index 값을 좌측 자식은 부모 노드의 x2, 우측 자식은 부모 노드의 x2 + 1로 설정하고 부모 노드는 자식 노드 아무 쪽에서든, 1/2을 곱해주면 바로 구할 수 있기 때문이다.
(만약 Binary Tree가 아닌 3진/4진 트리로 Heap을 구현한다면 더더욱 불편하다.)
위의 배열에서 Index 1 ~ Index 10 까지 완전히 정렬된 상태는 아님을 알 수 있다. 즉, 느슨한 정렬 상태를 유지하는 것이다.
2. 직접 구현하기
그럼 우선순위 큐가 어떤 자료구조인지는 이해를 할 수 있었으니 직접 구현하면서 내부 로직을 어떻게 구성해야 올바르게 구현할 수 있는지 학습해보자.
여기서는 최대 힙(Max Heap)을 기준으로 진행한다.
최소 힙(Min Heap)은 아래의 코드들에서 적절히 부호만 바꾸어 주면 된다.
① 생성자 구성
생성자에는 크게 필요한 것은 없다. 일단 전체 데이터를 배열로 구현할 것이므로 배열을 만들어주는 것이 좋을 듯 하다. 크기를 직접 지정했다면 전달하고 아니라면 기본값으로 지정한다.
package com.test;
public class PriorityQueueImpl<T extends Comparable> { // 비교 가능하도록 Comparable 구현
private Object array[]; // 데이터 저장 배열
private static final int default_capacity = 1000001; // 기본 100만개 데이터 넣을 수 있게 설정
private int capacity; // 사용자가 지정한 최대 데이터 입력 수
private int size = 0; // 현재 입력된 데이터 수
private int lastIndex = 0; // 마지막으로 입력된 데이터의 Index
public PriorityQueueImpl(){
new PriorityQueueImpl(this.default_capacity);
}
public PriorityQueueImpl(int capacity){
this.capacity = capacity+1; // 0번 Index를 사용하지 않으므로 +1 해줌
this.array = new Object[this.capacity];
}
}
② 데이터 삽입(insert)
데이터를 삽입 시에는 새로 삽입되는 데이터가 있을 때, 기존의 배열이 비어있었다면 단순히 루트 노드에 삽입하면 된다. 그런데 만약 데이터가 있었고 해당 데이터보다 큰 경우에는 위치를 바꾸어주는 작업이 필요하다.
아래의 그림을 통해 새로운 값 11을 삽입하고자 한다고 하자.
만약 새로이 넣고자 하는 값이 5이하의 숫자였다면 단순히 해당 위치에 삽입을 해도 상관이 없을 것이다. 만약 그랬다면 부모 노드의 Index가 5인데 좌측 자식 노드는 이미 데이터가 있으니, 우측 자식으로 단순히 삽입하면 된다.
여기서 잠시 복습 하자면, 0번 Index를 사용하지 않는 경우 부모와 자식 노드의 관계는 다음과 같다.
부모 노드 Index : n
좌측 자식 노드 Index : nx2
우측 자식 노드 Index : nx2+1
하지만 최대 힙은 숫자가 클 수록 우선순위가 높은데 11이라는 숫자는 현재 저장된 어떠한 숫자보다도 우선순위가 높다. 따라서 재정렬을 하는 Heapify 과정이 필요하다.
Heapify는 힙을 고친다라는 의미로, 현재 삽입 혹은 삭제될 노드에 의해 전체 정렬 상태에 영향이 생길 경우 그 정렬을 다시 올바르게 진행하기 위한 절차를 의미한다.
현재 노드보다 상단으로 힙을 고쳐야 한다면 Above Heapify, 하단으로 힙을 고쳐야 한다면 Below Heapify라고 부르자.
삽입 시에는 가장 마지막 배열 위치에 값을 우선 넣고 진행하므로 상단으로 힙을 재정렬해야 한다. 그림으로 간단히 삽입 후 Above Heapify를 하는 과정을 이해해보자.
데이터 삽입 부분을 코드로 진행하면 이와 같다.
public boolean insert(T data){
// 현재 Heap이 꽉 찼다면 배열의 크기를 2배로 만든다.
if(capacity-1 == size){
makeDouble();
}
array[++lastIndex] = data;
aboveHeapify(lastIndex); // 상단 방향으로 재정렬 수행
size++;
return true;
}
// 배열을 2배로 만들고 새로 구성하는 함수
private void makeDouble(){
this.capacity = this.capacity*2-1;
Object newArray[] = new Object[this.capacity];
System.arraycopy(this.array, 0, newArray, 0, this.lastIndex);
this.array = newArray;
}
③ 데이터 상향 재정렬(Heapify)
삽입을 통해 데이터 재정렬이 필요한 경우가 있다는 것을 확인할 수 있었다. 이번엔 그 재정렬을 어떻게 코드로 구현할 수 있는지 살펴보자.
아래의 코드와 같이 간단하게 상단 Heapify는 부모 노드와 비교하여 현재 데이터가 더 우선순위 상으로 높다면 위치를 바꾸어주는 방식이다.
private void aboveHeapify(int startIndex){
T relocateData = (T)this.array[startIndex];
int current = startIndex;
// Index가 Root에 다다르지 않았고 부모 데이터보다 현재 데이터가 더 크다면
while(current > 1 && relocateData.compareTo((T)this.array[current/2]) > 0){
// 부모 데이터를 현재 위치에 저장
this.array[current] = this.array[current/2];
current /= 2;
}
this.array[current] = relocateData;
}
④ 데이터 추출(pop)
데이터를 저장했으니 이제 우선순위에 맞게 추출하거나 내부의 특정 데이터를 추출할 수 있어야 한다.
애초에 우선순위 큐를 사용하는 이유가 우선순위 대로 추출하기 위해서이기 때문에 현재 최우선 순위 상태가 아닌 데이터를 먼저 추출하고자 하는 경우는 거의 없다. 그러나 예외의 경우가 있을 수 있으니 그에 대한 코드도 같이 구현하도록 하겠다.
일단, 추출 시의 로직을 생각해보자.
현재 최우선 순위의 데이터를 추출해냈다면 배열의 가장 마지막에 있는 데이터를 최우선 순위 위치로 가져다 놓는다. 그 다음 아래 방향으로 재정렬(Heapify)를 진행하면 된다. 그림으로 이해해보자.
위의 내용을 코드로써 구현하면 아래와 같다.
// 비어있는 상태인지 확인
public boolean isEmpty(){
return this.size==0;
}
// 가장 우선순위인 데이터 추출
public T pop(){
if(isEmpty()){
throw new NullPointerException();
}
return pop((T)this.array[1]); // 가장 우선 순위인 데이터를 전달한다.
}
// 특정 데이터를 추출
public T pop(T data){
if(isEmpty()){
throw new NullPointerException();
}
int targetIndex = find(data);
// 만약 그런 데이터가 없다면
if(targetIndex == -1){
throw new NullPointerException();
}
// 반환할 데이터를 미리 저장
T retData = (T)this.array[targetIndex];
// 만약 가장 마지막에 저장된 데이터를 추출하려는 경우라면 그냥 추출하고 끝낸다.
if(targetIndex == lastIndex){
this.array[this.lastIndex--] = null;
this.size--;
return retData;
}
// 가장 마지막에 저장된 데이터를 가져온다. 마지막 Index 값은 바꿔주어야 한다.
T rightMostData = (T)this.array[this.lastIndex];
this.array[this.lastIndex--] = null;
// 최 우측 데이터를 현재 제거될 위치의 데이터가 있는 자리에 넣는다.
this.array[targetIndex] = rightMostData;
// 루트 데이터가 추출되는 경우이거나 부모 데이터보다 대체된 데이터가 더 작다면 아래로 Heapify
if(targetIndex == 1 || rightMostData.compareTo((T)this.array[targetIndex / 2]) < 0){
belowHeapify(targetIndex);
// 아니라면 위로 Heapify
} else {
aboveHeapify(targetIndex);
}
this.size--;
return retData;
}
// 특정 데이터의 위치를 파악한다.
public int find(T data){
for(int i=1; i <= this.size; i++){
if(this.array[i].equals(data)){
return i;
}
}
return -1;
}
⑤ 데이터 하향 재정렬(Heapify)
하향 재정렬도 기본적으로 원리는 같은데, 상향 재정렬과 다른 점은 하향 재정렬은 비교 대상이 2개라는 것이다.
즉, 좌측 / 우측 자식 데이터와 비교를 해야하는데 이 때 3가지 가능성이 있다.
⑴ 좌측 / 우측 자식 데이터가 모두 없는 경우
⑵ 좌측 자식 데이터만 있는 경우
⑶ 좌측 / 우측 자식 데이터가 모두 있는 경우
잘 생각해보면 우측 자식 데이터만 있는 경우는 없다는 것을 알 수 있다. 완전 이진 트리이기 때문이다.
자식 데이터가 없으면 리프(Leaf) 데이터이므로 재정렬이 불필요하다.
좌측 자식 데이터만 있으면 그 데이터가 더 크다면 상호 교환한다.
모든 자식 데이터가 있으면 더 큰 자식 데이터와 비교하여 해당 데이터가 자신보다 크다면 교환한다.
이를 코드로 작성하면 아래와 같다.
private void belowHeapify(int startIndex){
T relocateData = (T)this.array[startIndex];
int current = startIndex;
// 마지막 Index보다 작거나 같을 때까지 지속 진행
while(current <= lastIndex){
int leftIndex = current*2;
int rightIndex = current*2+1;
// 현재 Leaf 위치라면 더 이상 비교할 필요 없다.
if(leftIndex > lastIndex){
break;
} else {
T leftChild = (T)this.array[leftIndex];
T rightChild = rightIndex > this.lastIndex ? null : (T)this.array[rightIndex];
// 우측 자식이 없고 좌측 자식이 더 값이 크다면 상호 위치를 바꾼다.
if(rightChild == null){
if(leftChild.compareTo(relocateData) > 0) {
this.array[current] = leftChild;
this.array[leftIndex] = relocateData;
current = leftIndex;
} else {
break;
}
} else {
T targetToSwap = leftChild.compareTo(rightChild) > 0 ? leftChild : rightChild;
int swapIndex = leftChild.compareTo(rightChild) > 0 ? leftIndex : rightIndex;
if(targetToSwap.compareTo(relocateData) > 0){
this.array[current] = targetToSwap;
this.array[swapIndex] = relocateData;
}
current = swapIndex;
}
}
}
}
이를 전체 코드로 보면 아래와 같다.
package com.test;
public class PriorityQueueImpl<T extends Comparable> {
private Object array[]; // 데이터 저장 배열
private static final int default_capacity = 1000001; // 기본 100만개 데이터 넣을 수 있게 설정
private int capacity; // 사용자가 지정한 최대 데이터 입력 수
private int size = 0; // 현재 입력된 데이터 수
private int lastIndex = 0; // 마지막으로 입력된 데이터의 Index
public PriorityQueueImpl(){
this.array = new Object[this.default_capacity];
this.capacity = this.default_capacity;
}
public PriorityQueueImpl(int capacity){
this.capacity = capacity+1;
this.array = new Object[this.capacity];
}
public boolean insert(T data){
if(capacity-1 == size){
makeDouble();
}
array[++lastIndex] = data;
aboveHeapify(lastIndex);
size++;
return true;
}
private void makeDouble(){
this.capacity = this.capacity*2-1;
Object newArray[] = new Object[this.capacity];
System.arraycopy(this.array, 0, newArray, 0, this.lastIndex);
this.array = newArray;
}
private void aboveHeapify(int startIndex){
T relocateData = (T)this.array[startIndex];
int current = startIndex;
// Index가 Root에 다다르지 않았고 부모 데이터보다 현재 데이터가 더 크다면
while(current > 1 && relocateData.compareTo((T)this.array[current/2]) > 0){
// 부모 데이터를 현재 위치에 저장
this.array[current] = this.array[current/2];
current /= 2;
}
this.array[current] = relocateData;
}
public boolean isEmpty(){
return this.size==0;
}
public T pop(){
if(isEmpty()){
throw new NullPointerException();
}
return pop((T)this.array[1]);
}
public T pop(T data){
if(isEmpty()){
throw new NullPointerException();
}
int targetIndex = find(data);
// 만약 그런 데이터가 없다면
if(targetIndex == -1){
throw new NullPointerException();
}
// 반환할 데이터를 미리 저장
T retData = (T)this.array[targetIndex];
// 만약 가장 마지막에 저장된 데이터를 추출하려는 경우라면 그냥 추출하고 끝낸다.
if(targetIndex == lastIndex){
this.array[this.lastIndex--] = null;
return retData;
}
// 가장 마지막에 저장된 데이터를 가져온다. 마지막 Index 값은 바꿔주어야 한다.
T rightMostData = (T)this.array[this.lastIndex];
this.array[this.lastIndex--] = null;
// 최 우측 데이터를 현재 제거될 위치의 데이터가 있는 자리에 넣는다.
this.array[targetIndex] = rightMostData;
// 루트 데이터가 추출되는 경우이거나 부모 데이터보다 대체된 데이터가 더 작다면 아래로 Heapify
if(targetIndex == 1 || rightMostData.compareTo((T)this.array[targetIndex / 2]) < 0){
belowHeapify(targetIndex);
// 아니라면 위로 Heapify
} else {
aboveHeapify(targetIndex);
}
return retData;
}
public int find(T data){
for(int i=1; i < this.array.length; i++){
if(this.array[i].equals(data)){
return i;
}
}
return -1;
}
private void belowHeapify(int startIndex){
T relocateData = (T)this.array[startIndex];
int current = startIndex;
// 마지막 Index보다 작거나 같을 때까지 지속 진행
while(current <= lastIndex){
int leftIndex = current*2;
int rightIndex = current*2+1;
// 현재 Leaf 위치라면 더 이상 비교할 필요 없다.
if(leftIndex > lastIndex){
break;
} else {
T leftChild = (T)this.array[leftIndex];
T rightChild = rightIndex > this.lastIndex ? null : (T)this.array[rightIndex];
// 우측 자식이 없고 좌측 자식이 더 값이 크다면 상호 위치를 바꾼다.
if(rightChild == null){
if(leftChild.compareTo(relocateData) > 0) {
this.array[current] = leftChild;
this.array[leftIndex] = relocateData;
current = leftIndex;
} else {
break;
}
} else {
T targetToSwap = leftChild.compareTo(rightChild) > 0 ? leftChild : rightChild;
int swapIndex = leftChild.compareTo(rightChild) > 0 ? leftIndex : rightIndex;
if(targetToSwap.compareTo(relocateData) > 0){
this.array[current] = targetToSwap;
this.array[swapIndex] = relocateData;
}
current = swapIndex;
}
}
}
}
}
3. 최소 / 최대힙 동시 구현하기(2020.10.17 추가됨)
최소 / 최대힙을 각각 구현을 직접 하는 것은 낭비이므로 한 번에 구현하기 위해 이 내용을 추가한다. 위의 최대힙을 구한 경우를 보면 비교 시 Comparable 인터페이스를 이용하였다.
이 Comparable의 compareTo 메소드의 결과 값에 1 또는 -1을 곱하여 최소 / 최대 힙 중 어느 것으로 사용할 것인지 지정할 수 있다.
오름차순이면 최소힙, 내림차순이면 최대힙이라고 가정하자. 실제로는 느슨한 정렬이지만 이해는 가능할 것이다. 사용자가 생성자를 통해 어느 쪽으로 할지 지정할 수 있으며, 만약 미 지정 시 오름차순(최대힙)이라고 가정하여 생성하도록 한다.
아래에 전체 코드를 올리며 주석의 내용을 확인하면 기존의 코드에서 생성자와 compareTo 메소드의 결과에 1 또는 -1을 곱하여 규칙을 지정한 것을 알 수 있다. 내용은 어렵지 않다.
package com.test;
public class PriorityQueueImpl<T extends Comparable> {
private Object array[];
private static final int default_capacity = 1000000;
private int capacity;
private int size = 0;
private int lastIndex = 0;
private int multiple = 1; // Ascending as Default
public PriorityQueueImpl(boolean ascending){
new PriorityQueueImpl(this.default_capacity, ascending);
}
public PriorityQueueImpl(int capacity, boolean ascending){
this.capacity = capacity+1;
this.array = new Object[this.capacity];
if(ascending){
this.multiple = -1; // 오름차순
} else {
this.multiple = 1; // 내림차순
}
}
public boolean insert(T data){
if(capacity-1 == size){
makeDouble();
}
array[++lastIndex] = data;
aboveHeapify(lastIndex);
size++;
return true;
}
private void makeDouble(){
this.capacity = this.capacity*2-1;
Object newArray[] = new Object[this.capacity];
System.arraycopy(this.array, 0, newArray, 0, this.lastIndex);
this.array = newArray;
}
private void aboveHeapify(int startIndex){
T relocateData = (T)this.array[startIndex];
int current = startIndex;
// Index가 Root에 다다르지 않았고 부모 데이터보다 현재 데이터의 비교 결과에 정렬 방식에 따른 결과를 곱한다.
// 오름차순이면(최소힙) 재배치할 값이 더 작다면 상호교환 해야 하므로, -1을 곱한 값이 0보다 크다면 교환
// 내림차순이면(최대힙) 재배치할 값이 더 크다면 상호교환 해야 하므로, 1을 곱한 값이 0보다 크다면 교환
while(current > 1 && relocateData.compareTo((T)this.array[current/2]) * this.multiple > 0){
// 부모 데이터를 현재 위치에 저장
this.array[current] = this.array[current/2];
current /= 2;
}
this.array[current] = relocateData;
}
public boolean isEmpty(){
return this.size==0;
}
public T pop(){
if(isEmpty()){
throw new NullPointerException();
}
return pop((T)this.array[1]);
}
public T pop(T data){
if(isEmpty()){
throw new NullPointerException();
}
int targetIndex = find(data);
// 만약 그런 데이터가 없다면
if(targetIndex == -1){
throw new NullPointerException();
}
// 반환할 데이터를 미리 저장
T retData = (T)this.array[targetIndex];
// 만약 가장 마지막에 저장된 데이터를 추출하려는 경우라면 그냥 추출하고 끝낸다.
if(targetIndex == lastIndex){
this.array[this.lastIndex--] = null;
this.size--;
return retData;
}
// 가장 마지막에 저장된 데이터를 가져온다. 마지막 Index 값은 바꿔주어야 한다.
T rightMostData = (T)this.array[this.lastIndex];
this.array[this.lastIndex--] = null;
// 최 우측 데이터를 현재 제거될 위치의 데이터가 있는 자리에 넣는다.
this.array[targetIndex] = rightMostData;
// 루트 데이터가 추출되는 경우이거나 부모 데이터보다 대체된 데이터가 더 작다면 아래로 Heapify
// 오름차순(최소힙)일 때, 대체된 데이터(최우측 값)이 부모 데이터와 비교해 더 크다면 부모와의 관계는 정상이므로 아래로 재정렬
// 즉, 비교값이 0보다 크다면 대체 데이터가 더 크다는 의미이며 -1을 곱해 전체 값이 0보다 작다면 아래로 재정렬
// 내림차순(최대힙)일 때, 대체된 데이터(최우측 값)이 부모 데이터와 비교해 더 작다면 부모와의 관계는 정상이므로 아래로 재정렬
// 즉, 비교값이 0보다 작다면 대체 데이터가 더 작다는 의미이며 1을 곱해 전체 값이 0보다 작다면 아래로 재정렬
if(targetIndex == 1 || rightMostData.compareTo((T)this.array[targetIndex / 2]) * this.multiple < 0){
belowHeapify(targetIndex);
// 아니라면 위로 Heapify
} else {
aboveHeapify(targetIndex);
}
this.size--;
return retData;
}
public int find(T data){
for(int i=1; i <= this.size; i++){
if(this.array[i].equals(data)){
return i;
}
}
return -1;
}
private void belowHeapify(int startIndex){
T relocateData = (T)this.array[startIndex];
int current = startIndex;
// 마지막 Index보다 작거나 같을 때까지 지속 진행
while(current <= lastIndex){
int leftIndex = current*2;
int rightIndex = current*2+1;
// 현재 Leaf 위치라면 더 이상 비교할 필요 없다.
if(leftIndex > lastIndex){
break;
} else {
T leftChild = (T)this.array[leftIndex];
T rightChild = rightIndex > this.lastIndex ? null : (T)this.array[rightIndex];
// 우측 자식이 없다면 좌측 자식만 비교
if(rightChild == null){
// 오름차순(최소힙)이라면 자식이 더 작다면 상호 교환해야 한다.
// 왼쪽 자식과 비교했을 때 자식이 더 작으면 0보다 작은 값을 반환할 것이고 -1을 곱하면 0보다 큰 조건을 만족하므로 교환
// 내림차순(최대힙)이라면 자식이 더 크다면 상호 교환
// 왼쪽 자식과 비교 시 자식이 더 크다면 0보다 큰 값을 반환하고 1을 곱하면 0보다 큰 조건을 만족하여 교환
if(leftChild.compareTo(relocateData) * this.multiple > 0) {
this.array[current] = leftChild;
this.array[leftIndex] = relocateData;
current = leftIndex;
} else {
break;
}
// 두 자식 모두와 비교해야 한다면
} else {
// 오름차순(최소힙)이라면 좌/우측 중 더 작은 값의 자식 노드와 비교 후 교환해야 한다.
// 좌 / 우측 비교 시 좌측이 더 작으면 0보다 작은 값을 반환하고 -1을 곱하면 0보다 큰 조건을 만족하여 좌측 자식으로 설정. 아니면 우측
// 내림차순(최대힙)이라면 좌/우측 중 더 큰 값의 자식 노드와 비교 후 교환
// 좌 / 우측 비교 시 좌측이 더 크다면 0보다 큰 값을 반환하고 1을 곱하면 0보다 큰 조건을 만족하니 좌측 자식으로 설정. 아니면 우측
T targetToSwap = leftChild.compareTo(rightChild) * this.multiple > 0 ? leftChild : rightChild;
int swapIndex = leftChild.compareTo(rightChild) * this.multiple > 0 ? leftIndex : rightIndex;
// 오름차순(최소힙)이라면 자식의 값이 대체값보다 더 작다면 교환
// 자식 / 대체값 비교 시 자식이 더 작으면 0보다 작고 -1 곱하면 0보다 크니 조건 만족하여 교환
// 내림차순(최대힙)이라면 자식의 값이 대체값보다 더 크다면 교환
// 자식 / 대체값 비교 시 자식이 더 크다면 0보다 크고 1 곱하면 0보다 크니 조건 만족하여 교환
if(targetToSwap.compareTo(relocateData) * this.multiple > 0){
this.array[current] = targetToSwap;
this.array[swapIndex] = relocateData;
}
current = swapIndex;
}
}
}
}
}
4. 자바 Collection Framework 내의 우선 순위 큐 사용하기
이미 이전 포스팅(여기)에서 자바의 Collection Framework 관련 내용을 설명하여 우선 순위 큐에 대해서도 진행한 적이 있다.
여기서 추가로 설명하며 어떻게 사용할 수 있는지 대략적으로 알아보자. 여기서는 생성, 데이터 저장 및 추출, 정렬 방식 지정 등을 하는 법을 알아보자.
① 기본 생성, 최소/최대힙 정렬하기
package com.test;
import java.util.PriorityQueue;
import java.util.Collections;
public class PriorityQueueTest{
public static void main(String[] args) {
// 숫자를 저장하는 우선 순위 큐 생성
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(10);
pq.add(5);
pq.add(30);
pq.add(27);
pq.add(13);
// 위와 같이 저장하면 기본적으로 최소힙(최소값이 우선 순위)로 저장된다.
// 아래와 같이 출력해보자.
while(!pq.isEmpty()){
System.out.print(pq.poll() + ", "); // 5, 10, 13, 27, 30
}
System.out.println();
// 이를 최대힙으로 저장하도록 하려면 아래와 같이 진행한다.
// reverseOrder를 통해 최대힙으로 구성되도록 한다.
pq = new PriorityQueue<>(Collections.reverseOrder());
pq.add(10);
pq.add(5);
pq.add(30);
pq.add(27);
pq.add(13);
// 위와 같이 저장하면 기본적으로 최대힙(최대값이 우선 순위)로 저장된다
// 아래와 같이 출력해보자.
while(!pq.isEmpty()){
System.out.print(pq.poll() + ", "); // 5, 10, 13, 27, 30
}
}
}
② Comparator를 이용하여 정렬 순서 지정하기
package com.test;
import java.util.PriorityQueue;
import java.util.Collections;
import java.util.Comparator;
public class PriorityQueueTest{
public static void main(String[] args) {
// Test Class의 Object를 저장하는 우선 순위 큐 생성
PriorityQueue<Test> pq = new PriorityQueue();
// Test Object 저장
pq.add(new Test(10, "Banana"));
pq.add(new Test(5, "Apple"));
pq.add(new Test(8, "Kiwi"));
pq.add(new Test(30, "Lemon"));
pq.add(new Test(2, "Melon"));
// 정렬 방식은 아래 Test Class를 확인
// 출력 결과 : [2 : Melon], [5 : Apple], [8 : Kiwi], [10 : Banana], [30 : Lemon],
while(!pq.isEmpty()){
System.out.print(pq.poll() + ", ");
}
System.out.println();
// Comparator를 이용하여 별도의 방식으로 저장하기
// 각 String의 길이를 기반으로 하는 경우
pq = new PriorityQueue(new Comparator<Test>(){
@Override
public int compare(Test t1, Test t2){
return t1.s.length() - t2.s.length();
}
});
// Test Object 저장
pq.add(new Test(10, "3자리"));
pq.add(new Test(5, "5자리!~"));
pq.add(new Test(8, "4자리!"));
pq.add(new Test(30, "1"));
pq.add(new Test(2, "7자리는어떨까"));
// 아래 출력 결과
// [30 : 1], [10 : 3자리], [8 : 4자리!], [5 : 5자리!~], [2 : 7자리는어떨까],
while(!pq.isEmpty()){
System.out.print(pq.poll() + ", ");
}
}
}
// 비교 대상을 만들기 위한 Class
class Test implements Comparable<Test>{
int a;
String s;
public Test(int a, String s){
this.a=a;
this.s=s;
}
// 아래와 같이 Comparable을 구현하였기에 오름차순으로 구현된다.
// 내림차순으로 하고 싶다면 o.a - this.a 로 한다.
// 만약 String을 기반으로 오름차순으로 하는 경우는 this.s.compare(o.s);
// 만약 String을 기반으로 내림차순으로 하는 경우는 o.s.compare(this.s);
@Override
public int compareTo(Test o) {
return this.a - o.a;
}
@Override
public String toString() {
return "[" + this.a + " : " + this.s + "]";
}
}
오류가 있는 부분은 댓글로 남겨주시면 반영하겠습니다. 감사합니다.
'자바 프로그래밍 > 자료구조(Data Structure)' 카테고리의 다른 글
| 자료구조 - 트라이(Trie) (6) | 2020.10.25 |
|---|---|
| 자료구조 - 그래프(Graph) (0) | 2020.10.20 |
| 자료구조 - 스택, 큐 직접 구현(Stack, Queue) (0) | 2020.09.30 |
| 자료구조 - 세그먼트 트리(Segment Tree) (0) | 2020.09.20 |
| 자료구조 - 이진 탐색 트리(Binary Search Tree) (2) | 2020.08.24 |
