우선순위 큐(Priority Queue), 트라이(Trie)

우선순위 큐(Priority Queue)

우선순위 큐는(Priority Queue)는 데이터를 우선순위에 따라 저장하고 관리하는 자료구조이다. 보통 힙(Heap) 자료구조를 이용하여 구현한다. 

 

우선순위 큐는 힙(Heap) 자료구조를 이용하여 구현할 수 있으며, 힙은 최대힙(Max Heap)과 최소힙(Min Heap)으로 구분된다. 최대힙은 부모 노드가 자식 노드보다 항상 큰 값을 가지고, 최소힙은 부모 노드가 자식보다 항삭 작은 값을 가진다. 이러한 특성 덕분에 우선순위 큐는 최대값(최소값)을 빠르게 찾을 수 있다. 

힙은 부모노드와 자식노드 간의 우선순위를 비교하여 부모노드가 항상 자식노드보다 우선 순위가 높은 완전이진트리 형태의 자료구조이다. 이를 이용하여 우선순위 큐를 구현할 경우, 최상위 우선순위를 가지는 데이터(루트노드)를 상수시간 O(1)로 추출 할 수 있다. 

 

구현

우선순위 큐의 경우 배열, 연결 리스트 그리고 힙으로 구현이 가능하며 각각의 자료구조 마다 걸리는 시간 복잡도는 아래와 같다. 

	Enqueue	Dequeue
정렬된 배열	O(N)	O(1)
정렬된 연결 리스트	O(N)	O(1)
힙	O(logN)	O(logN)

---

자바 PriorityQueue 클래스

자바에서는 기본적으로 PriorityQueue 클래스를 제공한다. 제공 하는 클래스를 사용 할 시 기본적으로 값이 작은 것을 우선으로 정렬 해준다. 

 

선언 및 초기화

위에서 설명 하였듯이 기본값으로 사용시 오름차순으로 정렬이 되며, 반대로 내림차순으로 설정하려면 Collections클래스 함수를 이용하여 바꿀 수 있다. 

PriorityQueue<Integer> pq = new PriorityQueue<>(); // 오름차순
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); // 내림차순

 

객체 내 멤버변수로 정렬

일반 숫자를 자려구조에 추가를 하면 자동으로 정렬이 이루어진다. 하지만 클래스 내에 있는 멤버변수를 기준으로 정렬을 하려고 하면 정렬기준이 없기 때문에 예외가 발생한다. 이러한 문제점을 해결하려면 타입으로 지정되는 클래스에서 Comparable 인터페이스를 구현해주면 된다. 

class Product implements Comparable<Product> {
	String name;
    int amount;
    
    @Override
    public int compareTo(Product p) {
    // 1 : 변경 x
    // -1 : 변경 o
    	return this.amount >= p.amount ? 1 : -1 ; // 내림차순 
    }
}

class static Main {
	
    public static void main(String[] args){
    	PriorityQueue<Product> pq = new PriorityQueue<>((Product p1, Product p2) -> p1.amount >= p2.amount ? 1 : -1);
    }
}

 

문자를 기준으로 정렬하는 방법

class static Main {
	
    public static void main(String[] args){
    	PriorityQueue<Product> pq = new PriorityQueue<>((Product p1, Product p2) -> p1.name.compareTo(p2.name));
    }
}

---

트라이(Trie)

트라이는(Trie)는 문자열의 집합을 표현하는 트리 자료구조이다. 원하는 원소를 찾기 위해 자주 이용되는 이진 검색 트리 등에서는 원소를 찾는데 O(logN)의 시간이 걸린다. 추가로 입력된 내용이 문자열인 경우 두 문자열을 비교하기 위해서는 문자열의 길이만큼 시간이 걸리기 때문에 O(M logN)의 시간이 걸리게 된다. 이러한 단점을 해결한 자료구조가 트라이이다. 

 

트라이(Trie) 구조

다음 그림은 문자열 집합{"rebro", "replay", "hi", "high", "algo"}를 트라이로 구현한 것이다. 

https://rebro.kr/86

트라이는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리이다. 한 문자열에서 다음에 나오는 문자가 현재 문자의 자식 노드가 되고, 빨간색으로 나타낸 노드는 문자열의 끝을 의미한다. 

 

장단점

트라이의 장점은 문자열을 빠르게 찾을 수 있다는 것이다. 문자열을 집합에 추가하는 경우에도 문자열의 길이만큼 노드를 따라가거나, 추가하면 되기 때문에 문자열의 추가와 탐색 모두 O(M)만에 가능하다 .

 

트라이의 단점은 필요한 메모리의 크기가 너무 크다는 것이다. 문자열이 모두 영소문자로 이루어져 있다고 하여도, 자식 노드를 가리키는 26개의 포인터를 저장해야 한다. 최악의 경우에는 O(포인터 크기 * 포인터 배열 개수 * 총노드의 개수)가 된다.