Java - heap(힙) & Priority Queue(우선 순위 큐)

◎힙(heap)이란 
최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 한 자료구조

---

- 포화 이진 트리(perfect binary tree)

모든 내부 노드가 두 개의 자식 노드를 가지며 모든 잎 노드가 동일한 레벨을 가지는 트리

포화 이진 트리

- 완전 이진 트리(complete binary tree)

마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드는 왼쪽부터 채워진 트리

완전 이진 트리, 노드개수: 4

위의 완전 이진트리에서 노드를 1개 추가하면, 노드가 왼쪽부터 채워져야 하므로 아래의 그림과 같아진다.

완전 이진 트리, 노드개수: 5

---

◎힙(heap)의 특징과 종류

-언제나 느슨한 정렬 상태를 유지한다. 

-최대힙(max heap):

부모 노드의 키 값이 자식 노드의 키 값보다 언제나 크거나 같은 완전 이진트리

-최소 힙(min heap):

부모 노드의 키 값이 자식 노드의 키 값보다 언제나 작거나 같은 완전 이진트리

---

◎배열을 이용한 힙(heap) 구현 및 주요 메서드

 

배열의 index 0을 사용하지 않는 heap 구현

- 배열의 인덱스는 노드의 위치를 나타내 준다. (ex. 3번 인덱스는 언제나 루트 노드의 rightchild를 가리킨다). 

 

 

1. 인덱스 찾기

- 배열의 index 0을 사용하지 않는 heap인 경우 아래의 수식을 언제나 만족한다

왼쪽 자식의 인덱스 = (부모의 인덱스) *2

오른쪽 자식의 인덱스 = (부모의 인덱스) *2 +1

부모의 인덱스 = (자식의 인덱스)/2

 

- 배열의  index 0을 사용하는 heap인 경우 아래의 수식을 언제나 만족한다

왼쪽 자식의 인덱스 = (부모의 인덱스 +1) *2 -1

오른쪽 자식의 인덱스 = (부모의 인덱스 +1) *2

부모의 인덱스 = (자식의 인덱스 +1) /2 -1 (자식의 인덱스가 0이라면, 루트 노드의 부모는 없다.)

 

2. 데이터 삽입

 

ex. 최대 힙

   1. 힙의 제일 마지막에 새로운 요소를 삽입한다.

   2. 부모 노드가 삽입한 노드보다 작으면 서로 교환한다

   3. 부모노드가 삽입한 노드보다 크거나 같을 때 또는 삽입한 노드가 루트 노드일 때까지 교환을 반복한다

 

3. 데이터 삭제

 

ex. 최대 힙

출처: https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

   1. 최댓값인 루트 노드를 삭제한다.

   2. 맨 마지막 노드(A)를 루트 노드에 집어넣는다

   3. A와 자식 노드들과 비교한다.

   (ex. A의 값이 3 , 왼쪽 자식 노드의 값이 5, 오른쪽 자식 노드의 값이 7이면, 부모 노드가 자식 노드보다 작고, 7이 5보     다 크므로 오른쪽 자식 노드와 교환한다)

   4. 부모 노드가 자식 노드들보다 클 때 또는 리프 노드에 도착할 때까지 반복한다

 

4. isEmpty

루트 노드가 없다면, 그 힙은 비어있는 힙이다.

 

- 구현 (배열 대신 사이즈 조절이 쉬운 ArrayList로 구현하였다, index 0을 사용한 최소 힙을 구현하였다.)

 

package SortAlgorithm;

import java.util.ArrayList;
import java.util.Collections;

public class heap {

	private ArrayList<Integer> heaparray;
	
	heap(){
		 heaparray = new ArrayList<>();
	}	
	
	//부모 노드 인덱스 찾기
	private int getparents(int idx) { 
		
		if(idx==0){ //루트 노드의 부모는 없음
			return -1;
		}
		
		int index =idx+1;
		// 부모 노드 = (자식 노드+1) /2 -1
		return index/2 -1;
	}
	
