[Java] TreeSet, PriorityQueue

트리

기본 비선형 자료구조에서 부모와 자식 규칙을 추가한 자료구조이다.

• 최상단 노드를 루트 노드, 최하단 노드를 leaf 노드라고 부른다.
• 특정 규칙으로 데이터를 부모와 자식으로 나누어 저장 함으로써 데이터의 정렬, 검색, 범위 검색 등에서 높은 성능을 보인다.
• DFS, BFS로 구현 가능하다.

이진 트리 (Binary Tree)

트리 자료구조에서 Child는 두개만 가져야 한다는 규칙을 적용한 자료구조이다.

📌 이진 검색 트리 (Binary Search Tree)

이진 트리에서 작은 값은 Left Child, 큰 값은 Right Child에 둔다는 규칙을 추가한 자료 구조이다.

• 왼쪽에 있는 노드일 수록 작은 값, 오른쪽 노드에 있는 노드일 수록 큰 값이 들어간다.
• 대소관계를 비교해서 값을 저장한다는 점에서 정렬, 검색(대소비교가 가능한 값)에 빠른 성능을 보인다.
• DFS(In-Order, Pre-Order, Post-o), BFS(Level-Order)로 구현 가능하다.

📌 TreeSet

자바에서 이진 검색 트리 자료구조를 활용하여 Set을 구현한 클래스이다.

• Set 인터페이스를 구현하였다 (중복 값 저장되지 않는다)
• 이진 검색 트리의 장점 중 데이터 검색이 빠르다는 점을 이용해서 데이터가 추가될 때 데이터의 중복을 빠르게 체크한다.
• HashSet과 달리 대소 관계로 중복을 체크하기 때문에 Comparable을 상속 받은 클래스 여야 하고, CompareTo 구현이 되어 있어야 한다. (참고 - HashSet은 equals()와 hashCode()구현이 되어 있어야한다.)

public class SetTest {

    public static void main(String[] args) {

        TreeSet<Integer> treeSet = new TreeSet<>();
        treeSet.add(10);
        treeSet.add(5);
        treeSet.add(1);
        treeSet.add(5);
        System.out.println(treeSet);
        // [1, 5, 10]

        TreeSet<MyData> treeSet2 = new TreeSet<>();
        treeSet2.add(new MyData(10));
        treeSet2.add(new MyData(5));
        treeSet2.add(new MyData(1));
        treeSet2.add(new MyData(5));
        System.out.println(treeSet2);
        // [1, 5, 10]
    }

    static class MyData implements Comparable<MyData> {
        private int value;

        public MyData(int value) {
            this.value = value;
        }

        @Override
        public int compareTo(MyData v2) {
            return value - v2.value;
        }

        @Override
        public String toString() {
            return String.valueOf(value);
        }
    }
}

• 아래와 같이 Comparator 재정의도 가능하다.

TreeSet<MyData> treeSet2 = new TreeSet<>((o1, o2) -> o1.value - o2.value);

📌 힙 (Heap)

이진 트리에서 큰 값을 Parent에 둔다(Max Heap) or 작은 값을 Parent에 둔다(Min Heap)는 규칙을 추가한 자료 구조이다.

• Max Heap은 최상단 루트 노드에 최대값이 들어간다.
• Min Heap은 최상단 루트 노드에 최솟값이 들어간다.

📌 PriorityQueue

우선순위 큐 라는 자료구조를 구현한 클래스이다. 우선순위 큐 = 힙은 아니고, 우선순위 큐는 큐에서 우선순위가 높은 데이터를 먼저 반환하는 자료구조인데, 자바에서는 이 우선순위 큐가 힙으로 구현되어 있다. 우선순위 큐라는 추상적인 개념을 구체화 한 것이 힙으로 구현된 PriorityQueue 클래스 인 것이다.

• 데이터의 정렬에 용이하다.(heap 정렬)
• 최댓값, 최솟값을 찾기 위한 목적이라면 기타 자료구조를 사용하여 정렬(O(nlogn))을 할 필요 없이 PriorityQueue(O(logn))을 이용하면 더 빠르다.

        // Min Heap
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        priorityQueue.offer(10);
        priorityQueue.offer(4);
        priorityQueue.offer(5);
        priorityQueue.offer(1);
        priorityQueue.offer(7);

        System.out.println(priorityQueue);
        // [1, 4, 5, 10, 7]

        // Max Heap
        PriorityQueue<Integer> priorityQueueMax = new PriorityQueue<>(Comparator.reverseOrder());

        priorityQueueMax.offer(10);
        priorityQueueMax.offer(4);
        priorityQueueMax.offer(5);
        priorityQueueMax.offer(1);
        priorityQueueMax.offer(7);

        System.out.println(priorityQueueMax);
        // [10, 7, 5, 1, 4]

참고

• 자바의 정석
• [JAVA] 우선순위 큐 구현하기