[Kotlin] Priority Queue

 

 

언제 사용하나?

가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료규조.

 

자료구조는?

Priority Heap == Heap + Complete Binary Tree 

Binary Search Tree 와 달리 중복을 허용하고 같은 레벨의 노드간에는 정렬 되있지 않은 느슨한 정렬 상태를 유지한다.

 

 

주요 연산 및 시간 복잡도

Operation	Time Complexity
Insert (add)	O (log N)
Find (contains)	O (N)
Find2 (peek)	O (1)
Delete (poll, remove)	O (log N)
Delete2 (remove(element))	O (N)

 

Binary Tree 인데 왜 Find 에 O(N) 이 걸리나?

PriorityQueue.contains() 원형

public boolean contains(Object o) {
// 해당 객체의 index가 0 이상인지 여부만 리턴한다.
    return indexOf(o) >= 0;
}

index 는 삽입된 순서에 의해 결정된다.

@Test
internal fun testPriorityQueueFind() {
    val pq = PriorityQueue<Int>(100)
    pq.addAll(listOf(1, 2, 7, 3, 4, 7, 8, 7, 3))

	// 원소 7은 0, 1, 2번째므로 index 2를 갖는다.
    println(pq.indexOf(7)) // 2 
}

맨 앞 0 인덱스부터 0, 1, 2 ... N 으로 찾기 때문에 $$ O(N) $$ 이 된다.

 

반면에 peek() 메소드는 현재 우선순위 큐의 root 값만 확인하므로 O(1) 이 된다.

 

특정 원소 삭제 remove(element) 도 
O(N)?

PrirorityQueue.remove() 원형

메소드의 원형을 보면 내부적으로 해당 원소의 index 부터 찾는 것을 알 수 있다.

따라서 우선순위 큐 내에 존재하는 특정 원소의 삭제는 $$ O(N) $$ 이 소요된다.

public boolean remove(Object o) {
    // 내부적으로 해당 원소의 index 부터 찾는다.
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        removeAt(i);
        return true;
    }
}

 

단점

특정 원소가 존재하는지 여부를 contains() 메소드로

$$ O(N) $$

이 소요되고, 특정 원소를 추출해내는 것이 불가능하다. (포함 여부만 알 수 있다.)

 

iterator 를 돌리는 방법이 있으나 이 또한

$$ O(N) $$

시간이 소요된다.  iterator 를 돌리는 방식도 우선순위와는 무관하다. (순서가 보장되지 않는다.)

 

iterator 를 통한 원소찾기

// Java code to illustrate iterator()
import java.util.*;
  
public class PriorityQueueDemo {
    public static void main(String args[])
    {
    	// min heap
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
  		
        queue.add(10);
        queue.add(15);
        queue.add(30);
        queue.add(20);
        queue.add(5);
 
        // Creating an iterator
        Iterator value = queue.iterator();
  
        // Displaying the values after iterating through the queue
        System.out.println("The iterator values are: ");
        // 5 -> 10 -> 15 -> 20 -> 30 순서가 보장되지 않는다.
        while (value.hasNext()) {
            System.out.print(value.next() + " ");
            // [print]
            // 5 10 30 20 15
        }
    }

 

특정 원소 접근시 O (N) 이 소요된다.

 

특정 원소를 O (log N) 내에
뽑아내려면?

 

TreeSet or TreeMap 을 사용해야한다.

단, TreeSet 과 TreeMap 사용 시 원소가 중복 허용되지 않는다.

중복성 여부는 `equals()` 와 `hashCode()` 를 통해 검사된다.

 

 

Kotlin Code

TreeSet은 iterating 시 순서가 보장된다.

따라서 해당 값이 존재하는지 쉽게 찾을 수 있다.

data class Room(val roomNum: Int, var isFull: Boolean) : Comparable<Room> {
    override fun compareTo(other: Room): Int {
        return if(this.isFull && !other.isFull) 1
        // 꽉차지 않은 방이 우선순위 높음.
        else if (!this.isFull && other.isFull) -1
        // 방의 상태가 같다면 방번호로 구별
        else this.roomNum.compareTo(other.roomNum)
    }
}

@Test
internal fun testTreeSet() {
    val treeRoomSet = TreeSet<Room>()
    treeRoomSet.add(Room(1, false))
    treeRoomSet.add(Room(2, true))
    treeRoomSet.add(Room(3, false))
    treeRoomSet.add(Room(4, true))
    treeRoomSet.add(Room(3, false)) // Duplicates is ignored.

    // 방이 존재하고, 풀방이 아닌 상태임을 안다면
    val threeRoom = Room(3, false)
    val targetRoom = treeRoomSet.floor(threeRoom)

    for (room in treeRoomSet) {
    // 우선순위가 높은 1, 3, 2, 4 순으로 출력된다.
        println(room)
    }
}

 

TreeSet 이 생성된 후에 객체의 값을 변경한다면, re-ordering 이 일어날까?

// 방이 존재하고, 풀방이 아닌 상태임을 안다면
val threeRoom = Room(3, false)
val targetRoom = treeRoomSet.floor(threeRoom)
// 3번방의 상태를 풀방으로 옮기면
targetRoom!!.isFull = true

// 우선순위상 1 -> 2 -> 3 -> 4 가 되야 하지만, 
// 1 -> 3 -> 2 -> 4 가 그대로 출력된다.
for (room in treeRoomSet) {
    println(room)
}

 

우선순위 큐라면 다를까?

@Test
internal fun testPriorityQueueRoom() {
    val pq = PriorityQueue<Room>()
    val firstRoom = Room(1, true)

    pq.add(firstRoom)
    pq.add(Room(2, true))
    pq.add(Room(3, false))
    pq.add(Room(4, false))

    // 1번방의 우선순위를 최고로 높임
    firstRoom.isFull = false

    while (pq.isNotEmpty()) {
        println(pq.poll())
    }
}

1번이 가장 먼저 와야하는데 3번이 먼저왔다.

 

그럼 Re-ordering 은 어떻게 해야하나?

원하는 값 추출(삭제) - 재삽입 해야한다.

// 1번방의 우선순위를 최고로 높임
firstRoom.isFull = false
// 수정하고자 하는 값을 삭제하고 재삽입 -> 재정렬 
pq.remove(firstRoom)
pq.add(firstRoom)

 

📝 Conclusion

 

우선순위 큐, TreeSet, TreeMap 은
re-ordering 을 위해 삭제(추출) -> 재삽입을 해야한다.

우선순위 큐에서 한번에 값을 추출하는 방법은 없다.
원한다면 TreeSet, TreeMap을 쓰자.

우선순위 큐는 중복을 허용하고
TreeSet, TreeMap 은 허용하지 않는다.

 

🔗 Reference

PriorityQueue (Java Platform SE 7 )

PriorityQueue in Java - GeeksforGeeks

PriorityQueue iterator() Method in Java - GeeksforGeeks