우선순위큐

2021년 09월 08일 TIL - Heap (Java)

Heap 우선 순위 큐를 하다가 Heap 구조를 사용한다는 것을 보았는데 Heap 자료구조란 무엇일까? 힙은 일종의 BinaryTree 이며 수의 집합에서 가장 작은 수나 가장 큰 수만을 자주 꺼내올 때 유용한 자료구조 가장 큰 / 작은 수 가져올때 시간 복잡도 : O(log N) 예: 최소 힙 구현 규칙이 있다. 루트는 가장 작은 값이여야 함. 자식은 자신보다 크기만 하면됨. 완전 이진 트리의 규칙을 그대로 적용 힙을 배열 형태로 구현 왼쪽 자식은 (자신의 인덱스 * 2) 오른쪽 자식은 (자신의 인덱스 * 2 + 1) 자신의 부모는 (자신의 인덱스 / 2) Heap 정의 public class Heap { public static final int MAX_N = 10001; public int[] ar..