	//왼쪽 자식 노드 인덱스 찾기
	private int getleftchild(int idx) {
		
		
		int index =idx+1;
		//왼쪽 자식 =  (부모+1)* 2 -1
		if(index*2 -1>= heaparray.size()-1) {
			return -1; //자식이 없으면 -1 반환
		}else {
			return index*2 -1;
		}
	}
	
	//오른쪽 자식 노드 인덱스 찾기
	private int getrightchild(int idx) {
		
		int index =idx+1;
		//오른쪽 자식 =  (부모+1)* 2
		if(index*2 >= heaparray.size()-1) {
			return -1; //자식이 없으면 -1 반환
		}else {
			return index*2;
		}
	}
	
	//heap 삽입
	void add(int num) {
		heaparray.add(num); //우선 맨끝에 삽입
		
		int me = heaparray.size()-1;
		int parents = this.getparents(me);
		
		//heap 다시 정렬
		//부모가 없을 때까지 반복	
		while(parents != -1 ) {		
			if(heaparray.get(me)<heaparray.get(parents)) { //부모보다 내가 작으면 부모와 나를 바꿈
				Collections.swap(heaparray, me, parents);
			}else {
				break;
			}
			
			me = parents;
			parents = this.getparents(me);
		}
	}
	
	//heap 삭제
	int delete() {
		//맨 앞의 원소를 맨뒤의 원소와 바꾸고 삭제
		Collections.swap(heaparray, 0, heaparray.size()-1);
		int delete = heaparray.remove(heaparray.size()-1); //삭제된 원소는 가장 작은 값임
		
		int me = 0;
		int leftchild = this.getleftchild(me);
		int rightchild = this.getrightchild(me);
		
		/*자식이 leftchild부터 채워지므로, leftchild가 없는 경우에는 rightchild도 없지만
		 * rightchild가 없는 경우에도 leftchild는 있을 수 있다
		 */
		
		//heap 다시 정렬
		//leftchild가 없을 경우 (모든 자식이 없을 경우)에만 종료
		while(leftchild != -1) {
			// rightchild가 있고, 내가 자식보다 크고, rightchild가 자식들 중에 가장 작은 값일 경우에만 
			// rightchild와 me 교환
			if(rightchild != -1 && heaparray.get(me) >heaparray.get(rightchild) 
					&& heaparray.get(leftchild) > heaparray.get(rightchild)){
				Collections.swap(heaparray, me, rightchild);
				me = rightchild;
			}
			// 내가 자식보다 크고, leftchild가 자식들중에 가장 작은 값인 경우에만
			// leftchild와 me 교환
			else if(heaparray.get(me) >heaparray.get(leftchild)) {
				
				Collections.swap(heaparray, me, leftchild);
				me = leftchild;
			}else {
				break;
			}
			
			leftchild = this.getleftchild(me);
			rightchild = this.getrightchild(me);
			
		}
		
		return delete;
	}
	
	//isEmpty
	boolean isEmpty() {
		if(heaparray.size()==0) {
			return true;
		}else {
			return false;
		}
		
	}
}

---

◎우선순위 큐(Priority Queue)이란 

힙을 이용해 구현된 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조

---

◎우선 순위 큐(Priority Queue)의 특징

1.  힙 자료구조를 이용해 구성되어있으므로, 삽입/삭제 시간 복잡도는 O(logN).

2.  큐의 들어가는 데이터는 비교 가능한 기준이 있어야 한다.

 

※ 힙을 사용하지 않고 구현한 우선순위 큐:

ex. 배열과 연결 리스트를 사용하면, 삽입/삭제하는 과정 중에 모든 원소를 탐색해야 하는 최악의 경우가 나올 수 있으므로, 시간 복잡도가 O(N)이다.

---

◎우선순위 큐(Priority Queue) 선언/추가/삭제/참조

import java.util.PriorityQueue; // import

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(); // 선언

priorityQueue.add(1); // 1추가
priorityQueue.offer(3); // 3추가

