[자료구조] 4-9. 힙(Heap)과 우선 순위 큐(Priority Queue)

힙

 

힙(Heap)은 다음과 같은 특성을 가지고 있다:

1. 완전 이진 트리이다.

2. (부모 노드의 index) = (자식 노드의 index) // 2

3. (왼쪽 자식의 index) = (부모 노드의 index) * 2

4. (오른쪽 자식의 index) = (부모 노드의 index) *2 +1

5. 루트의 index는 1이다. (구현의 편의상 1부터 시작한다.)

 

힙은 이러한 특성때문에 보통 배열로 많이 구현한다.

힙의 삽입과 삭제는 O(log N)이 걸리고, 탐색에는 O(N)이 걸린다.

 

힙은 두 가지의 종류가 있다. 최대 힙과 최소 힙이다.

최대 힙(max heap)은 부모 노드의 key값이 자식 노드의 key 값보다 큰 힙이고,

최소 힙(min heap)은 부모 노드의 key값이 자식 노드의 key 값보다 작은 힙이다.

 

 

힙의 삽입

 

힙의 삽입에는 다음의 과정이 있다:

1. 맨 끝자리에 노드를 삽입한다.

2. 노드를 부모와 비교하며 최대 힙 / 최소 힙의 조건에 맞게 바꾼다

(최대 힙에서 부모보다 더 크면 부모와 자리를 바꾼다 / 최소 힙에서 부모보다 더 작으면 부모와 자리를 바꾼다.)

3. 더 이상 바꿀 수 없을 때까지 또는 루트 노드에 다다를 때까지 2번을 반복한다.

 

아래는 10을 삽입하는 예시이다

 

 

힙의 삭제

 

힙의 삭제는 다음의 과정을 거친다:

1. 힙의 삭제는 루트 노드만 삭제할 수 있다.

2. 가장 마지막에 삽입된 노드(맨 끝 노드)가 루트 자리로 간다.

3. 루트 노드와 자식 노드를 비교하여 바꿔주면 된다.

  a. 최대 힙에서

      가. 자신보다 더 큰 자식이 없으면 마친다.

      나. 자신보다 더 큰 자식이 하나 있으면 그 노드와 교환한다.

      다. 둘 다 자신보다 크다면, 더 큰 노드와 교환한다.

      라. 계속 반복한다.

  b. 최소 힙에서

      가. 자신보다 더 작은 자식이 없으면 마친다.

      나. 자신보다 더 작은 자식이 하나 있으면 그 노드와 교환한다.

      다. 둘 다 자신보다 작다면, 더 작은 노드와 교환한다.

      라. 계속 반복한다.

 

아래는 최대 힙에서 노드를 삭제하는 과정이다.

 

우선순위 큐

 

우선순위 큐는 힙을 이용한 자료 구조이다.

기존의 스택이 선입후출, 큐가 선입선출로, 들어오고 나오는 순서와 관련이 있지만, 우선순위 큐는 데이터의 우선순위와 관련이 있다.

정렬, 네트워크, 운영체제의 작업 스케줄링 등에서 사용된다.

 

우선순위 큐의 연산

push(): 힙의 삽입과 같다. 완전 이진 트리의 마지막에 삽입하고, 정렬 과정이 일어난다.

pop(): 힙의 삭제와 같다. 루트를 삭제하고, 마지막에 삽입된 노드가 루트를 대신하고, 정렬 과정이 일어난다.