[JAVA] 힙과 최소 힙, 최대 힙 개념 및 구현

Recent Posts

Link

관리 메뉴

Dazzling 개발 노트

Develop/Java

dj._.dazzling 2024. 4. 23. 19:16

힙

완전 이진트리 형태의 최대, 최솟값을 빠르게 찾아내는데 유용한 자료구조

부모 노드의 key가 자식 노드의 key보다 작거나 같은 완전 이진트리

부모 노드의 key가 자식 노드의 key보다 크거나 같은 완전 이진트리

우선순위 큐인 PriorityQueue를 통해 구현할 수 있다.

최대 힙은 내림차순 정렬이어야 하므로, Collections.reverseOrder 옵션을 추가해서 사용한다.

PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());

11279번: 최대 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

'Develop/Java' Related Articles