힙(Heap)

type: Algorithm archive: false

완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조

최대 힙(max heap)

키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리

부모 노드 의 키 값 > 자식 노드의 키 값

루트 노드 : 키 값이 가장 큰 노드

최소 힙(min heap)

키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리

부모 노드의 키 값 < 자식 노드의 키 값

루트 노드 : 키 값이 가장 작은 노드

힙에서는 루트 노드의 원소만을 삭제 할 수 있다.

루트 노드의 원소를 삭제하여 반환한다.

힙의 종류에 따라 최대값 또는 최소값을 구할 수 있다.

우선순위 큐를 구현하는 가장 효율적인 방법 이 힙을 사용하는 것이다.

노드 하나의 추가 / 삭제의 시간 복잡도가 O(logN)이고 최대값 / 최소값을 O(1)에 구할 수 있다.

완전 정렬보다 관리 비용이 적다.

배열을 통해 트리 형태를 쉽게 구현할 수 있다.

부모나 자식 노드를 O(1)연산으로 쉽게 찾을 수 있다.

n 위치에 있는 노드의 자식은 2n과 2n + 1위치에 존재한다.

완전 이진트리의 특성에 의해 추가 / 삭제의 위치는 자료의 시작과 끝 인덱스로 쉽게 판단할 수 있다.

우선순위 큐의 특성

우선순위를 가진 항목들을 저장하는 큐

FIFO순서가 아니라 우선순위가 높은 순서대로 먼저 나가게 된다.

java.util.PriorityQueue

Heap 자료구조

최대 Heap - 가장 큰 값을 기준으로 먼저 나옴.

최소 Heap - 가장 작은 값을 기준으로 먼저 나옴.

java.util.PriorityQueue()

원소들의 natural Ordering에 따라 Heap 유지

따라서, 반드시 모든 원소는 Comparable 인터페이스를 구현해야 함.

java.util.PriorityQueue(Comparator comparator)

명시된 Comparator의 구현에 따라 원소들의 순서를 유지