힙(Heap), 최소 힙(Min Heap), 최대 힙(Max Heap)이 뭐야?

---

---

✅ 힙(Heap)

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

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

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

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

---

✅ 최소 힙(Min Heap)

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

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

최소 힙의 삽입 과정

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

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

최소 힙의 삭제 과정

힙은 삭제할 때 최상위 노드를 반환하며 삭제한다. 마치 Queue의 poll()와 같다.
최상위 노드를 삭제한 후 최상위 노드에 가장 마지막 위치의 노드를 위치시킨다.

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

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

---

✅ 최대 힙(Max Heap)

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

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

최대 힙의 삽입 과정

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

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

최대 힙의 삭제 과정

힙은 삭제할 때 최상위 노드를 반환하며 삭제한다. 마치 Queue의 poll()와 같다.
최상위 노드를 삭제한 후 최상위 노드에 가장 마지막 위치의 노드를 위치시킨다.

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

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

---

✅ 우선순위 큐(Priority Queue)

자바에서는 우선순위 큐(Priority Queue)가 우선순위를 선정할 때 힙 방식으로 정렬한다.

우선순위 큐의 사용법에 대해 정리한 글이다.