[algorithm]heap
Heap
우선순위 큐
우선순위 큐에서 사용되는 자료구조
- 우선순위 큐
- 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 빠져나간다.
- 우선순위 큐 이용 사례
- a.네트워크 트래픽 제어
- b.운영체제의 작업 스케줄링
Heap
- 완전이진트리의 일종이다.
- 여러개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
- 힙은 일종의 반정렬상태(느슨한정렬상태)를 유지한다.
- 큰 값이 상위 레벨에 있고 작은 값이 하위레벨에 있는 정도
- 부모노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
Heap의 종류
-
최대 힙(max heap)
- 부모노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
- 부모노드 key >= 자식노드 key
-
최소 힙(min heap)
- 부모노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리
- 부모노드 key <= 자식노드 key
Heap의 구현
- 배열을 통해 구현한다.
- 부모노드와 자식노드의 관계
- 왼쪽 자식의 인덱스 = (부모의 인덱스)*2
- 오른쪽 자식의 인덱스 = (부모의 인덱스)*2+1
- 부모의 인덱스 = (자식의 인덱스)/2