AI 요약관련 정보

• 힙은 이진 트리 기반의 자료구조로, 부모 노드가 자식 노드보다 크거나(최대 힙) 작아야(최소 힙) 하는 규칙을 가집니다. 🌳
• 힙은 항상 '완전 이진 트리' 형태를 유지하며, 마지막 레벨을 제외한 모든 레벨이 채워져 있고 마지막 레벨은 왼쪽부터 채워집니다. 🏗️
• 내부적으로는 노드 객체 대신 인덱스를 활용하는 리스트(배열)로 구현되어, 부모/자식 노드의 인덱스를 쉽게 계산할 수 있습니다. 🔢
• 새로운 노드를 추가할 때(Insert)는 맨 끝에 추가한 후 heapify_up (상향 재조정) 과정을 통해 적절한 위치로 이동시키며, 시간 복잡도는 O(log N)입니다. ⬆️
• 루트 노드를 제거할 때(Delete Root)는 마지막 노드를 루트로 옮긴 후 heapify_down (하향 재조정) 과정을 통해 적절한 위치로 이동시키며, 시간 복잡도는 O(log N)입니다. ⬇️
• 정렬되지 않은 요소들로 힙을 구성할 때(Build Heap)는 모든 요소를 넣은 후 중간 노드부터 역순으로 heapify_down을 적용하여 힙 속성을 만족시키며, 시간 복잡도는 O(N)입니다. 🛠️
• 힙은 값의 크기를 기준으로 요소를 꺼내는 특성 때문에 '우선순위 큐' 구현에 널리 사용됩니다. 👑