개발 공부 - [정렬] 힙(heap)의 다른 응용 : 우선순위 큐 (priority queue)

1) 최대 우선순위 큐 (maximum priority queue)는 다음의 두 가지 연산을 지원하는 자료구조

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

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

2) 최소 우선순위 큐 (minimum priority queue)는 EXTRACT_MAX 대신 EXTRACT_MIN을 지원하는 자료구조

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

INSERT의 수도 코드

MAX-HEAP-INSERT(A, key){

    heap_size = heap_size+1;

    A[heap_size] = key;

    i = heap_size;

    while(i>1 and A[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

    그러면 에러 heap underflow

max <- A[1]

    A[1] <- A[heap_size[A]]

    heap-size[A] <- heap-size[A] - 1

    MAX-HEAPIFY(A,1)

    return max