[Java] TreeMap과 TreeSet (feat. 이중우선순위큐)

이중 우선순위큐를 구현하기 위해 TreeMap에 대해 알아보자
이를 기반으로 둔 TreeSet도 함께 알아보겠다.

이중우선순위큐 스펙

1. 원소 삽입
2. 최대값 삭제
3. 최소값 삭제

• 위 기능을 가진 큐가 이중우선순위큐다.

구현방법

1. TreeMap을 사용
2. 두 개의 PriorityQueue를 사용(최소힙과 최대힙)

TreeMap이란?

• Red-Black Tree기반의 Map을 구현한 클래스다.
• 키 값을 기준으로 오름차순 정렬된 트리다.
• 선언시에 compartor를 통해 정렬 기준을 정할 수 있다.

TreeMap의 매소드

• Map을 구현하는 추상클래스인 AbstractMap을 구현하는 클래스로 Map의 매소드는 모두 사용 가능하다.

• NavigableMap을 구현하기에 아래 매소드를 사용 가능하다. (쓸만한 몇개만 가져옴)

  • 리턴타입은 Map.Entry<k,v>타입을 사용해야한다.

  1. firstEntry()
  2. lastEntry()
  3. pollFirstEntry()
  4. pollLastEntry()

• 기본 정렬에서 최소값 최대값을 조회하는 매소드는 다음과 같다.

  • 리턴타입은 key의 타입이다.

  1. firstKey(): 최소
  2. lastKey(): 최대

TreeMap의 시간복잡도

• 삽입, 삭제, 조회: O(logn)
• 조회에는 최대값, 최소값 조회도 포함이다.

TreeSet

• 트리맵을 기반으로 정렬된 집합이다.

TreeSet의 매소드

• Set을 구현하는 추상클래스인 AbstractSet을 구현하는 클래스로 Set의 매소드는 모두 사용 가능하다.

• NavigableSet을 구현하기에 아래 매소드를 사용 가능하다. (쓸만한 몇개만 가져옴)

  • 리턴타입은 원소 타입인 E 타입이다.
  • 최소값 또는 최대값을 poll

    1. pollFirst(): 최소
    2. pollLast(): 최대

• 단순 조회용 매소드로 아래 매소드를 사용할 수 있다.

  • 리턴타입은 원소 타입인 E 타입이다.

    1. first()
    2. last()

결론

• TreeMap의 매소드를 사용하여 이중우선순위큐를 구현할 수 있다.
• 만약 우선순위큐를 두 개 사용한다면 두 큐의 동기화에 비용이 들며 TreeMap 하나로 간단히 구현할 수 있기에 TreeMap으로 구현하기를 권장한다.