✍️ Heap

힙은 완전 이진 트리 기반의 자료구조이며, 최소힙과 최대힙 두 가지가 있고 해당 힙에 따라 특정한 특징을 지킨 트리를 뜻합니다.

📝 Heap의 종류

1. 최대 힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 합니다. 또한 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 합니다.
   => 최대 힙은 마치 피라미드 구조와 같다고 생각하면 된다.

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

📝 Heap의 삽입과 삭제

최대 힙과 최소 힙 모두 삭제와 삽입의 순서가 비슷한데.

✏️ 삽입

1. 힙의 마지막 노드 다음에 새로운 노드를 삽입합니다.

2. 부모 또는 자식 노드와 비교하여 힙의 종류에 맞게 교환합니다.

3. 이 과정을 반복하여 새로운 노드가 올바른 위치에 도달할 때까지 계속합니다.

✏️ 삭제

1. 최대 혹은 최소 값을 가진 루트 노드를 삭제합니다.

2. 힙의 마지막 노드를 루트 노드의 자리에 놓습니다.

3. 자식 노드와 비교하여 힙의 종류에 맞게 위치를 교환합니다.

4. 이 과정을 반복하여 노드가 올바른 위치에 도달할 때까지 계속합니다.

📝 Heap의 시간 복잡도

힙의 시간복잡도도 여타 자료구조와 마찬가지로 상황에 따라 다양할 수 있다.

• 노드의 삽입과 삭제 : O(log n)
• 최대 혹은 최소 값의 탐색 : O(1)
• 배열로부터 Heap 생성 : O(n)
• Heap 기반의 정렬 알고리즘 : O(n log n)