힙(heap)

힙(heap)

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

최대 힙(max heap)

• 키 값이 가장 큰 노드를 찾기위한 완전 이진 트리
• 부모 노드의 키 값 >= 자식 노드의 키 값 - 트리의 모든 노드에 성질 적용
• 루트 노드 : 키 값이 가장 큰 노드

최소 힙(min heap)

• 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
• 부모 노드의 키값 <= 자식 노드의 키 값 - 트리의 모든 노드에 성질 적용
• 루트 노드 : 키 값이 가장 작은 노드

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

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

힙의 종류에 따라 최댓값 또는 최솟값

우선순위 큐(Priority Queue)

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

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

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

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

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

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

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

우선순위 큐 특성

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

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

우선순위를 기준으로 FIFO

java.util.PirorityQueue

Heap 자료구조

원소 자체를 기준 힙 구성 - 원소 자체가 Comparable 해야한다.

비교 도우미를 기존 힙 구성 - Comparter , PirorityQueue 객체 생성시 알려줘야 한다.

힙 원소 추가/삭제시 마다 구성이 완성

최대 Heap

가장 큰 값을 기준으로 먼저 나옴

최소 Heap

가장 작은 값을 기준으로 먼저 나옴

java.util.PirorityQueue()

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

반드시 모든 원소는 Comparable 인터페이스를 구현해야 한다.

java.util.PirorityQueue(Comparator comparator)

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

힙 정렬(Heap Sort)

힙 정렬은 힙 자료구조를 이용해서 이진 트리와 유사한 방법으로 수행

정렬을 위한 2단계

1. 하나의 값을 힙에 삽입한다. (반복)
2. 힙에서 순차적(오름차순)으로 값을 하나씩 제거한다.

힙 정렬의 시간 복잡도

• N개의 노드 삽입 연산 + N개의 노드 삭제 연산
• 노드 하나의 삽입과 삭제 연산은 각각 O(logN)
• 따라서 O(NlogN)