• 개인 공부 목적으로 작성한 포스팅입니다.
  • 아래 출처를 참고하여 작성하였습니다. :)

우선순위 큐(Priority Queue)

자료 구조 개념으로 구현하는 방법은 여러 가지입니다.
힙으로 구현하는 것이 성능이 가장 좋을 뿐, 배열/연결 리스트로 만들어도 됩니다.

우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조

여러가지 구현방법

시간복잡도의 차이가 발생하는 지점은 내부 데이터를 우선순위 큐의 목적에 맞게 재정렬하는 과정에서 발생합니다
중요한 차이점은, 재정렬 과정에서 Heap의 경우 Heapify라는 독특한 연산을 통해서 O(logN)만에 재정렬이 끝납니다.

구현방법 enqueue() dequeue()
배열 (unsorted array) O(1) O(N)
연결 리스트 (unsorted linked list) O(1) O(N)
정렬된 배열 (sorted array) O(N) O(1)
정렬된 연결 리스트 (sorted linked list) O(N) O(1)
힙 (Heap) O(logN) O(logN)

힙(Heap)

JAVA 구현 기준입니다

Priority queue represented as a balanced binary heap

Heap이란?

  • 완전 이진트리 기반으로 자료구조로 부모-자식끼리만 대소관계를 가지는 느슨한 정렬을 사용합니다.
    • 내부 모든 데이터가 정렬되어 있는 형태 X

내부적으로는 동적으로 크기가 커지는 배열로 구현되어 있습니다.

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {

    /**
     * Priority queue represented as a balanced binary heap: the two
     * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
     * priority queue is ordered by comparator, or by the elements'
     * natural ordering, if comparator is null: For each node n in the
     * heap and each descendant d of n, n <= d.  The element with the
     * lowest value is in queue[0], assuming the queue is nonempty.
     */
    transient Object[] queue; // non-private to simplify nested class access

n과 2n+1, 2n+2

Priority queue represented as a balanced binary heap
the two children of queue[n] are queue[2n+1] and queue[2(n+1)].

  • 힙 구현시 배열 인덱스를 0부터 사용하면 부모-자식 노드 간의 이동 연산 계산식이 n과 2*n+1, 2*n+2 입니다.

siftDown 연산: 부모 => 자식으로 이동하는 경우

int leftChild = (parent << 1) + 1;
int rightChild = leftChild + 1;

siftUp 연산: 자식 => 부모로 이동하는 경우

int parent = (child - 1) >> 1;