- 힙은 이진 트리 기반이지만 이진 탐색 트리와는 다르며, 최대 힙과 최소 힙 두 종류가 존재한다. 🌳
- 최소 힙은 루트 노드에 가장 작은 값이 위치하며, 아래로 갈수록 값이 커지는 구조를 가진다. 👶
- 힙은 완전 이진 트리 구조를 유지하며, 마지막 레벨은 왼쪽부터 채워진다. 🧱
- 노드 추가 시, 완전 이진 트리 조건을 만족하는 위치에 추가 후 부모 노드와 값을 비교하여 위치를 조정한다. 🔄
build_heap기능은 정렬되지 않은 요소들을 힙에 넣은 후 힙 속성을 만족하도록 재배열한다. 🏗️- 루트 노드 제거 후, 힙의 마지막 노드를 루트로 이동시키고
heapify_down을 통해 힙 속성을 유지한다. 🗑️ - 힙은 우선순위 큐 구현에 널리 사용되며, 값의 크기를 기준으로 요소들을 꺼낼 수 있다. 🥇
- 힙은 내부적으로 인덱스가 있는 리스트를 사용하여 구현되며, 트리 형태로 시각화할 수 있다. 🔢
heapify_up메소드는 새로운 값이 추가되었을 때 적절한 위치까지 밀어 올리는 기능을 한다. ⬆️heapify_down메소드는 루트 노드 제거 후 큰 값을 아래로 밀어내려 힙 속성을 유지하는 기능을 한다. ⬇️
Recommanded Videos
