[자료구조] 힙(heap) #java

 

힙(heap) 자료구조

---

안녕하세요? 장장스입니다.

오늘은 힙자료구조에 대해 알아보겠습니다.

 

 

힙 (heap)

---

힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기반으로 한 자료구조입니다.

 

힙에는 최대 힙(max heap)과 최소 힙(min heap)이 있습니다. 부모 노드가 자식 노드보다 크면 최대 힙, 반대이면 최소 힙입니다. 가장 큰 숫자가 뿌리에 있게 하려면 최대 힙, 가장 작은 숫자로부터 시작하려면 최소 힙을 사용하면 됩니다.

 

 

 

최대 힙 (max heap)

---

max heap은 root에 가장 큰 값이 오는 heap 입니다.

 

최소 힙 (min heap)

---

min heap은 root에 가장 작은 값이 오는 heap 입니다.

 

 

 

힙 추가

---

그렇다면 새로운 데이터를 추가하거나 제거는 어떻게 될까요? max heap, min heap의 규칙을 지키야 합니다. 최대 힙이면 부모 노드가 자식 노드보다 커야 하고 최소 힙은 자식 노드가 부모 노드보다 커야 합니다.

 

 

 

1. 비어있는 공간에 노드를 추가합니다.
2. 부모 노드보다 큰 숫자인지 확인하고 만약 그렇다면 두 노드를 바꿉니다. (trickle up)

 

 

 

힙 제거

---

1. 루트를 제거합니다.
2. 트리의 마지막 요소를 루트에 넣어줍니다.
3. 루트에서 시작하여 두 자식 중 큰 노드와 바꿔주어 힙의 규칙을 만족하게 합니다. (trickle down)

 

무언가를 제거할 때 힙에서는 항상 루트를 제거해야 합니다.

 

 

 

 

Post

---

• 2021.11.16 - [DataStructures] - [자료구조] 트리(Tree)

References

---

• [부스트코스] 자바로 구현하고 배우는 자료구조

 

---

잘못된 코드나 내용이 있다면 댓글을 남겨주세요. 즉시 수정하도록 하겠습니다! :)