힙(Heap)

힙(Heap)

Algorithm : 힙(Heap)

: 완전이진트리의 일종으로, 부모노드와 자식노드는 우선순위에 따라 정렬이 되어 있지만 형제 간의 순위는 정렬되어 있지 않은 반정렬 상태이다. 또한, 중복값이 허용된다.

힙의 종류

최소힙 : 부모 노드가 자식노드보다 작은 힙

최대힙 : 부모 노드가 자식노드보다 큰 힙

최소힙 알고리즘 코드

출처 : 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 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("

"); heap.delete(); } else { heap.insert(val); } } System.out.println(sb); } }

힙 참고 사이트

반응형

from http://se0r1-tae27.tistory.com/95 by ccl(A) rewrite - 2021-08-08 19:26:43