[자료구조] 우선순위 큐 / 히프

우선순위 큐

• 우선순위 큐에서는 데이터들이 우선 순위를 가지고 있고 우선 순위가 높은 데이터가 먼저 나가게 된다.

 

우선순위 큐 ADT

객체: n개의 element형의 우선 순위를 가진 요소들의 모임
연산:
	create() ::= 우선순위 큐를 생성한다.
    init(q) := 우선순위 큐 q를 초기화 한다.
    is_empty(q) ::= 우선순위 큐 q가 비어있는지를 검사한다.
    is_full(q) ::= 우선순위 큐 q가 가득 찼는가를 검사한다.
    insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가한다.
    delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 이 요소를 반환한다.
    find(q) ::= 우선순위가 가장 높은 요소를 반환한다.

 

 

우선순위 큐의 구현 방법

1. 배열을 사용하는 방법
2. 연결 리스트를 사용하는 방법
3. 히프를 사용하는 방법

 

히프

• 히프는 완전 이진 트리 기반의 '더미'와 모습이 비슷한 특정한 자료 구조를 의미한다.
• 히프는 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조이다.
• 중복된 값을 허용한다. [이진트리는 불가]
• 느슨한 정렬 상태를 유지한다.

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

 

히프의 종류

1. 최대 히프
   • 부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전 이진트리
2. 최소 히프
   • 부모 노드의 키값이 자식 노드의 키값보다 작거나 같은 완전 이진 트리

 

히프트리에서의 삽입 알고리즘(의사 코드)

insert_max_heap(A, key):

heap_size <- heap_size + 1;
i <- heap_size;
A[i] <- key;
while i != 1 and A[i] > A[PARENT(i)] do
	A[i] <-> A[PARENT];
    i <- PARENT(i);

 

 

히프트리에서의 삭제 알고리즘

delete_max_heap(A):

	item <- A[1];
    A[1] <- A[heap_size];
    heap_size <- heap_size - 1;
    i <- 2;
    while i <= heap_size do
    	if i < heap_size and A[i + 1] > A[i]
        	then largest <- i + 1;
            else larget <- i;
        if A[PARENT(largest)] > A[largest]
        	then break;
        A[PARENT(largest)] <-> A[largest];
        i <- CHILD(largest);
        
return item;