힙

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(m+n)

페어링 힙 (Pairing Heap)

O(1)

O(logn)

O(1)

O(logn)

O(1)

이항 힙 (Binomial Heap)

O(1)

O(logn)

O(1)

O(logn)

피보나치 힙 (fibonacci Heap)

O(1)

O(logn)

O(1)

O(logn)

O(1)

✔ 사용 예

허프만 코드

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

✔ 우선순위 큐

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

Previous그래프 NextRed Black Tree

Last updated 3 years ago