[자료구조] Binary Heap

힙

• 완전 이진 트리 기반의 자료 구조이며, 최소힙과 최대힙 두 가지가 있고 해당 힙에 따라 특정한 특징을 지킨 트리
• 어떠한 값이 들어와도 특정 힙의 규칙을 지키게 만들어져 있다.

최대힙과 최소힙

• 최대힙 : 투트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 합니다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.
• 최소힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 합니다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.

최대힙의 삽입

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입
2. 이 새로운 노드를 부모 노드들과 크기를 비교하며 교환해서 힙의 성질을 만족시킨다.

최대힙의 삭제

최대힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제되고, 그 이후 마지막 노드와 루트 노드를 스왑하여 또다시 스왑 등의 과정을 거쳐 재구성