우선순위큐

  • 큐는 선입선출 방식으로 먼저 들어간 원소가 가장 먼저 나오게 된다.
  • 하지만 우선순위큐는 들어간 순서에 상관없이 우선순위가 높은 원소가 가장 먼저 나오게 된다.
  • 우선순위큐를 구현하는 방법은 총 3가지가 있다.
    • 배열 → 데이터를 삽입하거나 삭제하는 과정에서 기존에 있던 데이터를 한칸씩 당기거나 밀어야 하는 연산을 해야 한다.
    • 연결리스트 → 리스트는 배열처럼 한칸씩 밀거나 당기는 연산은 없지만, 삽입 위치를 찾아야하기 때문에 배열과 비슷하게 전체를 순회하는 비교연산을 하게 된다.
    • 힙 → 완전이진트리의 구조로 트리의 높이(logN)만큼 비교연산을 한다.

우선순위큐 삽입

  • 최소힙을 기준으로 생각한다. pq1

다음과 같이 기존에 원소가 들어있는 우선순위큐에 ‘4’라는 새로운 원소가 들어온다고 할 때 이루어지는 연산과정을 살펴보자.

pq2

‘4’는 부모노드인 ‘8’을 비교한 후 자신이 더 작은값이기 때문에 서로 자리를 교체한다.

그리고 다시 부모노드인 ‘1’과 비교한 후 부모가 더 작은값이기 때문에 조건을 충족하고, 그대로 자리를 유지한다.

pq3

우선순위큐 삭제

pq4

삭제를 할때는 루트노드를 삭제한다.

pq5

그리고 마지막 노드에 있는 값을 루트노드로 가져온다.

pq6

pq7

그리고 옮겨진 루트노드를 자식 노드와 비교하여 자신보다 작은값이 있으면 자리를 바꾼다.

pq8

‘2’ 이 ‘8’ 보다 작으므로 부모노드로 올라간다.

pq9

다시 자식노드와 비교하여 만약 자신보다 작은 값이 있으면 자리를 교체한다.

여기서 ‘5’가 ‘8’보다 작으므로 부모노드로 올라간다.

pq10

package coupang;

import java.util.Arrays;

public class 우선순위큐 {
	public static void main(String[] args) {
		int[] arr = { 9, 8, 1, 2, 5, 4, 7, 6, 3 };
		우선순위큐  pq = new 우선순위큐();
		for (int i = 0; i < arr.length; i++) {
			pq.push(arr[i]);
		}
		
		for (int i = 0; i < arr.length; i++) {
			System.out.print(pq.pop() + " ");
		}
	}

	int[] heap = new int[10];
	int hCnt = 0;

	public void push(int x) {
		heap[++hCnt] = x;
		int idx = hCnt;
		while (idx > 1 && heap[idx / 2] > heap[idx]) {
			if (idx == 1 || heap[idx / 2] < heap[idx])
				break;
			int tmp = heap[idx / 2];
			heap[idx / 2] = heap[idx];
			heap[idx] = tmp;
			idx /= 2;
		}
		System.out.println(Arrays.toString(heap));
	}

	public int pop() {
		int pop = heap[1];
		heap[1] = heap[hCnt--];
		int idx = 1;
		int next;
		while (true) {
			next = idx * 2;
			if (next < hCnt && heap[next] > heap[next + 1])
				next++;
			if (next > hCnt || heap[next] > heap[idx])
				break;
			int tmp = heap[idx];
			heap[idx] = heap[next];
			heap[next] = tmp;
			idx = next;
		}
		return pop;
	}

}

pq