Heap
- Data structure
- 2021년 6월 3일
Tree중 하나로 최대,최솟값을 찾아내는 연산을 빠르게 하기 위한 완전 이진 트리이다. (Complete Binary Tree )
우선 순위를 무엇에 두냐에 따라 순서가 달라지기 때문에 자료가 들어온 시간을 우선순위로 놓는다고 하면 일반적인 큐도 우선순위 큐가 될 수 있다.
1. 최대 힙(Max Heap)
부모 노드의 key값이 자식 노드의 key값보다 크거나 같은 완전 이진 트리
2. 최소 힙(Min Heap)
부모 노드의 key값이 자식 노드의 key값보다 작거나 같은 완전 이진 트리
3. 구현
1) 루트 인덱스가 0일 경우
- 왼쪽 자식의 인덱스 = 부모 인덱스 * 2 + 1
- 오른쪽 자식의 인덱스 = 부모 인덱스 * 2 + 2
- 부모 인덱스 = (자식의 인덱스 - 1) / 2
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. 사용 예
1) 허프만 코드
주어진 문자열을 이용하여 문자의 빈도수를 고려하여 2진수로 압축하는 알고리즘 중 하나로 최소 힙을 이용한다.
2) 우선순위 큐
우선순위의 개념을 큐에 도입한 자료 구조로 일반적인 큐는 FIFO의 규칙으로 먼저 들어온것이 나가게 되나 우선순위 큐는 우선순위가 높은 순서대로 나가게 된다.
