[알고리즘] 우선순위

* 우선순위 큐(Priority Queue)

: 일반적인 큐는 먼저 들어간 데이터가 먼저 나오는데, 우선순위큐는 우순순위가 가장 높은 데이터가 먼저 나온다.

 

* 우선순위 큐를 구현하는 방법 3가지

1. 배열을 기반으로 구현 : 배열은 삽입, 삭제하는 과정에서 데이터를 한 칸씩 옮겨야 한다는 단점이 있음

2. 연결리스트를 기반으로 구현 : 삽입의 위치를 찾기 위해 처음부터 우선순위를 비교해야 한다.

3. 힙을 이용하여 구현

주로 힙을 이용하여 구현한다.

 

* 우선순위 큐 저장

 

 : 숫자가 작을수록 우선순위가 높다.

 

 

 

 

 

 

 

 

 

: 새로운 데이터 '3'을 추가한다. 추가할 때는 가장 마지막 위치에 추가한다. 그리고 부모 노드와 우선순위를 비교하면서 위치를 바꿔준다.

 

 

 

: '3'의 부모인 '8'과 비교하였을 때 '3'이 우선순위가 크기 때문에 '8'과 자리를 바꿔준다.

 

 

 

 

 

 

: '8'과 자리를 바꾼 '3'의 부모는 '4'가 된다. '4'와 우선순위를 비교하였을 때 '3'이 우선순위가 크기 때문에 자리를 바꿔준다.

 

 

 

 

 

 

 

: 자신의 자리를 찾을 때 까지 반복한다.

 

 

 

 

 

 

 

 

 

 

: 이때는 '1'이 '3'보다 우선순위가 크기 때문에 바꾸지 않는다.

 

 

 

 

 

 

 

 

 

 

* 우선순위 큐 삭제

 

: 가장 우선순위가 높은 것은 루트에 있기 때문에 삭제는 어렵지 않다.

: 루트에 있는 '1'을 삭제한다. 

 

 

 

 

 

 

 

 

: 루트를 채워주기 위해서 마지막 노드를 루트 노드의 자리로 옮긴 뒤 자식 노드와 비교하여 자리를 찾는다.

 

: 마지막 노드인 '8'을 루트자리로 옮긴다.

 

 

 

 

 

 

 

 

: 자식 노드 '3'과 비교하였을 때 '3'이 우선순위가 높기 때문에 자리를 바꾼다.

 

 

 

 

 

 

 

 

 

 

: 자식 노드 '4'와 비교하였을 때 '4'가 우선순위가 높기 때문에 자리를 바꾼다.

 

: 위 와같은 방법으로 자기 자리를 찾아간다.

 

 

 

 

 

 

 

 

 

* 예제

Student 클래스

- 이름, 점수를 속성으로 가지고 있고, 점수가 높은 사람을 우선순위가 높다고 가정한다.

- Comparable의 compareTo를 구현한다. 객체를 비교할 때 점수값을 기준으로 비교하여 우선순위가 결정된다.

  아래의 예제는 점수가 높을 수록 우선순위가 높게 구현한 것이다.

    static class Student implements Comparable<Student> {
        String name;
        int score;
 
        public Student(String name, int score) {
            this.name = name;
            this.score = score;
        }
 
        @Override //점수 높은 것이 우선순위
        public int compareTo(Student target) {
            return this.score <= target.score ? 1 : - 1;
        }
 
        @Override
        public String toString() {
            return "이름 : " + name + ", 나이 : " + score;
        }
    }
 

 
import java.util.PriorityQueue;
 
public class 우선순위큐 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        PriorityQueue<Student> q = new PriorityQueue<Student>();
        q.add(new Student("A", 10));
        q.add(new Student("B", 100));
        q.add(new Student("C", 96));
        q.add(new Student("D", 17));
        q.add(new Student("E", 53));
        q.add(new Student("F", 80));
     
        // 높은 순으로 학생들 목록을 출력
        while (!q.isEmpty())
            System.out.println(q.poll());
        }
 
}