우선순위 큐

 

부모 노드로 부터 2개의 노드로 갈라지는 것이 이진트리 구조

• 트리가 이진구조로 모두 채워져있다면 포화 이진트리
• 트리가 꽉채워져있지 않지만 이진구조라면 완전 이진트리
• 트리가 이진구조가 되어있지 않다면 불완전 이진트리

순회방법

•  중간에 루트 노드를 거친다면 중위 순회
•  맨 처음 루트 노드를 거친다면 전위 순회
•  마지막에 루트 노드를 거친다면 후위 순회

1. 배열로 우선순위 큐를 만들 경우 추가 삭제시 인덱스를 밀거나 당겨야하고 요소 추가시 마지막 노드 부터 우선순위에 따라 모든 인덱스를 순회할 수 있다.
2. 연결리스트로 우선순위 큐를 만들 경우 요소 추가시 마지막 노드 부터 우선순위에 따라 모든 인덱스를 순회할 수도 있다.

그렇기에 보통 우선순위 큐는 Heap 으로 한다.

 

MaxHeap 은 내림 차순으로 이진트리 구조를 만들며 MinHeap은 오름 차순으로 이진트리 구조를 만든다.

---

• 요소 추가시 요소는 트리의 최하 레벨( 층을 의미함 ) 의 오른쪽에 위치하고 부모노드와의 순회를 통해 순서를 변경한다.
• 요소 삭제는 루트노드의 삭제를 의미한다. ( 우선순위가 가장 높은 것이 루트 노드에 있으므로 ) 루트 노드 삭제시 최하 레벨의 오른쪽 노드의 값이 루트노드로 이동하여 자식노드와 순회하며 순서를 변경한다.

peak() 는 스텍과 동일, poll() 은 pop() 과 동일 , add() 나 offer() 로 값을 추가한다. 

 

우선순위를 정의하는 방법은 Comparator 를 재정의 하여 생성자에 추가하는 것이다.

public class 우선순위큐 {
	
	/**
	 * 일반 큐와 다르게 우선순위 큐는 프로그래머가 정의한 우선 순위에 따라 나오는 순서가 결정난다.
	 * 구현은 배열, 린크드리스트, 힙으로한다.
	 * 배열은 우선순위 검색을 위해 모든 노드를 다 탐색하고 삽입이나 삭제시 모든 인덱스를 당기거나 밀어야만한다.
	 * 린크드 리스트는 우선 순위 검색을 위해 모든 노드를 다 탐색할 수 있다.
	 * 
	 * 그렇기에 우선순위 큐는 Heap 을 이용해서 하는 것이 일반적이다. MinHeap은 가장 작은 순으로 MaxHeap 은 가장 높은 순으로 
	 * 우선순위가 결정된다.
	 * 
	 * 힙에 데이터 추가시 마지막 노드의 가장 오른쪽에 데이터를 저장하며 부모노드와의 우선순위에 따라 노드 변경을 반복한다.
	 * @param args
	 */
	public static void main(String[] args) {
		PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>();
		
		priorityQueue.add(4); // 추가한다.
		priorityQueue.offer(2); // 추가한다.
		priorityQueue.offer(3); //추가한다.
		priorityQueue.add(1); // 추가한다. 내부적으로는 최하레벨 노드에서 루트노트까지 순서변경이 일어나고 있다.
		Integer poll = priorityQueue.poll();// 꺼낸다.
		System.out.println(priorityQueue.size());//3
		System.out.println(poll);//기본적으로 숫자는 작은 것은 우선순위로 둔다.
		
		/// 만약 우선순위를 변경하고 싶다면 Collections.reverseOrder 를 쓰면 된다.
		PriorityQueue<Integer> reverseQueue = new PriorityQueue<Integer>(Collections.reverseOrder());
		
		reverseQueue.add(1);//내부적으로는 최하 레벨 노드부터 부모노드 사이에서 비교하며 우선순위에따라 변하고 있다.
		reverseQueue.add(2);
		reverseQueue.offer(3);
		reverseQueue.add(10);
		
		poll = reverseQueue.peek();//살짝 보기만한다.
		System.out.println(reverseQueue.size());//4
		System.out.println(poll); // 우선순위에따라 역정렬 되었다.
	}

}