본문 바로가기
공부방

[자료구조] 우선순위큐(PriorityQueue)에 대한 고찰

개발하는 히포 2024. 12. 29. 17:27

우선순위 큐(Priority Queue)는 각 요소에 우선순위(priority)를 부여하여, 우선순위가 가장 높은 요소가 먼저 처리되는 자료구조이다. 일반적인 큐와 다른 점은, 큐에서는 FIFO(First In, First Out) 원칙에 따라 요소가 처리되지만, 우선순위 큐에서는 우선순위에 따라 요소가 처리된다.

 

우선순위: 각 요소는 우선순위를 가지고 있으며, 우선순위가 높은 요소가 먼저 큐에서 제거된다.
동적 크기: 우선순위 큐는 동적으로 크기가 변할 수 있으며, 요소를 추가하거나 제거할 수 있다.
구현 방식: 우선순위 큐는 보통 힙(Heap) 자료구조를 사용하여 구현된다. 최소 힙(Min-Heap)이나 최대 힙(Max-Heap)을 사용하여 우선순위를 관리한다.

우선순위 큐는 동적으로 크기가 변할 수 있다라는건 그럼 큐의 크기는 어떤 기준에 따라서 변하게 될까?

 

Java의 PriorityQueue는 기본 생성자를 호출할 때 내부 배열을 11 크기로 초기화한다.(내부 배열을 크기 11로 초기화하는 것은 JDK 1.5부터다. 이전 버전에서는 기본 크기가 10)

큐가 비어 있는 상태에서 size() 메소드를 호출하면 0이 출력되지만, 내부 배열의 기본 크기는 11이다. 이 크기는 큐에 요소가 추가될 때, 내부적으로 필요한 경우 grow 메서드를 통해 확장된다.

 

grow 메서드로 들어가보자.

ArraysSupport.newLength 메서드에서 최종적으로 우선순위 큐의 크기(newCapacity)를 결정짓는 것 같다.

newLength 메소드에서 기존 크기에 Math.max(minGrowth, prefGrowth)를 더하는 구조다. 따라서, grow 메소드에서 oldCapacity + 2 또는 oldCapacity >> 1이 직접적으로 더해지는 것이 아니라, newLength 메소드에서 이 값을 고려하여 최종 크기를 결정하는 것이다.

newLength 메소드에서의 if-else 구문은 오버플로우를 방지하기 위한 로직이다. 

public static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;

 

왜 -8을 하는지에 대해서는 스택오버플로우에서 아래와 같이 답변한 내용이 있었다. (배열의 크기를 저장하기 위한 8바이트를 고려)

더보기

Anatomy of a Java array object

The shape and structure of an array object, such as an array of int values, is similar to that of a standard Java object. The primary difference is that the array object has an additional piece of metadata that denotes the array's size. An array object's metadata, then, consists of: Class : A pointer to the class information, which describes the object type. In the case of an array of int fields, this is a pointer to the int[] class.

Flags : A collection of flags that describe the state of the object, including the hash code for the object if it has one, and the shape of the object (that is, whether or not the object is an array).

Lock : The synchronization information for the object — that is, whether the object is currently synchronized.

Size : The size of the array.

max size 2^31 = 2,147,483,648 

as the Array it self needs 8 bytes to stores the size 2,147,483,648

so 2^31 -8 (for storing size ),

so maximum array size is defined as Integer.MAX_VALUE - 8

prefLength는 oldLength에 minGrowth와 prefGrowth 중 더 큰 값을 더한 것으로 이 과정에서 오버플로우가 발생할 수 있다. prefLength가 특정 최대 크기(SOFT_MAX_ARRAY_LENGTH) 이하인지 확인하여 배열의 크기로 사용하기에 안전한 최대값이다. (만약 prefLength가 0 이하이거나 SOFT_MAX_ARRAY_LENGTH를 초과하면, hugeLength 메소드를 호출하여 더 큰 배열 크기를 결정)

if (minLength < 0): 이 조건은 minLength가 음수인지 확인하고 만약 minLength가 음수라면 오버플로우가 발생했음을 나타내고 OutOfMemoryError를 발생시킨다.
else if (minLength <= SOFT_MAX_ARRAY_LENGTH): 이 조건은 minLength가 안전한 최대 크기인 SOFT_MAX_ARRAY_LENGTH 이하인지 확인하여SOFT_MAX_ARRAY_LENGTH를 반환한다.
else: 만약 minLength가 SOFT_MAX_ARRAY_LENGTH를 초과한다면, minLength를 반환한다.

 

