우선순위 큐

우선순위 큐는 들어간 순서에 상관없이 데이터의 우선순위에 따라서 우선순위가 높은 데이터부터 꺼내도록 만들어진 큐이다.

위 사진처럼 내부 요소는 힙으로 구성된 이진트리 형태이다.

우선순위 큐는 배열과 연결리스트, 힙으로 구현을 할 수 있다.

• 배열로 구현을 할 경우 삽입 삭제는 빠르지만, 나머지 인덱스를 한 칸씩 연산을 할 때마다 옮겨줘야 하기 때문에 번거롭다.
• 연결리스트로 구현할 경우 처음부터 끝까지 우선순위를 탐색해야 할 수도 있는데, 이는 큐의 성능을 크게 저하시킨다.

그래서 우선순위 큐를 구현할때는 힙을 사용하여 구현한다.

힙으로 구성되어 있기에 모든 연산과 시간복잡도 등은 힙과 동일하다.

힙

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
현재 들어있는 데이터 중 최대값, 최소값을 찾아내는 연산을 쉽게 하기 위해 만들어진 자료구조이다.

힙은 크게 최대 힙과 최소 힙으로 나눌 수 있다.

• 최대 힙
  • 루트 노드의 값이 가장 크다.
  • 각 노드의 값이 부모 노드의 값보다 작거나 같은 힙을 얘기한다.
• 최소 힙
  • 루트 노드의 값이 가장 작다.
  • 각 노드의 값이 부모 노드의 값보다 크거나 같은 힙을 얘기한다.

특징

힙에서 부모 노드와 자식 노드는 특별한 규칙이 존재한다.

• 왼쪽 자식의 인덱스는 부모의 인덱스 * 2
• 오른쪽 자식의 인덱스는 부모의 인덱스 * 2 + 1
• 부모의 인덱스는 자식의 인덱스 / 2

힙을 구현할 때 대표적으로 사용하는 것은 배열이다.
배열로 구현할 때, 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
만일 루트 노드의 인덱스가 0일 경우, 인덱스 2를 /2 한다 해도 0이 나올 수 없다.
그래서 루트 노드의 인덱스의 경우는 1로 시작을 한다.

또한 특정 위치의 노드 번호는 새로운 노드가 추가되어도 바뀌지 않는다.
ex) 루트 노드의 오른쪽 노드 번호는 항상 3이다.

연산

힙의 대표적인 연산에는 삽입, 삭제가 존재한다.

삽입

1. 이진트리의 맨 마지막에 데이터를 추가
2. 최대 힙 기준 맨 마지막에 삽입한 노드와 부모 노드를 비교한
3. 자신이 부모노드보다 값이 크다면 두 노드의 위치를 교환
4. 더이상 교환하지 않을 때까지 2~3번 반복

최소 힙이라면 2번에서 자신이 부모노드보다 값이 작다면 변경하면 된다.

삭제

1. 이진트리의 루트노드 데이터를 삭제
2. 현재 트리에서 가장 마지막에 있는 데이터를 루트 노드로 올림
3. 자신의 노드와 자식 노드를 비교
4. 자식 노드 중 더 큰 값을 지닌 노드와 자신의 위치를 교환
5. 더 이상 교환하지 않을 때까지 3~4번 반복

최소 힙이라면 4번에서 자신이 자식노드보다 값이 작고, 자식 노드 중 더 작은 값을 지닌 노드와 교환하면 된다.

시간복잡도

힙에서 데이터를 삽입, 삭제 할 때의 시간복잡도는 모두 O(logn)이다.

예제코드

자바에서는 기본적으로 PriorityQueue 객체를 제공해준다.

public class PriorityQueue {
    public static void main(String[] args) {
        Queue<Integer> queue = new java.util.PriorityQueue<>();
        queue.add(1);
        queue.add(3);
        queue.add(2);
        queue.add(5);

        System.out.println(queue.peek());

        queue.remove();
        queue.remove();
        System.out.println(queue.peek());
    }
}