λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°
πŸŽ› Others.../- 자료ꡬ쑰 & μ•Œκ³ λ¦¬μ¦˜

[자료 ꡬ쑰] PriorityQueue μ»¬λ ‰μ…˜μ„ μ΄μš©ν•œ μžλ°” μš°μ„ μˆœμœ„ 큐 :: Java Priority Queue implementing by PriorityQueue Class

by Wonit 2020. 6. 25.

μš°λ¦¬κ°€ μ§€λ‚œμ‹œκ°„μ— Heap을 λ°°μ› λŠ”λ°, 사싀 Heap은 이 Priority Queue, μš°μ„ μˆœμœ„ 큐λ₯Ό μœ„ν•΄μ„œ κ³ μ•ˆλœ 자료ꡬ쑰라고 해도 과언이 μ•„λ‹ˆλ‹€.

μš°μ„ μˆœμœ„ 큐에 λŒ€ν•΄μ„œ μ§€κΈˆλΆ€ν„° μ•Œμ•„κ°€λ³΄μž.

μš°μ„ μˆœμœ„ 큐

μš°μ„ μˆœμœ„ νλŠ” 말 κ·ΈλŒ€λ‘œ μš°μ„ μˆœμœ„(Priority) κ°€ μ‘΄μž¬ν•˜λŠ” 큐 이닀.

 

예λ₯Όλ“€μ–΄ μš°λ¦¬κ°€ 학생듀이 μžˆμ„ λ•Œ, λ‚˜μ΄ 순으둜 학생듀을 μ­‰ μ„Έμš΄λ‹€λ©΄ λ‚˜μ΄κ°€ μš°μ„ μˆœμœ„κ°€ λ˜μ–΄ λ‚˜μ΄κ°€ ν¬κ±°λ‚˜ μž‘μ€ μˆœμ„œλ‘œ 학생듀이 정렬이 될 것이닀.

 

이 말을 λ‹€μ‹œ ν’€μ–΄μ„œ 말 ν•œλ‹€λ©΄, λ“€μ–΄μ˜¨ μˆœμ„œμ— 상관 없이 μš°μ„ μˆœμœ„κ°€ 높은 데이터가 λ¨Όμ € 좜λ ₯λœλ‹€λŠ” λœ»μ΄λ‹€.

μŠ€νƒ VS 큐 VS μš°μ„ μˆœμœ„ 큐

자료 ꡬ쑰 μ‚­μ œ λŒ€μƒ
μŠ€νƒ κ°€μž₯ λ‚˜μ€‘μ— λ“€μ–΄μ˜¨ 데이터
큐 κ°€μž₯ λ¨Όμ € λ“€μ–΄μ˜¨ 데이터
μš°μ„ μˆœμœ„ 큐 κ°€μž₯ μš°μ„ μˆœμœ„κ°€ 높은 데이터

μ—¬κΈ°μ„œ μ‹ κΈ°ν•œ 사싀은 μš°μ„ μˆœμœ„ 큐둜 μŠ€νƒμ΄λ‚˜ 큐λ₯Ό κ΅¬ν˜„ν•  수 μžˆλ‹€λŠ” 것이닀.

 

μœ„μ˜ ν‘œλ₯Ό 보면 μ•Œκ² μ§€λ§Œ μŠ€νƒκ³Ό νλŠ” μš°μ„ μˆœμœ„ 큐의 μž…μž₯μ—μ„œ λ³Έλ‹€λ©΄, μš°μ„ μˆœμœ„κ°€ λ“€μ–΄μ˜¨ μˆœμ„œμ΄λ‹€.

 

이λ₯Ό μ΄μš©ν•˜λ©΄ μš°μ„ μˆœμœ„ 큐둜 μŠ€νƒκ³Ό 큐 자료ꡬ쑰 λͺ¨λ‘λ₯Ό κ΅¬ν˜„ν•  수 μžˆλ‹€.

μš°μ„ μˆœμœ„ 큐 μ—°μ‚°μ˜ λ‚΄λΆ€ λ™μž‘ κ³Όμ •

μš°μ„ μˆœμœ„ νλŠ” λ‚΄λΆ€μ μœΌλ‘œ μ‚­μ œμ™€ μ‚½μž…μ˜ 연산이 μ΄λ£¨μ–΄μ§ˆ λ•Œ μ–΄λ–€ 자료 ꡬ쑰둜 κ΅¬ν˜„μ΄ 될까?


