Heap

💫 @TODO

---

Heap
그래프의 트리 구조 중 하나
우선순위 큐 Priority Queue를 구현할 때 사용됨

우선순위 큐는 데이터 구조의 하나로서 데이터를 자유롭게 추가할 수 있음
반면, 데이터를 추출할 때는 최솟값부터 순서대로 선택됩니다
-> 추가는 자유롭게, 추출 시 작은 값부터 꺼내는 것

힙을 표현하는 트리 구조에서는 각 정점은 노드 Node라고 부름
힘에서는 각 노드에 데이터가 저장됨

노드들은 최대 두 개의 자식 노드를 가질 수 있음
트리의 모양은 데이터의 개수에 의해 정해집니다

노드는 위에서부터 채워지며, 같은 층(단)에서는 왼쪽부터 채워집니다
읽을 때도 마찬가지

힙에서는 데이터 저장 위치를 정하기 위해 자식 노드의 숫자는 반드시 부모의 숫자보다 커야한다는 규칙이 있음
따라서 가장 위 (뿌리, Root)에 가장 작은 숫자가 들어있음

데이터를 추가할 때는 이 규칙을 지키기 위해 가장 아래 층에 있는 왼쪽 노드부터 값을 채움
가장 아래 층이 모두 채워지면 새로운 층을 만들어서 가장 왼쪽에 채움

구현 (추가)

1. 일단 먼저 남은 자리에 저장
2. 부모의 숫자가 크면 조건을 만족하지 않으므로 부모와 자식을 교환 (교환이 발생하지 않을 때까지 반복)

구현 (추출)

1. 가장 위에 있는 숫자 추출 (가장 작은 수부터 나오니까), 이후 재구축
2. 가장 후미에 있는 숫자를 가장 위로 이동 (저장 순서가 위에서 아래, 왼쪽에서 오른쪽이므로)
3. (교환) 부모의 숫자가 크면 조건을 만족하지 않으므로 부모와 자식을 교환 (교환이 발생하지 않을 때까지 반복)

추가 : 재구축 O(log₂ N) (트리의 높이(log₂ N)와 비례, 아래 방향)
추출 : O(1) + 재구축 O(log₂ N) (트리의 높이(log₂ N)와 비례, 윗 방향)

다익스트라

🫧 _