안녕하세요!
오늘 공부한 힙 자료구조를 작성해 보겠습니다.
HEAP
힙은 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해 만든 자료 구조입니다.
힙의 종류에는 최대 힙 (max heap) , 최소 힙 (min heap) 이 있습니다.
최대 힙
최대 힙은 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리입니다.
부모 노드의 키 값은 자식 노드의 키 값보다 항상 큽니다.
그렇다면 최대 힙의 루트 노드는 트리의 최대값이 될 것입니다.
최소 힙
최소 힙은 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리입니다.
부모 노드의 키 값은 자식 노드의 키 값보다 항상 큽니다.
그렇다면 최소 힙의 루트 노드는 트리의 최소값이 될 것입니다.
힙을 분석해보자
힙에 원소를 넣기 위해서는 현재 트리의 높이(level) 만큼 부모 노드와 비교합니다.
최대 힙에 원소를 넣는다고 했을 때, 우선 트리의 리프 노드에 원소를 삽입하고 자신의 부모 노드의 값과 비교해 본인이 크다면 부모 노드와 자리를 바꾸고, 자신이 작다면 그대로 저장됩니다.
이렇게 한 노드를 힙에 삽입하거나 삭제하는데 소요되는 시간 복잡도는 O(logN) 입니다.
그렇다면, N 개의 노드를 힙에 삽입하거나 삭제하는 것은 O(NlogN) 이 될 것입니다.
힙에 원소들을 삽입한 후에는 루트 노드부터 삭제합니다.
이것을 힙정렬이라고 합니다.
최대 힙을 루트 노드부터 삭제해 반환하면 내림차순 힙정렬, 최소 힙을 루트 노드부터 삭제해 반환하면 오름차순 힙정렬입니다.
우선순위 큐
우선순위 큐(Priority Queue)는 우선순위를 가진 항목들을 저장하는 큐입니다.
일반 큐의 삭제는 FIFO 순서이지만 우선순위 큐는 우선순위가 높은 순서대로 삭제됩니다.
이 우선순위 큐를 구현하는 가장 효율적인 방법은 힙을 사용하는 것입니다.
한 노드를 삽입하거나 삭제하는데 O(logN) 이 소요되고 최대값과 최소값을 구하는 데는 O(1) 이 소요됩니다.
(이것은 완전 정렬보다 관리 비용이 적습니다.)
java.util.PriorityQueue- Heap 자료구조를 구현한 자바의 라이브러리
java.util.PriorityQueue()- 원소들의 natural ordering, 오름차순에 따라 Heap을 유지
- 모든 원소는
Comparable인터페이스를 구현해야 함
java.util.PriorityQueue(Comparator comparator)- 명시된
Comparator의 구현에 따라 원소들의 순서를 유지
- 명시된
Comparable, Comparator
값을 비교하는 두 인터페이스는 정수로 값을 비교합니다.
- 음수 : 이후에 비교한 원소가 크다.
- 0 : 두 원소의 크기가 같다.
- 양수 : 이전에 비교한 원소가 크다.
해당 인터페이스의 구현 메소드를 return o1.value - o2.value 로 구현했을 때 비교할 대상의 값이 음수와 양수가 섞인 경우는 언더플로 발생 가능성이 있습니다.
따라서 음수와 양수가 섞인 경우는 예외처리가 필요 합니다.
Comparable
java.lang.Comparable<T> 인터페이스는 객체를 비교할 때 사용됩니다.
Comparable 을 구현하는 클래스에서는 int compareTo(T other) 메소드를 반드시 오버라이딩해야 합니다.
Comparable 은 자신이랑 같은 타입과 값을 비교한 후 int의 3가지 상태 (양수, 0, 음수) 로 대소를 체크합니다.
비교할 원소에게 다른 원소와의 대소 관계를 비교하는 것이므로, 매개변수는 하나입니다.
만약, 비교할 대상이 Comparable 의 compareTo 를 구현하지 않는다면 런타임에 ClassCastException 예외가 발생합니다.
Comparator
java.lang.Comparator<T> 인터페이스도 객체를 비교할 때 사용됩니다.
Comparator 는 int compare(T o1, T o2) 메소드를 반드시 구현해야 합니다.
하지만 Comparator 는 Comparable 과는 달리 비교 대상의 두 원소가 아닌 별도의 도우미 역할입니다.
즉, 값을 비교할 원소와는 상관이 없는 제 3의 존재입니다.
정렬의 도우미 역할이므로 객체 두 개의 비교를 돕습니다.
따라서 구현할 메소드의 매개변수는 2개입니다.
매개변수간의 대소 관계를 비교한 후 int의 3가지 상태 (양수, 0, 음수) 로 대소를 체크합니다.
배열의 경우는 Comparable 을 구현할 수 없으므로 Comparator 을 사용해야 합니다.
마무리
미루고 미루던 알고리즘 개념 정리를 다시 노션에도, 블로그에도 해야겠습니다!
이번 포스팅도 읽어주셔서 감사합니다 :)
