🔍 힙 자료구조란?

힙(Heap)은 여러 값 중 가장 크거나 작은 값을 빠르게 찾기 위해 고안된 완전 이진 트리 형태의 자료구조입니다

📌 힙 자료구조 규칙

• 힙은 항상 완전 이진 트리구조를 유지합니다
• 항상 최소 힙 또는 최대 힙 형태로 구성됩니다

📌 최소 힙과 최대 힙

• 최소 힙(Min Heap): 부모 노드가 자식 노드보다 항상 작거나 같습니다
• 최대 힙(Max Heap): 부모 노드가 자식 노드보다 항상 크거나 같습니다

📌 부모 - 자식 노드간의 관계

힙은 주로 배열을 이용해 구현되며, 자식과 부모 간의 인덱스 관계는 다음과 같습니다

• 부모 인덱스: (자식 인덱스)/2
• 왼쪽 자식: (부모 인덱스)*2
• 오른쪽 자식: (부모 인덱스)*2 + 1

📌 힙의 동작 과정 (최소 힙 기준)

먼저 예시 배열 [7, 3, 5, 2, 8, 1, 4, 6]을 완전 이진 트리 형태로 구성합니다

배열을 [1,3,2,6,8,5,4,7] 형태로 정렬했습니다

이 배열을 기반으로 최소 힙의 삽입,삭제 과정을 살펴보겠습니다

🎈 가정1 - 힙에 새로운 원소 1 삽입

기존 예시 배열에 원소 1을 삽입합니다
현재 힙은 최소힙 형태로 구성되어 있습니다

📌1회차 비교 과정:

새 원소(1)는 부모 노드(6)과 비교하며, 새 원소가 더 작으므로 서로의 위치를 바꿉니다

📌2회차 비교 과정:

다시 부모 노드(3)과 비교하며, 새 원소가 더 작으므로 서로의 위치를 바꿉니다

위와같은 삽입 과정을 통해,
새로운 원소 1이 삽입되었지만 최소 힙 구조가 유지됩니다

삽입 이후 배열은 [1,1,2,3,8,5,4,7,6] 형태입니다

🎈 가정2: 최소값인 루트 노드 원소 1을 삭제

앞서 삽입 과정에서 갱신된 배열의 첫 원소 1을 삭제합니다

먼저 루트 노드를 삭제한 후 마지막 노드(6)을 루트 위치로 이동합니다

📌1회차 비교 과정:

새 루트(6)은 두 자식(1, 2) 중 더 작은 값(1)과 교환합니다

📌2회차 비교 과정:

다시 자식들(3, 8)과 비교해 작은 값(3)과 교환합니다

위와같은 삭제 과정을 통해,
원소 1이 삭제되었지만 최소 힙 구조가 유지됩니다

삭제 이후 배열은 [1,3,2,6,8,5,4,7] 형태입니다

🛠️ 시간 복잡도

• 삽입: O(logN)
• 삭제: O(logN)
• 최소/최대값 조회: O(1)

🛠️ 공간 복잡도

힙은 배열 기반으로 구현되므로 공간 복잡도는 O(N)입니다

🧠 힙의 활용 예시

• 우선순위 큐 -> Java의 PriorityQueue
• 운영체제의 작업 스케줄링

📌 힙의 장점

• 빠르게 최소/최댓값을 찾을 수 있습니다

📌 힙의 단점

• 임의의 값 검색은 비효율적입니다

✍️ 결론

힙은 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진트리 형태의 자료구조입니다

최소, 최댓값을 빠르게 찾을 수 있다는 장점이 있지만, 임의의 값 검색은 비효율적이라는 단점이 있습니다