Heap
Section
Tree중 하나로 최대,최솟값을 찾아내는 연산을 빠르게 하기 위한 완전 이진 트리이다. (Complete Binary Tree )
우선 순위를 무엇에 두냐에 따라 순서가 달라지기 때문에 자료가 들어온 시간을 우선순위로 놓는다고 하면 일반적인 큐도 우선순위 큐가 될 수 있다.
1. 최대 힙(Max Heap)
부모 노드의 key값이 자식 노드의 key값보다 크거나 같은 완전 이진 트리
2. 최소 히프(Min Heap)
부모 노드의 key값이 자식 노드의 key값보다 작거나 같은 완전 이진 트리
3. 구현
◾ 루트 인덱스가 0일 경우
-
왼쪽 자식의 인덱스 = 부모 인덱스 * 2 + 1
-
오른쪽 자식의 인덱스 = 부모 인덱스 * 2 + 2
-
부모 인덱스 = (자식의 인덱스 - 1) / 2
◾ 루트 인덱스가 1일 경우
-
왼쪽 자식의 인덱스 = 부모 인덱스 * 2
-
오른쪽 자식의 인덱스 = 부모 인덱스 * 2 + 1
-
부모 인덱스 = 자식의 인덱스 / 2
루트 인덱스를 0 | 1 중에 무엇으로 두냐에 따라 위와같이 구현방법이 조금 달라질 수 있다.
◾ 삽입
가장 끝에 삽입 후 부모 노드와 비교후 교체하면서 더이상 교체가 안될때까지 루트까지 올라가면 된다.
◾삭제
첫 번째 노드 값을 꺼낸 후 마지막 노드의 값을 첫 번째로 이동을 한 후,마지막 노드 삭제한다.
옮긴 첫번째 노드의 값을 아래로 내려가며(child와) 비교후 교체를 수행한다.
4. 시간 복잡도 ( Big-O )
| 자료구조 | 시간 복잡도 | |||||
|---|---|---|---|---|---|---|
| 최댓값 찾기 (Find Max) | 최댓값 추출 (Extract Max) | 키 증가 (Increase Key) | 삽입 (Insert) | 삭제 (Delete) | 합병 (Merge) | |
| 이진 힙 (Binary Heap) | O(1) | O(logn) | O(logn) | O(logn) | O(logn) | O(m+n) |
| 페어링 힙 (Pairing Heap) | O(1) | O(logn) | O(logn) | O(1) | O(logn) | O(1) |
| 이항 힙 (Binomial Heap) | O(1) | O(logn) | O(logn) | O(1) | O(logn) | O(logn) |
| 피보나치 힙 (fibonacci Heap) | O(1) | O(logn) | O(1) | O(1) | O(logn) | O(1) |
5. 사용 예
◾ 허프만 코드
주어진 문자열을 이용하여 문자의 빈도수를 고려하여 2진수로 압축하는 알고리즘 중 하나로 최소 힙을 이용한다.
◾ 우선순위 큐
우선순위의 개념을 큐에 도입한 자료 구조로 일반적인 큐는 FIFO의 규칙으로 먼저 들어온것이 나가게 되나 우선순위 큐는 우선순위가 높은 순서대로 나가게 된다.