자료구조) 자료구조 힙(Heap) 알아보기 - Priority Queue

 

우선 메모리 구조의 힙(Heap)과는 별개의 개념입니다.

 

Heap

• 우선순위 큐 - Priority Queue를 구현하기 위한 자료구조입니다.
• 우선순위의 데이터 검색과 삭제에 유용한 자료구조입니다.
• 우선순위 큐라고 해서 FIFO(First In First Out)의 큐와 비슷하다고 생각하시면 안됩니다.
• 기본적으로 Min Heap 과 Max Heap이 있습니다.

 

Min Heap

• 이진 힙의 구현 방식에서 최솟값을 찾기 위한 구조입니다.
• 부모노드는 자식노드보다 값이 작거나 같습니다. 
• 루트노드에 최솟값이 배정됩니다.

 

Max Heap

• 이진 힙의 구현 방식에서 최댓값을 찾기 위한 구조입니다.
• 부모노드는 자식노드보다 값이 크거나 같습니다.
• 루트노드에 최댓값이 배정됩니다.

 

Heap 구현 방식

 

기본적으로 Min Heap의 구현 방식은 위와 같습니다.

 

index 순으로 보면 0번째에 1 노드, 1번째에 5 노드, 2번째에 3 노드, 3번째에 7 노드, 4번째에 9 노드, 5번째에 8 노드 값이 들어있습니다.

아까 Min Heap의 구현 방식은 부모노드가 자식노드 보다 값이 작거나 같다고 했습니다. 

그렇다면 0번째 index의 1 노드부터 시작해서 아래 자식노드와 값을 비교해 값이 작다면 스왑(swap) 하는 방식으로 구현됩니다.

• 루트노드인 1 노드와 자식노드인 5 노드를 비교해 1 > 5  때문에 스왑하지 않습니다.
• 그 다음 5 노드와 자식노드인 7 노드를 비교 5 > 7  때문에 스왑하지 않습니다.
• 그 다음 5 노드와 다른 자식노드인 9 노드 비교 5 >9 때문에 스왑하지 않습니다.
• 다음 루트 노트인 1 노드와 다른 자식노드인 3 노드와 비교 1 > 3 때문에 스왑하지 않습니다.
• 다음 3 노드와 자식노드인 8 노드 비교 3 >8 때문에 스왑하지 않습니다.

위의 예시는 스왑이 필요하지 않게 값을 넣었기 때문에 스왑이 없었습니다. 하지만 아래와 같이 값을 넣으면 어떻게 될까요?

 

PriorityQueue<Integer> queue = new PriorityQueue<>();

queue.offer(3);
queue.offer(4);
queue.offer(5);
queue.offer(2);
queue.offer(1);

System.out.println(queue);

index 순으로 본다면 0 index -> 3 node, 1 index -> 4 node,  2 idnex  -> 5 node, 3 idnex  -> 2 node,  4 index  -> 1 node 가 들어갔습니다.

 

Min Heap으로 구현해본다면

• 루트노드인 3과 자식노드인 4를 비교 3 > 4 때문에 스왑하지 않습니다.
• 4 노드와 자식노드인 2 노드 비교 4 < 2 때문에 2와 4를 스왑합니다.
• 스왑된 2노드와 부모노드인 3 노드를 비교 3 < 2 때문에 3과 2를 스왑합니다.
• 현재 루트 노드는 2가 되었고 자식 노드로 내려가 3 노드와 오른쪽 자식 노드인 1을 비교 3 < 1 때문에 3과 1을 스왑합니다.
• 1과 부모노드인 2를 비교  1 < 2 때문에 1과 2를 스왑합니다.
• 루트노드는 1이 되었고 오른쪽 자식노드인 5와 비교 1 < 5 때문에 스왑하지 않습니다.

위의 과정을 통해 결과는 아래와 같이 출력됩니다.

[1, 2, 5, 4, 3]

---

이제 Max Heap으로 구현해보겠습니다. Min Heap과 정반대의 개념이라고 생각하시면 됩니다.

PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

queue.offer(3);
queue.offer(4);
queue.offer(5);
queue.offer(2);
queue.offer(1);

우선순위 큐 PriorityQueue로 선언하고 Collections.reversOrder() 메소드를 넣어주시면 Max Heap으로 구현됩니다.

• 루트노드인 3과 자식노드인 4를 비교 3 < 4 때문에 3과 4를 스왑합니다.
• 3 노드와 왼쪽 자식노드인 2를 비교 3 > 2 때문에 스왑하지 않습니다.
• 3노드와 오른쪽 자식노드인 1을 비교 3 >1 때문에 스왑하지 않습니다.
• 루트노드인 4의 오른쪽 자식노드인 5와 비교  4 < 5 때문에 4와 5를 스왑합니다.

 

위의 과정을 통해 결과는 아래와 같이 출력됩니다.

[5, 3, 4, 2, 1]

 

Insert

또 다른 데이터를 삽입 하게 된다면 위의 과정을 거쳐서 우선순위가 정해지게 됩니다.

 

Remove

데이터를 삭제하게 된다면 Min Heap 에서는 내림차순으로 값이 작은 수 부터 삭제됩니다.

반대로 Max Heap에서는 오름차순으로 값이 큰 수부터 삭제됩니다.

 

Peek

위의 예시에서 Min Heap에서 peek() 메소드의 값은 맨 앞의 값인 1이 출력이 됩니다.

Max Heap에서 peek() 메소드의 값은 맨 앞의 값인 5가 출력이 됩니다.

---

Reference

[자료구조/Java] 힙 구현

Java Heap & Priority Queue