μš°μ„ μˆœμœ„ νλŠ” μš°λ¦¬κ°€ λ°”λ‘œ 전에 λ°°μ› λ˜ Heap(νž™ 자료ꡬ쑰) 에 내뢀적인 λ™μž‘μ— μ˜ν•΄ λ™μž‘ν•œλ‹€. λ‹€λ₯Έ μžλ£Œν˜•κ³Ό λΉ„κ΅ν•΄λ³΄μž.

 

Unsorted Array

μ •λ ¬λ˜μ§€ μ•Šμ€ 배열은 μ‚½μž…μ΄ κ°„λ‹¨ν•˜λ‹€. κ·Έλƒ₯ κΈ°μ‘΄ μš”μ†Œ λ§ˆμ§€λ§‰μ— λΆ™νžˆλ©΄ λ˜λŠ”λ° μ΄λŠ” μ‹œκ°„ λ³΅μž‘λ„κ°€ O(1)이닀. ν•˜μ§€λ§Œ μ‚­μ œν•  λ•Œ μš°μ„ μˆœμœ„λ₯Ό λ”°μ Έμ•Ό ν•˜λ―€λ‘œ κ²°κ΅­ λ°°μ—΄ λͺ¨λ“  μ›μ†Œλ₯Ό ν•œ λ²ˆμ”© 확인해야 ν•˜λ―€λ‘œ μ‹œκ°„ λ³΅μž‘λ„λŠ” O(n)이 λœλ‹€.

Sorted Array

μ •λ ¬λœ λ°°μ—΄μ˜ μ‚½μž…μ€ 쑰금 λ³΅μž‘ν•΄μ§„λ‹€. μ‚½μž…ν•  μš”μ†Œμ— λŒ€ν•œ μš°μ„ μˆœμœ„λ₯Ό λ‹€λ₯Έ κ°’λ“€κ³Ό 비ꡐ해야 ν•˜λ―€λ‘œ μ‹œκ°„ λ³΅μž‘λ„λŠ” O(n)κ°€ λœλ‹€. μ‚­μ œκ°€ 된 뒀에도 각 μš”μ†Œλ₯Ό μ•žμœΌλ‘œ λ‹Ήκ²¨μ€˜μ•Ό ν•œλ‹€λŠ” 점이 λ„˜μ–΄μžˆμ§€λ§Œ 이미 μ‹œκ°„λ³΅μž‘λ„κ°€ μ˜€λ°”λ‹ˆκΉŒ λ„˜μ–΄κ°€μž

Sorted, Unsorted LinkedList

μ •λ ¬λ˜μ§€ μ•Šμ€ λ¦¬μŠ€νŠΈλ‚˜ μ •λ ¬λœ λ¦¬μŠ€νŠΈλ‚˜ 사싀 κ±°κΈ°μ„œ κ±°κΈ°λ‹€. 배열은 연속적인 λ°μ΄ν„°μ˜ 묢음이고 λ¦¬μŠ€νŠΈλŠ” 비연속적엔 λ…Έλ“œμ˜ 연결에 μ˜ν•΄ μ΄λ£¨μ–΄μ ΈμžˆλŠ”λ°, μ‚½μž…κ³Ό μ‚­μ œ μ—­μ‹œ μš°μ„ μˆœμœ„λ₯Ό 비ꡐ해야 ν•˜λ―€λ‘œ 각각 O(n), O(1)의 μ‹œκ°„ λ³΅μž‘λ„κ°€ μ†Œλͺ¨λœλ‹€.

Heap

νž™μ€ λ°˜μ •λ ¬ μƒνƒœλ₯Ό μœ μ§€ν•˜λ―€λ‘œ 트리의 높이에 따라 μ‹œκ°„ λ³΅μž‘λ„κ°€ κ³„μ‚°λ˜λ―€λ‘œ O(log2N)μ΄λΌλŠ” μ–΄λ§ˆμ–΄λ§ˆν•œ μ‹œκ°„λ³΅μž‘λ„μ˜ 단좕이 μ‘΄μž¬ν•œλ‹€.

μžλ°”μ˜ PriorityQueue class

이제 λ‚΄λΆ€ λ™μž‘μ€ Heap에 μ˜ν•΄ 이루어 μ§„λ‹€λŠ” 것을 μ•Œκ²Œ λ˜μ—ˆλ‹€.

 

