힙

Tree의 형태로, Tree 중에서도 최대,최솟값을 찾아내는 연산을 빠르게 하기 위한 완전 이진 트리이다. (Complete Binary Tree )
우선 순위를 무엇에 두냐에 따라 순서가 달라지기 때문에 자료가 들어온 시간을 우선순위로 놓는다고 하면 일반적인 큐도 우선순위 큐가 될 수 있다.

✔ 최대 히프(Max Heap)

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

c++을 이용한 코드 예

✔ 최소 히프(Min Heap)

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

c++을 이용한 코드 예

✔ 힙의 구현

🔴 루트 인덱스가 0일 경우
 - 왼쪽 자식의 인덱스   = 부모 인덱스 * 2 + 1
 - 오른쪽 자식의 인덱스 = 부모 인덱스 * 2 + 2
 - 부모 인덱스 = (자식의 인덱스 - 1) / 2 

🔴 루트 인덱스가 1일 경우
 - 왼쪽 자식의 인덱스   = 부모 인덱스 * 2 
 - 오른쪽 자식의 인덱스 = 부모 인덱스 * 2 + 1
 - 부모 인덱스 = 자식의 인덱스 / 2 

  삽입 : 가장 끝에 삽입 후 부모 노드와 비교후 교체

  삭제 : 첫 번째 노드 값을 꺼낸 후 마지막 노드의 값을 첫 번째로 이동
        --> 마지막 노드 삭제 
        --> 옮긴 첫번째 노드의 값을 아래로 내려가며(child와) 비교후 교체

✔ 시간 복잡도 ( 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)

---

✔ 사용 예

• 허프만 코드

주어진 문자열을 이용하여 문자의 빈도수를 고려하여 2진수로 압축하는 알고리즘 중 하나.
최소 힙을 이용한다.

✔ 우선순위 큐

---

우선순위의 개념을 큐에 도입한 자료 구조.
일반적인 큐는 FIFO의 규칙으로 먼저 들어온것이 나가게 되나 우선순위 큐는 우선순위가 높은 순서대로 나가게 된다.