목차
1. Heap이란?
들어가기 전에..
- 이진 트리: 각 노드가 최대 두개의 자식노드를 가진 트리 자료구조
- 원소 추가 및 삭제의 시간복잡도 == O(log_N)
- 구현이 쉬운 편
1. Heap
-
특정한 규칙을 만족하도록 구성된 이진트리. 부모노드의 원소는 자식노드 이상(힙의 대소 관계 규칙). 이 때문에 최대 원소를 빠르게 찾을 수 있음
- 편향 트리가 나오지 않게 하기 위해 트리의 높이를 항상 일정하게 유지(트리 구조 제약)
- 힙의 모양 규칙
- 마지막 레벨을 제외한 모든 레벨에 노드가 가득 있어야
- 마지막 레벨의 노드는 가장 왼쪽부터 채워
힙 삽입: 마지막에 추가한 새 원소를 부모 노드의 원소와 비교, 자신이 클 때 까지 위치를 바꿈
힙 삭제: 마지막 노드를 지워 삭제된 노드의 위치에 삽입. 삽입된 마지막 노드는 해당 위치의 자식 노드와 원소를 비교, 자신이 더 작다면 위치를 바꿈
사용방법
힙의 모양 규칙에 의해, n개의 노드가 있을 떄 이 노드들은 arr[0]에서 arr[n-1]까지 순차적으로 대응
arr[i]의 왼쪽 자식은 arr[2*i + 1]에 대응
arr[i]의 오른쪽 자식은 arr[2*i]에 대응
arr[i]의 부모는 arr[(i-1)/2]에 대응 (나눗셈 결과는 내림)