[자료구조]-Heap
힙(Heap) 정리
개념
Heap의 개념
우선순위 큐는 힙(heap)을 이용한다는데 힙에 대해서 알아보자
Heap
- 최소값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조
여기서 이진트리는 모든 노드의 최대 차수를 2로 제한한 조건입니다.
차수 : ‘한 노드의 자식노드와 연결된 개수’이다.
여기서 완전 이진 트리는
- 마지막 레벨을 제외한 모든 노드가 채워져있어야하고
- 모든 노드들이 왼쪽부터 채워져 있어야한다.
레벨 : ‘특정 깊이의 노드집합’이다.
완전 이진트리의 루트 노트는 항상 우선순위가 높은 노드다. 부모노드가 자식노드보다 우선순위만 높으면 된다. 그래서 형제 간 우선순위를 안본다.
정수나 문자의 경우는 낮은 값이 우선이다. ex) {3, 2, 6, 5} 정렬 시 {2, 3, 5, 6}이다.
요약
- Heap은 완전이진트리 형태이다.
- 우선순위 큐는 Heap 구조이다.