[JAVA/자료구조] 강의노트 5강 : 우선순위 큐 Priority Queue, 비교연산자 Comparator

 

안녕하세요!

오늘은 우선순위 큐에 대하여 알아보겠습니다.

---

!) 자료구조 Queue를 잘 모르신다면?

자료구조 Queue 설명 보러가기

---

 

1) What is a PQ?

Queue 자료구조는 선입선출의 FIFO 규칙을 따릅니다.

하지만 우선순위 큐(PQ)는 우선순위를 결정하여, 그 우선순위에 따라 dequeue operation이 실행되는 자료구조 입니다.

그 우선순위를 결정하는 요소를 우리는 'key'라고 칭하도록 하겠습니다.

따라서 자료구조 PQ에 element가 저장될 때에는 (key, value) 두 값의 페어의 형태로 저장되게 되며

이를 'entry'라 칭하겠습니다.

key값은 반드시 unique할 필요는 없고, 변할 수 있습니다.

 

2) PQ Operation

- int size() : PQ의 크기를 반환합니다.

- boolean isEmpty() : PQ가 비워져있는 상태를 판단합니다.

- insert(Object k, Object v) : k의 값의 key, v값의 value를 지닌 entry를 PQ에 enqueue합니다.

- removeMin() : 제일 작은 k 값을 지닌 entry를 dequeue합니다.

- min() : 제일 작은 k 값을 지닌 entry를 반환합니다.(삭제하지 않고 보여주기만 합니다.)

---

!) PQ Operation Example

Oepration	Output	Priority Queue
insert(5 , A)	e1{=(5,A)}	{(5,A)}
insert(9, C)	e2{=(9,c)}	{(5,A),(9,C)}
insert(3, B)	e3{={3,B)}	{(3,B),(5,A),(9,C)}
insert(7, D)	e4{=(7,D)}	{(3,B),(5,A),(7,D),(9,C)}
min()	e3	{(3,B),(5,A),(7,D),(9,C)}
removeMin()	e3	{(5,A),(7,D),(9,C)}
size()	3	{(5,A),(7,D),(9,C)}
removeMin()	e1	{(7,D),(9,C)}
removeMin()	e4	{(9,C)}
removeMin()	e2	{}

---

3) Entry

PQ에서 저장되는 key와 value의 pair입니다.

-getKey() : entry의 key값을 반환합니다.

-getValue() : entry의 value값을 반환합니다.

public interface Entry {
    public Object getKey();
    public Object getValue();
}

 

4) Comparing keys

만약, key의 값이 같다면 PQ내에서 두 entry는 동일한 우선순위를 지닙니다.

또한 key의 값이 다르다면 두 key값을 비교하여 우선순위를 산출하게 됩니다.

위 과정을 Comparator 비교연산자를 통해 수행하게 됩니다.

- compare(a, b) : a, b를 비교하여 i값을 반환합니다.

i < 0, if a <= b

i = 0, if a = b

i > 0, if a >= b

import java.util.Comparator;
 
public class IntComparator implements Comparator {
 
    public int compare(Object o1, Object o2) {
        return (int)o1 - (int)o2;
    }
}

import java.util.ArrayList;
 
public class MyPQ {
    
    private ArrayList list;
    private IntComparator cpt;
    
    MyPQ(){
        this.list = null;
        this.cpt = null;
    }
    
    MyPQ(IntComparator comp){
        this.list = new ArrayList();
        this.cpt = comp;
    }
    
    MyPQ(int initialCapacity, IntComparator comp){
        this.list = new ArrayList(initialCapacity);
        this.cpt = comp;
    }
    
    public int size() {
        return list.size();    
    }
    
    public boolean isEmpty() {
        return list.isEmpty();
    }
    
    public MyEntry insert(Object k, Object v) {
        
        MyEntry newEntry = new MyEntry(k, v);
        
        int where = 0;
        int len = list.size();
        
        for(int i=0; i<len; i++) {
            MyEntry temp = (MyEntry)list.get(i);
            if(this.cpt.compare(k, temp.getKey()) > 0) {
                where++;
            }
        }
        
        list.add(where, newEntry);
        return newEntry;
    }
    
    public MyEntry removeMin() {
        return (MyEntry)list.remove(0);
    }
    
    public MyEntry min() {
        return (MyEntry)list.get(0);
    }
}