priorityQueue.poll(); // 우선순위가 가장 높은 값 삭제&반환
priorityQueue.remove();  // 우선순위가 가장 높은 값 삭제&반환

priorityQueue.peek();  // 우선순위가 가장 높은 값 참조(삭제x)

priorityQueue.clear(); // 우선순위 큐 초기화

---

◎우선 순위 큐(Priority Queue) 비교 기준

일반적으로 String이나 int는 사전식 정렬, 최솟값 순 정렬이라는 비교 기준을 가지고 있기에, 우선순위 큐를 생성할 때 비교 기준을 넣어주지 않아도 알아서 정렬이 된다.

하지만, custom적으로 만든 class 또는 정렬 기준을 정해줘야 하는 경우 비교 기준을 우선순위 큐 생성 시에 명시해주어야 한다.

 

- class에 Comparable을 implement / 우선순위 큐에 Comparator를 명시하기 

import java.util.Comparator;
import java.util.PriorityQueue;

public class car implements Comparable<car>{
    String name; // 차 이름
    int mileage; //주행거리
    int year; // 제조년

    public car(String name, int mileage, int year) {
        this.name = name;
        this.mileage = mileage;
        this.year = year;
    }
    
    

	@Override
	// 주행거리 기준으로 비교
	public int compareTo(car target) {
		return this.mileage - target.mileage;
	}
	
    @Override
    public String toString() {
        return "이름 : " + name + ", 주행거리 : " + mileage + ", 연식: " + year;
    }
	
	public static void main(String[] args) {
		
		 System.out.println("주행거리 기준:");
		 
		//class 내부에 구현된 compareTo를 기준으로 정렬
		PriorityQueue<car> priorityQueue = new PriorityQueue<>();
		
		priorityQueue.add(new car("A",10,2015));
		priorityQueue.add(new car("B",20,2015));
		priorityQueue.add(new car("C",5,2012));
		priorityQueue.add(new car("D",35,2010));
		priorityQueue.add(new car("E",0,2017));
		priorityQueue.add(new car("F",105,2025));
		
		while (!priorityQueue.isEmpty())
	        System.out.println(priorityQueue.poll());
		
		 System.out.println("");
		 System.out.println("연식 기준:");
		 
		priorityQueue  = new PriorityQueue<>(new Comparator<car>() {

			@Override
			//연식 기준으로 비교
			public int compare(car a, car b) {
				return a.year - b.year;
			}
			
		});
		
		priorityQueue.add(new car("A",10,2015));
		priorityQueue.add(new car("B",20,2015));
		priorityQueue.add(new car("C",5,2012));
		priorityQueue.add(new car("D",35,2010));
		priorityQueue.add(new car("E",0,2017));
		priorityQueue.add(new car("F",105,2025));
		
		while (!priorityQueue.isEmpty())
	        System.out.println(priorityQueue.poll());
	}
}

 

실행결과:

주행거리 기준:
이름 : E, 주행거리 : 0, 연식: 2017
이름 : C, 주행거리 : 5, 연식: 2012
이름 : A, 주행거리 : 10, 연식: 2015
이름 : B, 주행거리 : 20, 연식: 2015
이름 : D, 주행거리 : 35, 연식: 2010
이름 : F, 주행거리 : 105, 연식: 2025

연식 기준:
이름 : D, 주행거리 : 35, 연식: 2010
이름 : C, 주행거리 : 5, 연식: 2012
이름 : B, 주행거리 : 20, 연식: 2015
이름 : A, 주행거리 : 10, 연식: 2015
이름 : E, 주행거리 : 0, 연식: 2017
이름 : F, 주행거리 : 105, 연식: 2025

 

주행거리 기준으로 정렬한 것이 class에 Comparable을 implement 하여 class 내부에 비교 기준을 적어준 것이고.

연식 기준으로 정렬한 것이 PriorityQueue를 생성할 때 비교 기준을 Comparator 생성을 통해 적어준 것이다