공부하는 블로그

11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이� www.acmicpc.net 최대 힙을 구현하는 문제이다. 직접 최대 힙을 구현해서 풀어보는 방법과 우선순위 큐도 힙의 자료구조를 가지고 있으므로 자바에 이미 구현되어있는 PriorityQueue를 이용하여 푸는 방법이 있다. 공부를 위해 직접 구현해보는 방향으로 문제를 풀어보았다. import java.util.ArrayList; import java.util.Scanner; public class Main { public static class MyMaxHeap { p..

Heap ? 힙(Heap)은 부모 노드와 자식 노드 간에는 키 값의 대소관계가 존재하는 완전 이진트리이다. 대소관계는 오로지 부모 노드와 자식 노드 간에만 성립하며 형제 사이에는 대소관계가 정해지지 않는다. 부모 노드의 값이 자식 노드의 값보다 크거나 같으면 최대 힙(Max Heap), 그 반대면 최소 힙(Min Heap)이다. * 이진트리(Binary Tree) : 한 노드가 최대 두 개의 자식노드를 가지는 트리 * 완전 이진트리(Complete Binary Tree) : 노드를 삽일할 때 왼쪽부터 차례대로 삽입하는 이진 트리이다. 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안되었으며 우선순위 큐를 구현할 때 주로 사용된다. * 우선순위 큐(Priority Queue) : 우선순위가 ..