Heap

Tree중 하나로 최대,최솟값을 찾아내는 연산을 빠르게 하기 위한 완전 이진 트리이다. (Complete Binary Tree )

우선 순위를 무엇에 두냐에 따라 순서가 달라지기 때문에 자료가 들어온 시간을 우선순위로 놓는다고 하면 일반적인 큐도 우선순위 큐가 될 수 있다.


1. 최대 힙(Max Heap)

부모 노드의 key값이 자식 노드의 key값보다 크거나 같은 완전 이진 트리

c++을 이용한 코드 예



2. 최소 히프(Min Heap)

부모 노드의 key값이 자식 노드의 key값보다 작거나 같은 완전 이진 트리

c++을 이용한 코드 예



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의 규칙으로 먼저 들어온것이 나가게 되나 우선순위 큐는 우선순위가 높은 순서대로 나가게 된다.