[자료구조] Heap

🎯 Heap

---

Heap(힙)은 최대 값 또는 최소 값을 빠르게 찾기 위한 자료구조입니다. 일반적으로 우선순위 큐(Priority Queue)와 같이 사용됩니다.

부모 노드와 자식 노드 간의 크기 관계를 이용하여 효율적인 삽입, 삭제, 탐색 연산을 수행할 수 있는 트리 기반의 자료구조입니다.

Heap의 구조

---

Heap은 완전 이진 트리(Complete Binary Tree)의 형태를 갖고 있습니다. 완전 이진 트리는 모든 레벨에서 노드들이 꽉 차있고, 마지막 레벨에서는 왼쪽부터 순서대로 채워져 있습니다.

Heap은 크게 Max Heap과 Min Heap으로 나눌 수 있습니다. Max Heap은 부모 노드가 자식 노드보다 큰 값을 가지는 Heap이고, Min Heap은 부모 노드가 자식 노드보다 작은 값을 가지는 Heap입니다.

Heap의 특징

---

1. Heap은 항상 완전 이진 트리의 형태를 유지해야 합니다.
2. Max Heap에서는 루트 노드가 최대값을 가지며, Min Heap에서는 루트 노드가 최소값을 가집니다.
3. 부모 노드의 값은 항상 자식 노드의 값보다 크거나(Max Heap) 혹은 작아야(Min Heap) 합니다.
4. Heap에서는 새로운 노드를 삽입할 때, 항상 완전 이진 트리의 마지막 노드에 삽입합니다.
5. Heap에서는 루트 노드를 삭제할 때, 항상 마지막 노드를 루트 노드로 옮긴 후, Heap의 특성을 유지하기 위해 다시 정렬합니다.

Heap의 연산

---

1. 삽입(Insert): Heap에 새로운 노드를 추가합니다.
2. 삭제(Delete): Heap에서 루트 노드를 제거합니다.
3. 탐색(Search): Heap에서 최소 값 또는 최대 값에 접근합니다.
4. Heapify: 주어진 배열을 Heap으로 변환합니다.

Heap은 이진 탐색 트리와는 다르게 높이가 log(n)으로 유지되지 않습니다. 따라서 Heap에서의 삽입, 삭제, 탐색 연산의 시간 복잡도는 O(log n)입니다.

Heap 장단점

---

⭐️ Heap 장점

1. 힙은 삽입과 삭제가 O(log n)의 시간 복잡도로 가능합니다. 이는 배열이나 리스트를 이용한 일반적인 자료구조의 O(n) 시간 복잡도와 비교해서 빠른 속도를 보입니다.
2. 힙은 최대값 또는 최소값을 O(1) 시간 복잡도로 찾을 수 있습니다. 이는 정렬된 배열에서 최대값 또는 최소값을 찾는 것보다 더 빠르며, 일부 알고리즘에서 중요한 역할을 합니다.
3. 힙은 완전 이진 트리이므로 배열을 이용하여 구현하기 쉽습니다.

💀️ Heap 단점

1. 힙은 특정 값을 찾는 탐색 연산에는 적합하지 않습니다. 이는 트리를 탐색하는 과정에서 특정 노드를 찾기 위해 모든 노드를 탐색해야 하기 때문입니다.
2. 힙은 일반적으로 상수 계수가 크기 때문에, 작은 규모의 자료를 처리하는 데는 효율적이지 않을 수 있습니다.
3. 힙은 각 노드가 두 개의 자식 노드를 가지므로, 메모리 공간을 많이 사용할 수 있습니다.