Heap
- 최댓값이나 최솟값을 빠르기 구하기 위해 고안된 완전이진트리를 기반으로 한 자료구조
- 루트의 값만 바로 가져오면 되기 때문에 O(1)의 시간 복잡도 만으로 바로 최대값이나 최소값을 찾을 수 있다.
- complete binary tree이면서 heap property를 만족해야한다.
- 시간복잡도 :
O(logn)
최대힙
- 최댓값이 루트노드에 온다
- max heap property : 부모는 자식보다 크거나 같다 -> max heap
- Max-Heap 에서 root 노드의 key는 무조건 해당 노드의 자식 노드들의 key보다 크거나 같다. 또한 같은 속성이 모든 sub-tree 들에게도 재귀적으로 적용된다.
최소힙
- 최솟값이 루트노드에 온다
- min heap property : 부모는 자식보다 작거나 같다 -> min heap
- root 노드의 키값이 모든 자식들의 키 보다 작거나 같다.
Heap의 표현
- 힙은 일차원 배열로 표현가능하다 -> A[1…n]
- 루트노드 A[1]
- A[i]의 부모 = A[i/2]
- A[i]의 왼쪽 자식 = A[2i]
- A[i]의 오른쪽 자식 = A[2i+1]
기본연산 : MAX-HEAPIFY
- 트리의 전체 모양은 complete binary tree
- 유일하게 루트만이 heap property를 만족하지 않는다
- 왼쪽, 오른쪽 subtree도 그 자체로 heap이다
자바에서 Heap 사용하기
java에서는 Java1.5 부터 PriorityQueue로 Heap이 구현되어 있다!
예제 문제
- 백준 최대힙
```java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer;
public class Main {
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public static void main(String[] args) {
FastReader br = new FastReader();
int num = br.nextInt();
PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o2, o1));
StringBuilder sb = new StringBuilder();
for (int i = 0; i < num; i++) {
int input = br.nextInt();
if (pq.size() == 0 && input == 0) {
sb.append("0").append("\n");
} else if (pq.size() > 0 && input == 0) {
sb.append(pq.poll()).append("\n");
} else {
pq.add(input);
}
}
System.out.println(sb);
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
} } ```
- 백준 N번째 큰 수
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o2, o1));
FastReader br = new FastReader();
int N = br.nextInt();
for (int i = 0; i < N * N; i++) {
queue.add(br.nextInt());
}
for (int j = 0; j < N-1; j++) {
queue.poll();
}
System.out.println(queue.poll());
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
}
- 프로그래머스 더맵게
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
int answer = 0;
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int i = 0; i < scoville.length; i++) {
queue.offer(scoville[i]);
}
while(queue.peek() < K) {
queue.offer(queue.poll() + queue.poll() * 2);
answer++;
if (queue.size() == 1 && queue.peek() < K) {
return -1;
}
}
return answer;
}
}
reference
JAVA로 알아보는 힙 (Heap) 자료구조
자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)
