자료구조 - [ Binary Heap ]

Binary Heap

Heap은 트리에 기반한 특별한 자료구조로 우선순위가 높은 데이터가 부모로 배치되고 우선순위가 낮은 데이터가 자식으로 배치되는 관계를 가지고 있다. 삽입 순서와 상관없이 항상 우선순위가 가장 높은 데이터를 꺼내거나 삭제하기 때문에, 우선순위가 필요한 대기열이나 데이터 정렬이 필요할 때 사용할 수 있다.

Heap에는 Binary Heap, Fibonacci Heap 등이 존재한다.

 

Binary Heap은 Complete Binary Tree의 구조를 가지고 있으며, 삽입과 삭제 시 트리를 우선순위에 따라 재배치하는 과정을 거친다.

 

---

Binary Heap 삽입

삽입시 항상 맨 마지막 Leaf 노드로 삽입되며, 삽입 후 부모의 우선순위와 비교해 Swap 한다.

부모의 우선순위보다 낮을 때까지 삽입된 노드를 상위로 올리는 것을 UpHeap 이라고 한다.

 

ex) 

 

 

---

Binary Heap 삭제

Binary Heap은 루트 노드만 삭제할 수 있다. 루트 노드를 맨 마지막 Leaf 노드와 Swap한 후, Swap된 Leaf 노드를 삭제한다. 새롭게 루트 노드가 된 노드를 두 개의 자식 노드 중 우선순위가 더 높은 자식 노드와 Swap하고, 자식 노드의 우선순위가 낮을 때 까지 Swap한다. 

Heap의 구조를 유지하기 위해 부모의 노드가 자식 노드보다 우선순위가 높을 때까지 아래로 내리는 것을 DownHeap이라고 한다.

 

ex)

 

---

참조

https://www.codelatte.io/courses/java_data_structure

자바 자료구조 강의 - 코드라떼