[Algorithms] Heap, Priority Queue
[Algorithms] Heap, Priority Queue
안녕하세요? 정리하는 개발자 워니즈입니다. 이번시간에는 우선순위 큐에 대해서 정리하는 시간을 갖어 보겠습니다. 지난 시간에 이어서 자료구조중 하나로 알고리즘에서 많이 활용되는 형태입니다.
지난시간에 정리를 해뒀지만, 일반적인 Queue의 형태는 First-In First-out의 구조를 보였습니다. 하지만, PQ같은 경우 정해진 우선순위에 따라서, 우선순위가 높은 데이터가 먼저 나오는 것을 말합니다.
우선순위 큐는 힙(Heap)이라는 자료구조를 가지고 구현하기 때문에 이둘을 묶어서 설명을 합니다.
1. Heap이란?
- 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 입니다.
- 여러개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 입니다.
1-1. Heap의 구현
- 힙을 저장하는 표준적인 자료구조는 배열입니다.
- 구현을 쉽게 하기 위해서는 첫번째 인덱스인 0은 사용하지 않습니다.
- 힙에서의 부모 노드와 자식 노드와의 관계
- 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
- 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
- 부모의 인덱스 = (자식의 인덱스) / 2
1-2. heap 의 삽입
heap에 새로운 요소가 들어가면, 일단 말단 노드에 새로운 노드를 삽입합니다. 그리고 삽입된 노드를 상위의 부모노드와 비교를 수행하면서 재정렬을 수행합니다.
1-3. heap의 삭제
heap에서 요소가 삭제되면, 일단 말단 노드를 최상단 노드로 옮겨 옵니다. 그리고 자식의 노드와 비교를 수행하면서 재정렬을 수행합니다.
2. Priority Queue란?
우선순위 큐를 활용하는 것은 우리 일생생활에 굉장히 많이 있습니다. 예를들어, 응급실에서 환자를 들어오는 순서대로 본다면 어떻게 될까요? 중증, 경증에 따라 우선순위를 둬야 하고 좀더 긴박한사람에 대해서 빠른 응급조치를 해야될 것입니다.
2-1. Priority Queue의 구현
public class Sample {
public static void main(String[] args) {
PriorityQueue pq = new PriorityQueue<>();
pq.add(4);
pq.add(19);
pq.add(2);
pq.add(1);
System.out.println(pq.poll()); // 1이 출력된다.
}
}
위의 예제에서 보시는것처럼, PriorityQueue라는 구현체가 있습니다. Interger object타입을 받을수 있게 셋팅을 해두었고, 각각 add라는 함수를 통해서 넣어주고 있습니다.
기존의 queue 자료구조였다면, poll을 수행하게 되면 4가 노출이 되어야 하지만, 1이 출력이 되고 있습니다. 오름차순으로 정렬이 내부적으로 된것입니다.
public class Sample {
public static void main(String[] args) {
PriorityQueue pq = new PriorityQueue<>(Collections.reverseOrder());
pq.add(4);
pq.add(19);
pq.add(2);
pq.add(1);
System.out.println(pq.poll()); // 19가 출력된다.
}
}
Collection의 reserseOrder라는 함수를 수행하게 되면, 내림차순으로 정렬이 됩니다. 그러면 가장큰수인 10이 출력이 됩니다.
2-2. Custom 객체에 대한 우선순위 큐 적용
class Prisoner {
String name;
int weight; // 형량
public Prisoner(String name, int weight) {
super();
this.name = name;
this.weight = weight;
}
}
위의 예제와 같이 죄수라는 객체를 생성했습니다. value로는 이름과 형량일라는 값이 있습니다. 이제 우선순위큐에 넣고, 형량이 가장 작은 사람이 출력이 되도록 정렬을 수행하겠습니다.
class Prisoner implements Comparable {
String name;
int weight; // 형량
public Prisoner(String name, int weight) {
super();
this.name = name;
this.weight = weight;
}
@Override
public int compareTo(Prisoner target) {
if (this.weight > target.weight) {
return 1;
} else if (this.weight < target.weight) {
return -1;
}
return 0;
}
일반적으로는 Custom 객체에 위와 같이 compareTo라는 함수를 오버라이드 하여 구현하게 됩니다. 그렇게 되면, 객체를 생성하여 queue에 넣을때마다, compareTo함수가 동작을 하게 되어, 정렬을 수행합니다.
private static PriorityQueue getPriorityQueue() {
Prisoner prisoner1 = new Prisoner("james", 5);
Prisoner prisoner2 = new Prisoner("schofield", 99);
Prisoner prisoner3 = new Prisoner("alex", 14);
Prisoner prisoner4 = new Prisoner("silvia", 10);
Prisoner prisoner5 = new Prisoner("thomson", 1);
PriorityQueue priorityQueue = new PriorityQueue();
priorityQueue.offer(prisoner1);
priorityQueue.offer(prisoner2);
priorityQueue.offer(prisoner3);
priorityQueue.offer(prisoner4);
priorityQueue.offer(prisoner5);
return priorityQueue;
}
객체를 생성하여, 위와 같이 pq에 넣는 과정을 거쳤습니다.
public static void main(String[] args) {
PriorityQueue priorityQueue = getPriorityQueue();
System.out.println("=============== Normal Order");
while (!priorityQueue.isEmpty()) {
Prisoner prisoner = priorityQueue.poll();
System.out.println(prisoner.name);
}
}
=============== Normal Order
thomson
james
silvia
alex
schofield
3. 관련 알고리즘 문제
- 자료구조 기본 문제
4. 마치며..
이번시간에는 자료구조에 대해서 정리를 해보았습니다. 자바에서 제공해주는 자료구조들은 정말 활용도가 높게 설계가 되어 있습니다. 특히 힙의 자료구조 같은 경우, 트리를 활용해서 정렬을 수행하다보니 수행속도 면에서 굉장히 빠르게 설계가 되어있습니다.
이러한 자료구조를 적절하게 활용한다면 프로그래밍에서도 효율적인 코딩이 가능할 것이라고 생각이 들었습니다.
다음시간에는 최단거리 알고리즘인 다익스트라에 대해서 정리를 해보도록 하겠습니다.
