[Java Heap] 자바 힙 개념 정리 (feat. 시간복잡도)

자바 힙(Heap)에 대한 자세한 설명: 자바에서 힙(Heap)은 동적으로 생성된 객체들이 저장되는 메모리 영역으로, 가비지 컬렉터에 의해 관리되는 중요한 부분입니다. 📚

---

힙이란?

• 정의: 힙은 동적으로 할당된 객체들이 저장되는 메모리 영역으로, 자바 가상 머신(JVM)에서 관리됩니다. 힙 영역은 가비지 컬렉터에 의해 관리되며, 더 이상 사용되지 않는 객체들을 자동으로 정리합니다.
• 특징: 힙은 모든 객체와 배열이 생성될 때 사용되는 공간입니다. 이 영역은 실행 시간에 크기가 동적으로 변할 수 있으며, 힙의 크기는 JVM 옵션에 의해 조절될 수 있습니다. 그리고 중복 값이 허용 됩니다.

힙의 특징

• 완전 이진 트리: 힙은 완전 이진 트리의 형태를 가지며, 이로 인해 배열을 사용하여 효율적으로 구현할 수 있습니다.
• 느슨한 정렬 상태: 힙은 느슨한 정렬 상태를 유지합니다. 큰 값은 위에 있고, 작은 값들은 아래에 있습니다. 이는 우선순위 큐 구현에 적합합니다.
• 효율적인 삽입 및 삭제: 힙에서의 삽입과 삭제 연산은 O(log n)의 시간 복잡도를 가집니다. 이는 힙이 데이터를 관리하는 데 매우 효율적임을 의미합니다.

 

 

힙의 구현

힙은 배열을 통해 쉽게 구현할 수 있으며, 노드 간의 관계는 다음과 같은 인덱스 계산법을 사용합니다.

• 루트 노드: 인덱스 0
• 부모 노드: (자식 인덱스 - 1) / 2
• 왼쪽 자식 노드: 부모 인덱스 * 2 + 1
• 오른쪽 자식 노드: 부모 인덱스 * 2 + 2

 

최소 힙

• 정의 및 특징: 최소 힙에서는 각 부모 노드의 값이 자식 노드의 값보다 작거나 같아야 합니다. 이로 인해 힙의 루트에는 항상 가장 작은 요소가 위치하게 됩니다.

최소 힙

 

최대 힙

• 정의 및 특징: 최대 힙에서는 각 부모 노드의 값이 자식 노드의 값보다 크거나 같아야 합니다. 최대 힙의 루트 노드에는 힙 내의 가장 큰 요소가 위치하게 됩니다.
  
  

최대 힙

 

시간 복잡도

삽입 연산

• 삽입 연산은 새로운 요소를 힙의 마지막에 추가한 후, 힙의 조건을 만족시키기 위해 부모 노드와 비교하며 필요한 경우 위치를 교환합니다.
• 이 과정은 최악의 경우 힙의 높이만큼 반복될 수 있으며, 힙은 완전 이진 트리이기 때문에 높이는 log₂n을 넘지 않습니다.
• 따라서 삽입 연산의 시간복잡도는 O(log n) 입니다.
  
  

삭제 연산

• 삭제 연산은 힙에서 최댓값(최대 힙의 경우) 또는 최솟값(최소 힙의 경우)을 제거하는 연산입니다. 힙에서는 루트 노드가 이 값을 가지므로, 루트 노드를 제거하고 마지막 노드를 루트로 옮긴 후, 다시 힙의 조건을 만족시키기 위해 자식 노드와 비교하며 위치를 교환합니다.
• 이 과정 역시 최악의 경우 힙의 높이만큼 반복될 수 있으므로, 삭제 연산의 시간복잡도는 O(log n) 입니다.

•