Heap

Heap이란 최대값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조

 

최소힙이란?

작은 값을 항상 위에 있게하여 트리의 루트에는 가장 작은값이 오도록 함.

최소힙

최대힙이란?

큰값을 항상 위에 있게하여 트리의 루트에 가장 큰 값이 오도록 함.

최대힙

 

최소힙에 노드 삽입하기

1. 완전 이진트리에 값을 추가 하듯이 마지막 leaf에 값을 추가
2. 추가한값과 부모노드를 비교해서 자기보다 값이 작은 경우 자리 변경
3. 루트에 도착하거나 자기보다 값이 작은 부모를 만나기 전까지 반복

최소힙은 부모노드와 비교할때마다 전체 값의 절반이 사라지기 때문에 O(log n)의 시간 복잡도를 가진다

 

최소힙에서 노드 꺼내오기

1. 최소힙에 최솟값을 요청할때 루트의 값을 빼온 다음에는 마지막 하위 노드의 값을 가져와 루트에 채움
2. 이후 정렬은 자식과 비교하여 자신보다 작은 자식과 자리를 바꾸는데 2개의 값중 더 작은 값과 자리를 바꾼다.

노드 삽입과 동일하게 마지막 자식을 루트에 올린 후 값을 비교할때마다 절반씩 검사해야할 값이 사라지기 때문에
O(log n)의 시간 복잡도를 갖는다.

힙과 배열

배열 heap에서 부모노드와 자식 노드의 관계

-

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

• 왼쪽 자식의 인덱스 = (부모의 인덱스) x 2
• 오른쪽 자식의 인덱스 = (부모의 인덱스) x 2 + 1
• 부모의 인덱스 = (자식의 인덱스) / 2

Priority Queue (우선순위 큐)

Queue와는 다르게 Priority Queue는 push 연산 시 우선순위 큐 안에서 제일 우선순위가 높은 원소를 추출한다.

우선순위 큐는 보통 힙을 이용해 구현되기 때문에 최댓값을 가져오는 우선순위큐는 최대 힙이라고 할 수 있고,

최소값을 가져오는 우선순위 큐는 최소 힙이라고 할 수 있다.

 

JAVA 문법

// 최소힙
PriorityQueue<Integer> queue = new PriorityQueue<>();
// 최대힙
PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());