[자료구조] 우선순위 큐와 힙

우선순위 큐(Priority Queue)

큐 형태로 우선순위가 높은 데이터가 먼저 나가는 자료구조

 

cf ) 큐(Queue)

먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조

 

  ADT(Abstract Data Type)  

- 객체

우선순위를 가진 요소들의 모음

 

- 연산

• insert(x)
  우선순위 큐에 요소 x 추가
• remove()
  우선순위 큐에서 가장 우선순위가 높은 요소를 삭제하고 반환
• find()
  우선순위 큐에서 가장 우선순위가 높은 요소를 반환

 

  구현 방법  

• 배열 또는 연결리스트를 이용 > 삽입 또는 삭제 연산을 위한 시간복잡도는 O(n) ( ∵ 선형 구조의 자료구조 )
• 힙 트리 이용  > 힙트리의 높이는 log₂(n+1)이며 힙의 시간복잡도는 O(log₂n) ( ∵ 완전이진트리 구조 )
  
  => 일반적으로 힙(Heap)을 이용하여 구현

 

 

---

 

힙(Heap)

우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조

 

  특징  

• 부모노드와 서브트리간 대소 관계가 성립된다. (반정렬 상태)
• 여러 개의 값 중 최대/소값을 찾아내는 연산이 빠르다.
• 이진탐색트리(BST)와 달리 중복된 값이 허용된다.

  종류  

• 최대 힙 (Max Heap)
  부모 노드의 키 값 ≥ 자식 노드의 키 값
  

 

• 최소 힙 (Min Heap)
  부모 노드의 키 값 ≤ 자식 노드의 키 값
  

 

  구현 방법  

배열을 이용하여 구현( ∵ 완전이진트리이므로 중간에 비어있는 요소 X )

- HOW TO

트리의 각 노드에 인덱스 번호를 붙인다.

 

 

- 특징

부모/자식 노드를 찾아가는 연산 구현이 간편 ( ∵ 배열로 구현)

• 자식노드를 구하는 경우
  • 왼쪽 자식노드 index = (부모 노드 index) * 2
  • 오른쪽 자식노드 index = (부모 노드 index) * 2 + 1
• 부모노드를 구하는 경우
  • 부모 노드 index = (자식노드 index) / 2

 

- 연산

힙 트리의 성질을 만족시키면서 연산하는 것이 중요하다.

• 삽입
  시간복잡도 O(log₂n) ( ∵ 최악의 경우 새로 추가된 노드가 루트노트까지 비교하며 올라감)
  
  1. 완전이진트리의 마지막 노드에 이어서 새로운 노드를 추가한다.
  2. 추가된 새로운 노드를 부모의 노드와 비교하여 교환한다.
  3. 정상적인 힙트리가 될 때까지 (더이상 부모노드와 교환할 필요가 없을 때까지) 2번을 반복한다.
• 삭제
  시간복잡도 O(log₂n) ( ∵ 최악의 경우 루트노트부터 가장 아래까지 내려감)
  
  1. 루트 노드를 삭제한다. ( ∵ 가장 높은 우선순위 )
  2. 루트 노드가 삭제된 빈자리에 완전이진트리의 마지막 노드를 가져온다.
  3. 루트 자리에 위치한 새로운 노드를 자식 노드와 비교하여 교환한다.
     최대 힙인 경우 - 자식노드 중 더 큰 값과 교환
     최소 힙인 경우 - 더 작은 값과 교환
  4. 정상적인 힙트리가 될 때까지 (더 이상 자식노드와 교환할 필요가 없을 때까지) 3번을 반복한다.

 

  구현  

소스 추가 예정