heap(2)
-
[알고리즘] 11286. 절댓값 힙
0. 문제 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 1. 문제 이해 Heap Priority Queue Comparator 2. 제출 가. Priority Queue로 풀기 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Comparator; import java.util.PriorityQueue; import java.util.StringTokenizer; public class BO..
2024.02.18 -
[Java] Heap
1. Heap 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조. 무언가를 차곡차곡 쌓아 올린 더미 부모의 값은 항상 자식(들)의 값보다… 크거나 같은 최대 힙(Max heap) 작거나 같은 최소 힙(Min heap) 데이터의 삽입과 삭제는 모두 O(logN)이 소요. (완전 이진 트리일 때) 가. 데이터 삽입 가장 끝의 자리에 노드를 삽입한다. 그 노드와 부모 노드를 서로 비교한다. 규칙에 맞으면 그대로 두고, 그렇지 않으면 부모와 교환한다. 규칙에 맞을 때까지 반복한다. 나. 데이터 삭제 최댓값 혹은 최솟값이 저장된 루트 노드만 제거할 수 있다. 루트 노드를 제거한다. 루트 자리에 가장 마지막 노드를 삽입한다. 올라간 노드와 그의 자식..
2024.02.18