💿 자료구조 - Heap

완전 이진 트리 기반의 자료구조 (왼쪽부터 채워지는 트리)

 

최대 힙 (Max Heap)

: 주어진 트리는 완전 이진 트리

: 모든 부모 노드는 자기 자식보다 큰 값

최소 힙 (Min Heap)

: 주어진 트리는 완전 이진 트리

: 모든 부모 노드는 자기 자식보다 작은 값

 

---

 

Up-Heap : 새로운 원소 주가

- 힙은 완전 이진 트리 기반으로, 최초 삽입 위치는 고정되어있음

- 최대 힙의 원리를 깨지 않게끔 삽입된 노드를 움직임

Down-Heap : 루트 노드 제거

- 최하단 최우측 노드를 루트 노드로 대체 (완전 이진 트리의 규칙을 깨지 않기 위해)

- 이후 위치 조정

---

 

[ Heap의 구현 ]

Index를 이용

- 힙은 완전 이진 트리이므로 트리에 노드가 추가되더라도 기존의 노드 번호는 변하지 X

- 동적배열을 사용하여 구현

 

 

코드가 너무 길어서 깃허브 보고 하시오

https://github.com/codenameVien/DataStructure/blob/main/maxHeap.ipynb

DataStructure/maxHeap.ipynb at main · codenameVien/DataStructure