grow 메소드의 크기 증가 로직

  1. 64 미만일 경우:
    oldCapacity가 11이라면?
    prefGrowth는 oldCapacity + 2가 된다. 즉, prefGrowth는 11 + 2 = 13이다. 이 경우, newLength 메소드에서 크기를 결정할 때는 prefLength = oldCapacity + Math.max(minGrowth, prefGrowth);
    여기서 minGrowth는 minCapacity - oldCapacity이다. 예를 들어, minCapacity(큐에 추가해야 할 최소 원소의 수를 기준으로 설정된 값)가 1이라면 minGrowth는 1 - 11 = -10이 된다.
    prefLength = 11 + Math.max(-10, 13) = 11 + 13 = 24
    결론: 새로운 크기는 24가 된다.
  2. 64 이상일 경우:
    oldCapacity가 64라면?
    prefGrowth는 oldCapacity >> 1이 되어 즉, 64 >> 1은 32이다.이 경우, newLength 메소드에서: prefLength = oldCapacity + Math.max(minGrowth, prefGrowth);
    만약 minCapacity가 65라고 가정하면, minGrowth는 65 - 64 = 1이 된다.
    prefLength = 64 + Math.max(1, 32) = 64 + 32 = 96
    결론: 새로운 크기는 96이 된다.

왜 64가 기준일까?

작은 배열에서는 자주 메모리를 할당하고 해제하는 것보다, 약간의 여유를 두고 배열을 확장하는 것이 성능에 유리하고 64 이상의 크기에서는 큰 배열을 자주 할당하는 것보다, 크기를 두 배로 늘리는 것이 메모리 파편화를 줄이고 성능을 향상시킨다고 한다. (보다 상세한 내용 아시는 분은 댓글 부탁드리겠습니다.)

우선순위 큐는 힙(Heap) 자료구조를 사용하는데, 내부적으로 어떻게 구성된 구조일까?

만약 아래와 같이 임의의 원소를 offer() 했을 때,

void testPriorityQueueOrders() {
    PriorityQueue<Integer> pq = new PriorityQueue<>(Integer::compare);
    pq.offer(70);
    pq.offer(50);
    pq.offer(80);
    pq.offer(90);
    pq.offer(60);
    pq.offer(10);
    pq.offer(20);

    System.out.println(pq);
    print(pq);
}

void print(PriorityQueue<Integer> pq) {
    while(!pq.isEmpty()) {
        System.out.print(pq.poll() + " ");
    }
}

 

결과값 출력


위와 같이 내가 생각한 것과는 다른 결과가 나온다. 단순하게 나는 큐를 한 번에 출력하니까 원소를 임의의 순서로 랜덤으로 출력하는게 아닐까라는 생각이었다. 멍청한건 나였고, 컴퓨터가 귀찮아서 저렇게 랜덤(?)으로 출력한게 아니다.

 

우선순위 큐는 힙(Heap)구조
힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료 구조라고 한다. 따라서, 위의 출력 값 [10, 60, 20, 90, 70, 80, 50]은 아래의 트리 순서에 따른 것이었다!


힙은 루트 노드에 우선순위가 높은 데이터를 위치시키는 자료구조이다. 힙에 저장된 노드를 뺄 때마다 우선순위가 높은 데이터가 먼저 나온다.
최소 힙(Min Heap)은 완전 이진트리이면서, 루트 노드로 올라갈수록 값이 감소하는 구조다. 최대 힙이던 최소 힙이든 루트 노드에는 우선순위가 높은 것이 위치한다.

새로운 원소가 삽입(offer)된다면 어떻게 될까?
30을 넣어보자. 
새 노드를 우선순위가 가장 낮다는 가정을 하고 완전 이진트리를 만족해야 하므로 맨 끝 위치에 저장한다. 


부모노드 90이랑 비교해서 값이 더 작으므로 자식노드 30과 노드 위치 교체


부모노드 60이랑 비교해서 값이 더 작으므로 자식노드 30과 노드 위치 교체


부모노드 10이랑 비교해서 자식노드 값(30)이 더 크므로 노드 위치 교체하지 않음


새로운 노드가 삽입되면서 이 과정이 계속 반복된게 바로 [10, 60, 20, 90, 70, 80, 50]의 실체였다.
삭제(poll)는?


우선순위 큐에서의 poll()은 루트 노드를 삭제한다는 의미다. 루트 노드를 지우고 우선순위가 가장 낮은 맨 아래 노드(90)를 루트 노드에 위치시킨다. 그리고 우선순위를 하나씩 비교하면서 최소 힙구조를 유지할 때 까지 반복 비교를 한다.

티스토리툴바