목록힙 (1)

Tori의 개발 공부

[알고리즘 / Swift] 힙 Heap

Heap 이란? 데이터에서 최댓값 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리로 우선순위 큐를 위해 만들어진 자료구조 최대힙(max heap) : 부모노드 ≥ 자식노드 최소힙(min heap) : 부모노드 ≤ 자식노드 💡 완전 이진 트리란? 이진트리 = 자식 노드가 최대 두 개인 트리 완전 이진트리 = 마지막 레벨을 제외한 모든 노드가 2개씩 채워져 있으며, 최하단 레벨 또한 좌측부터 채워져있는 노드를 의미한다. 즉 완전 이진트리는 왼쪽부터 자식 노드를 차례로 채운다. index 성질 heap은 완전 이진 트리 구조이기 때문에 노드 간 인덱스 관계를 나타낼 수 있다. → 완전 이진트리는 무조건 왼쪽부터 채워지기 때문에 채워지는 순서가 있음 = index 부모 노드 index = 자식 노드 index ..
Algorithm/개념 정리 2024. 3. 13. 18:30
이전 Prev 1 Next 다음