그럼 μ‹€μ „μ—μ„œ μ‚¬μš©ν•˜κΈ° μœ„ν•΄μ„œ μžλ°”μ˜ PriorityQueue 클래슀λ₯Ό λ°°μ›Œλ³΄μž.

java.util 클래슀둜 μ»¬λ ‰μ…˜μ΄ μžˆλŠ” νŒ¨ν‚€μ§€μ™€ λ™μΌν•œ νŒ¨ν‚€μ§€μ— μ‘΄μž¬ν•œλ‹€.


일단 μš°μ„ μˆœμœ„ 큐λ₯Ό μ΄μš©ν•˜κΈ° μœ„ν•΄μ„œλŠ” κ°€μ€‘μΉ˜, 즉 μš°μ„ μˆœμœ„κ°€ μ‘΄μž¬ν•΄μ•Ό ν•œλ‹€.


μ‚¬λžŒμ΄λΌλŠ” 클래슀λ₯Ό λ§Œλ“€μ–΄μ„œ μ‚¬λžŒμ˜ λ‚˜μ΄μˆœ λŒ€λ‘œ 이름을 좜λ ₯μ‹œμΌœλ³΄μž.


λ‚˜μ΄μˆœλŒ€λ‘œ 이름을 좜λ ₯ν•˜κΈ° μœ„ν•΄μ„œλŠ” 또 comparable μΈν„°νŽ˜μ΄μŠ€λ₯Ό μ΄μš©ν•΄μ„œ compareTo λ©”μ„œλ“œλ₯Ό μž¬μ •μ˜ ν•΄μ•„ν•œλ‹€.

 

public class My_PriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Person> priorityQueue = new PriorityQueue<>();

        Person p1 = new Person(10, "jang");
        Person p2 = new Person(11, "Heo");
        Person p3 = new Person(11, "park");
        Person p4 = new Person(9, "choi");
        Person p5 = new Person(8, "seo");
        priorityQueue.offer(p1);
        priorityQueue.offer(p2);
        priorityQueue.offer(p3);
        priorityQueue.offer(p4);
        priorityQueue.offer(p5);

        System.out.println(priorityQueue.size());
        while(!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll().name);
        }
    }
    private static class Person implements Comparable<Person> {
        int age;
        String name;

        Person(int age, String name) {
            this.age = age;
            this.name = name;
        }

        @Override
        public int compareTo(Person o) {
            return o.age - this.age;
        }
    }
}

μš°λ¦¬κ°€ 주의깊게 보아야 ν•˜λŠ” 뢀뢄은 λ°”λ‘œ Person클래슀 이닀.

 

Person ν΄λž˜μŠ€μ— μ •λ ¬ 기쀀을 λ‚˜μ΄λ‘œ μ •ν•΄μ£Όλ©΄ μš°μ„ μˆœμœ„ 큐의 λ‚΄λΆ€ νž™μ— μ˜ν•΄μ„œ κ°€μ€‘μΉ˜κ°€ 적용된 κ²°κ³Όλ₯Ό 좜λ ₯ν•˜κ²Œ λœλ‹€.

그럼 μš°μ„ μˆœμœ„μ˜ μ—­μˆœμ€?

μš°μ„ μˆœμœ„ μ—­μˆœμ€ 두 가지 방법이 μžˆλ‹€.

  1. Comparable λ©”μ„œλ“œλ₯Ό μ—­μˆœ μž¬μ •μ˜ ν•˜λŠ” 방법
  2. Collections.reverseOrder()λ₯Ό PriorityQueue의 μƒμ„±μž λ§€κ°œλ³€μˆ˜λ‘œ λ„˜κ²¨μ£ΌλŠ” 것.

λ©”μ„œλ“œμ˜ μ—­μˆœ μž¬μ •μ˜λŠ”

@Override
        public int compareTo(Person o) {
            return this.age - o.age;
        }

둜 λ°˜ν™˜ 값을 λ°”κΏ”μ£Όλ©΄ 되고

 

μƒμ„±μž λ§€κ°œλ³€μˆ˜λŠ” λ‹€μŒκ³Ό 같이 ν•΄μ£Όλ©΄ λœλ‹€.

PriorityQueue<Person> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

λŒ“κΈ€