: 완전이진트리의 일종으로, 부모노드와 자식노드는 우선순위에 따라 정렬이 되어 있지만 형제 간의 순위는 정렬되어 있지 않은 반정렬 상태이다. 또한, 중복값이 허용된다.
힙의 종류
- 최소힙 : 부모 노드가 자식노드보다 작은 힙
- 최대힙 : 부모 노드가 자식노드보다 큰 힙
최소힙 알고리즘 코드
출처 : https://www.acmicpc.net/problem/1927
import java.util.ArrayList;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static class minHeap {
private ArrayList<Integer> heap;
public minHeap() {
heap = new ArrayList<>();
heap.add(0);
}
public int getRoot() {
if(heap.size() - 1 < 1) {
return 0;
}
return heap.get(1);
}
public void insert(int val) {
heap.add(val);
int p = heap.size() - 1;
while(ptr > 1 && heap.get(ptr/2) > heap.get(ptr)) {
// 자식노드보다 부모노드의 값이 크다면 값을 swap
int tmp = heap.get(ptr/2);
heap.set(ptr/2, heap.get(ptr));
heap.set(ptr, tmp);
ptr = ptr/2;
}
}
public void delete() {
if(heap.size() - 1 < 1) {
return ;
}
int item = heap.get(1);
heap.set(1, heap.get(heap.size() - 1));
heap.remove(heap.size() - 1);
int pos = 1;
while(pos * 2 < heap.size()) {
int min = heap.get(pos * 2);
int minPos = pos * 2;
if((pos * 2 + 1) < heap.size()
&& min > heap.get(pos * 2 + 1)) {
min = heap.get(pos * 2 + 1);
minPos = pos * 2 + 1;
}
if(heap.get(pos) < min) break;
int tmp = heap.get(pos);
heap.set(pos, heap.get(minPos));
heap.set(minPos, tmp);
pos = minPos;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
minHeap heap = new minHeap();
StringBuilder sb = new StringBuilder();
while(N --> 0) {
int val = Integer.parseInt(br.readLine());
if(val == 0) {
sb.append(heap.getRoot()).append("\n");
heap.delete();
} else {
heap.insert(val);
}
}
System.out.println(sb);
}
}
힙 참고 사이트
반응형
'Programando > Algorithm' 카테고리의 다른 글
최단경로 / 다익스트라(Dijkstra) (0) | 2021.09.24 |
---|---|
그래프의 탐색_DFS (0) | 2021.07.19 |
그래프의 탐색_BFS (0) | 2021.07.14 |
그래프(Graph) (0) | 2021.07.11 |
덱과 JAVA Deque 클래스 (0) | 2021.06.18 |