[JAVA/자료구조] 힙(Heap), 최소 힙(Min Heap), 최대 힙(Max Heap)

힙(Heap)

힙은 완전 이진트리 형태로 최대, 최솟값을 빠르게 찾아내는데 유용한 자료구조이다.

• 힙은 중복값을 허용한다.
• 부모-자식 간 (레벨 별) 정렬은 보장하고, 형제간의 정렬은 보장하지 않아서 반 정렬 상태라고 볼 수 있다.

힙은 최소 힙(Min Heap), 최대힙(Max Heap) 두가지가 있다.

• 최소 힙은 루트노드가 최솟값이 되고, 부모노드의 key는 자식노드의 key보다 작아야 한다는 규칙이 있다.
• 최대 힙은 루트노드가 최댓값이 되고, 부모노드의 key가 자식 노드의 key보다 커야 한다는 규칙이 있다.

완전이진트리는 마지막 레벨을 제외하고 노드들이 가득 차 있는 트리를 말한다.
https://innovation123.tistory.com/107

[JAVA/자료구조] 트리(Tree), 이진트리(Binary Tree) 개념

---

최소 힙(Min Heap)

최소 힙(Min Heap)은 부모 노드의 key가 자식 노드의 key보다 작거나 같은 완전 이진트리이다.

• 다른 규칙은 없다. 단지 부모노드가 자식 노드의 key보다 작기만 하면 된다.

---

최소 힙의 삽입 과정

트리의 가장 끝 위치에 데이터를 삽입하고,

부모노드와 key값을 비교하여 작을 경우 부모 노드와 자리를 교체하는 것을 반복한다.

---

최소 힙의 삭제 과정

• 힙은 삭제할 때 최상위 노드를 반환하며 삭제한다. 마치 Queue의 poll()와 같다.

최상위 노드를 삭제한 후 최상위 노드에 가장 마지막 위치의 노드를 위치시킨다.

그 후, 삽입과 반대의 과정으로 자식노드와 비교하며 자리를 교체한다.

(좌, 우 노드와 비교하여 더 작은 값과 자리를 교체한다.)

---

최대 힙(Max Heap)

최대 힙(Max Heap)은 부모 노드의 key가 자식 노드의 key보다 크거나 같은 완전 이진트리이다.

• 다른 규칙은 없다. 단지 부모노드가 자식 노드의 key보다 크만 하면 된다.

---

최대 힙의 삽입 과정

트리의 가장 끝 위치에 데이터를 삽입하고,

부모노드와 key값을 비교하여 클 경우 부모 노드와 자리를 교체하는 것을 반복한다.

---

최대 힙의 삭제 과정

• 힙은 삭제할 때 최상위 노드를 반환하며 삭제한다. 마치 Queue의 poll()와 같다.

최상위 노드를 삭제한 후 최상위 노드에 가장 마지막 위치의 노드를 위치시킨다.

그 후, 삽입과 반대의 과정으로 자식노드와 비교하며 자리를 교체한다.

(좌, 우 노드와 비교하여 더 큰 값과 자리를 교체한다.)

---

우선순위 큐(Priority Queue)

자바에서는 우선순위 큐(Priority Queue)라는 자료구조 라이브러리로 힙을 지원한다.

사실 힙을 지원한다기보다는, 우선순위 큐가 우선순위를 선정할 때 힙 방식으로 정렬한다는 게 맞다.

우선순위 큐는 Queue와 비슷하지만, 선입선출 구조인 Queue와 달리 Queue에 들어있는 자료 중 우선순위를 설정하여 우선순위가 높은 순서대로 poll() 하는 구조이다.

 

우선순위큐에 대해 따로 정리해 놓은 글이 있으니 확인하시길 바랍니다.
2023.06.11 - [자료구조] - [JAVA/자료구조] 우선순위 큐(Priority Queue) (Heap)