[자료구조] 우선순위 큐(priority queue), 힙(heap)

 

 

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

 

 

우선순위 큐(priority queue)

• 큐에 우선순위의 개념을 도입한 자료구조
• 데이터들은 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 된다.
• 우선순위에 따라 스택이나 큐처럼 동작하기도 한다.

 

우선순위 큐 연산

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

 

 

 

우선순위 큐 구현 방법

1. 배열을 이용
   - 정렬된 배열을 사용하는 경우
   - 정렬되지 X 배열을 사용하는 경우
2. 연결 리스트를 이용
   - 정렬된 연결 리스트를 사용하는 경우
   - 정렬되지 않은 연결 리스트를 사용하는 경우
3. 힙(heap)을 이용

 

 

각 구현 방법에 따른 시간 복잡도

자료 구조	삽입 연산	삭제 연산
정렬된 배열 이용	$O(n)$	$O(1)$
정렬되지 않은 배열 이용	$O(1)$	$O(n)$ 우선순위가 높은 요소를 찾아야하기 때문
정렬된 연결 리스트를 이용	$O(n)$ 우선순위가 높은 요소를 찾아야 하기 때문	$O(1)$
정렬되지 않은 연결리스트 이용	$O(1)$ (처음에 삽입하는 경우)	$O(n)$ 배열과 마찬가지로 우선순위가 높은 요소를 찾아야 하기 때문
힙(heap)을 이용	$O(log_2n)$	$O(log_2n)$

 

 

 

 

 

---

힙(heap)

• 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
• 이진 탐색 트리와 달리 중복 값을 허용한다.
• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리이다.
• 일종의 느슨한 정렬 상태를 유지한다. (삭제 연산이 수행될 때 최대값(root)만 찾으면 되므로 전체를 정렬하지 않는다.)
• 최대값이나 최소값을 빠르게 찾을 때 유리하다.

 

 

힙의 종류

1. 최대 힙(max heap)
   : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
2. 최소 힙(min heap)
   : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

 

 

힙 구현 방법

1. 배열을 이용한 구현
   - 정렬된 배열 이용
   - 정렬되지 X 배열 이용
   - 구현을 쉽게 하기 위해서 인덱스 0은 사용하지 않는다.
   - 연산을 통해 노드의 인덱스를 알 수 있다.
     ##왼쪽 자식의 인덱스 = (부모의 인덱스) * 2##
     ##오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1##
     ##부모의 인덱스 = (자식의 인덱스) / 2##
2. 연결 리스트 이용

 

 

힙의 시간 복잡도

• 삽입 연산 : $O(log_2n)$
• 삭제 연산 : $O(log_2n)$

 

 

힙의 연산

• 삽입 연산
  (1) 요소를 힙의 가장 마지막 노드로 삽입
  (2) 부모 노드와 비교하여 부모 노드보다 클 경우 값 교환(부모 노드보다 작을 때까지 반복)
• 삭제 연산
  (1) 루트 노드 삭제
  (2) 빈 루트 자리에 힙의 마지막 노드를 가져옴
  (3) 양쪽 자식 중 큰 값과 교환이 일어남(자식 노드보다 클 때까지 반복)

 

 

힙 정렬(heap sort)

  최대 힙을 이용하면 정렬을 할 수 있다. 데이터를 차례대로 최대 힙에 추가하여 힙을 생성한 뒤, 요소를 하나씩 빼서 뒤쪽부터 저장하면 오름차순이 된다. 이렇게 힙을 사용하는 정렬 알고리즘을 힙 정렬(heap sort)이라고 한다. 전체 자료를 정렬하지 않고 큰 값만 필요한 경우에도 유용하게 사용된다.

    시간 복잡도  : $O(nlog_2n)$ (전체 높이가 $log_2n$인 완전 이진트리이기 때문)

 

 

 

힙 응용

• LPT 알고리즘(longest processing time first) : 가장 긴 작업을 우선적으로 할당하는 것
• 허프만 코드(Huffman codes)
  ex) 영문자 빈도수를 이용한 데이터 압축