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

우선 순위 큐(Priority Queue)란 

큐는 FIFO(First In First Out) 구조로 먼저 들어온 순서대로 나가는 자료구조입니다. 
우선 순위 큐는 들어온 순서에 상관 없이 우선순위가 높은 순서대로 나가는 추상 자료형(ADT)입니다. 

흔히 힙(heap)을 우선 순위 큐라고 생각하시는데 우선 순위 큐는 연결 리스트나 배열 등 다양한 방식으로 구현할 수 있습니다. 하지만 힙(heap)으로 구현하는 것이 삽입과 삭제 연산에서 O(log n)의 시간 복잡도를 보장하여 효율적이기 때문에 많이 사용합니다.

 

힙(heap)

사전적 의미로는 "더미, (아무렇게나) 쌓다" 입니다. 

스택(stack)이랑 의미가 비슷해 보이지만 스택은 하나하나 차곡차곡 쌓는 거고 힙(heap) 아무렇게나 쌓습니다. 

 

컴퓨터 용어로서 힙(heap)의 의미로는

최대값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete Binary Tree)

이 힙(heap)은 나중에 배울 우선 순위 큐를 위해 만들어진 자료구조이다.

 

힙(heap)의 종류

1. 최대 힙(Max Heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• key(부모(parent) 노드) > = key(자식(child 노드)
• 가장 큰 값이 루트 노드에 있음

2. 최소 힙(Min Heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
• key(부모(parent) 노드) < = key(자식(child 노드)
• 가장 작은 값이 루트 노드에 있음

 

힙(Heap) 구현(배열)

• 힙은 완전 이진 트리 -> 일반적으로 배열로 표현
• 가독성 및 이해하기 쉽게 하기 위해서 배열의 인덱스는 1부터 시작한다고 가정(전제 조건입니다.)
• 루트 노드의 인덱스가 i = 1일 때
  • 노드 i의 부모 노드 인덱스: [i/2]
  • 노드 i의 왼쪽 자식 인덱스: 2*i
  • 노드 i의 오른쪽 자식 노드 인덱스: 2*i +1 

힙 삽입

1. 초기 상태
         1
       /   \
      5     2
     / \   / \
    7   6 4   3
   / \
  10  9

배열: [null, 1, 5, 2, 7, 6, 4, 3, 10, 9]


2. 값 0을 마지막에 추가
         1
       /   \
      5     2
     / \   / \
    7   6 4   3
   / \ /
  10 9 0

배열: [null, 1, 5, 2, 7, 6, 4, 3, 10, 9, 0]


3. 0과 부모(6) 비교 후 교환 (0 < 6)
         1
       /   \
      5     2
     / \   / \
    7   0 4   3
   / \ /
  10 9 6

배열: [null, 1, 5, 2, 7, 0, 4, 3, 10, 9, 6]


4. 0과 부모(5) 비교 후 교환 (0 < 5)
         1
       /   \
      0     2
     / \   / \
    7   5 4   3
   / \ /
  10 9 6

배열: [null, 1, 0, 2, 7, 5, 4, 3, 10, 9, 6]


5. 0과 부모(1) 비교 후 교환 (0 < 1)
         0
       /   \
      1     2
     / \   / \
    7   5 4   3
   / \ /
  10 9 6

배열: [null, 0, 1, 2, 7, 5, 4, 3, 10, 9, 6]

힙 삭제

1. 초기 상태
         1
       /   \
      5     2
     / \   / \
    7   6 4   3
   / \
  10  9

배열: [null, 1, 5, 2, 7, 6, 4, 3, 10, 9]


2. 값 6 찾기 (인덱스 5)
         1
       /   \
      5     2
     / \   / \
    7   6 4   3
   / \
  10  9
      ^
      삭제할 노드

배열: [null, 1, 5, 2, 7, 6, 4, 3, 10, 9]


3. 마지막 노드(9)를 삭제할 위치로 이동
         1
       /   \
      5     2
     / \   / \
    7   9 4   3
   /
  10

배열: [null, 1, 5, 2, 7, 9, 4, 3, 10]


4. 새 위치의 9와 자식 비교
   - 이 위치에서 9는 자식이 없으므로 비교 필요 없음
   - 힙 속성 만족하므로 종료

최종 상태:
         1
       /   \
      5     2
     / \   / \
    7   9 4   3
   /
  10

배열: [null, 1, 5, 2, 7, 9, 4, 3, 10]