Priority Queue(우선순위 큐)

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다.

Priority Queue(우선순위 큐)

힙의 응용 : 우선순위 큐

최대 우선순위 큐(Maximum Priority Queue)는 다음의 두 가지 연산을 지원하는 자료구조이다.

- INSERT(x) : 새로운 원소 x를 삽입

- EXTRALT_MAX() : 최대값을 삭제하고 반환

최소 우선순위 큐(Minimum Priority Queue)는 EXTRALT_MAX 대신 EXTRALT_MIN을 지원하는 자료구조이다.

- MAX HEAP을 이용하여 최대 우선순위 큐를 구현

INSERT 연산

의사코드

 MAX-HEAP-INSERT(A, key) {    // A : heap
heap_size = heap_size - 1;
A[heap_size] = key;
i = heep_size;    // i : 문제아 노드
while (i > 1 and A[PARENT(i)] < A[i]) {    // PARENT(i) : 부모 값, A[i] : 문제 값
exchange A[i] and A[PARENT(i)];
i = PARENT(i);
}
}

EXTRACT_MAX 연산

의사코드

HEAP-EXTRACT-MAX(A) {
if heap_size[A] < 1
then error "heap underflow"
max <- A[1]
A[1] <- A[heap_size[A]]
heap_size[A] <- heap_size[A] - 1
MAX-HEAPIFY(A, 1)
return max
}

소스 코드(JAVA)