[Java] 자료구조 - 우선순위 큐(Priority Queue) & 힙(heap) 이란 무엇인가?

우리가 알고있는 일반적인 큐(Queue)는 FIFO(First In - First Out) 구조입니다.

 

즉, 어떤 부가적인 조건 없이 먼저 들어온 데이터가 먼저 나가는 구조였습니다.

 

 

1. 우선순위 큐 - Priority Queue

 

1.1 우선순위 큐 (Priority Queue)란?

 

우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 구조입니다.

 

우선순위 큐는 힙(Heap)이라는 자료구조를 가지고 구현할 수 있습니다.

일상적인 예를 들자면, 제일 응급한 환자부터 치료하는 병원의 응급실이라고 할 수 있습니다.

 

즉, 우선순위가 가장 높은 환자부터 먼저 치료를 하는 것입니다.

 

 

 

1.2 우선순위 큐를 구현하는 방법

 

 

1.2.1 구현 방법 종류

1. 배열(Array)로 구현하는 방법

 

2. 연결리스트(LinkedList)로 구현하는 방법

 

3. 힙(Heap)을 활용하는 방법

 

1.2.2 배열 구현의 문제점

만일 배열로 구현한다면 우선순위가 높은 순서대로 배열의 가장 앞부분에 넣는다면 인덱스를 이용하여 데이터를 반환하면 되기 때문에 어렵지 않습니다.

 

하지만 배열의 경우 아래와 같은 단점이 따릅니다.

 

1. 우선순위가 중간인 것이 들어가야 하는 삽입이나 삭제하는 과정에서 데이터를 한 칸씩 당기거나 밀어야 하는 연산이 반복적으로 필요하다.

 

2. 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위 비교가 필요하다.

 

1.2.3 연결리스트 구현의 문제점

만일 연결리스트로 구현한다면 우선 순위가 높은 순서대로 연결 시키고 우선순위가 높은 데이터의 반환은 어렵지 않습니다.

 

연결리스트의 경우는 배열의 첫 번째 단점은 문제가 되지 않는다고 해도

 

"삽입의 위치를 찾기 위해 첫번재 노드에서부터 시작해 마지막 노드에 저장된 데이터와 우선순위를 비교해야 할 수 있다"

---

 

위와 같은 문제들 때문에 우선순위 큐는 주로 힙(Heap)을 이용해서 구현하는 것이 일반적입니다.

 

 

위에서 우선순위 큐에 대해 간략히 설명했으니 이를 구현하기 위해 힙(Heap)에 대해 설명하겠습니다.

2. 힙 - Heap

 

 

2.1 자료구조 힙(heap)이란?

 

1. 힙은 완전 이진 트리(Complete Binary Tree) 로 우선순위 큐를 위해 만들어진 자료구조이다.

 

2. 여러개의 값들 중 최대값이나 최소값을 빠르게 찾아낼 수 있도록 만들어졌다.

 

3. 힙은 일종의 반정렬 상태(느슨한 정렬)를 유지한다.

 

4. 힙 트리에서는 중복된 값을 허용한다.

 

 

 

2.2 힙(heap)의 종류

 

- 최대 힙 (max heap)

 

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• key(부모노드) >= key(자식노드)

 

- 최소 힙 (min heap)

 

• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
• key(부모노드) >= key(자식노드)

 

 

 

 

2.3 힙(heap)의 구현

 

• 힙을 저장하는 표준적인 자료구조는 배열이다.
• 구현을 쉽게 하기 위해 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다. (루트노드의 오른쪽 노드 번호는 항상 3임)

 

- 힙에서의 부모 노드와 자식 노드의 관게

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

 

 

 

 

 

2.4 힙(heap)의 삽입

 

위 힙 구조 안에 있는 숫자를 데이터 겸 우선순위라고 가정해봅시다.

 

 

위 상황에서 8을 추가한다고 가정 시

 

새로운 데이터는 우선순위가 제일 낮다는 가정하에서 마지막 위치에 저장한다.

 

그리고 부모 노드와 우선순위를 비교하여 위치가 바뀌어야 한다면 바꿔주고

 

제 자리를 찾을 때까지 반복한다.

 

 

위에서 언급한 '마지막 위치'는 노드를 추가한 이후에도 완전 이진 트리가 유지되는 마지막 레벨의 가장 오른쪽 위치를 의미합니다.

 

 

 

---

 

 

2.5 힙(heap)의 삭제

 

그렇다면 위의 구조에서 삭제는 어떻게 구현될까?

 

우선순위 큐의 삭제는 가장 높은 우선순위의 데이터 삭제를 의미합니다.

 

하지만 삭제한 뒤에 빈 루트 노드를 어떻게 채울까요?

- 흐름

 

1. 최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제됨

 

2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져옴

 

3. 힙을 재구성함