티스토리 뷰
Priority Queue란?
In computer science, a priority queue is an abstract data type similar to a regular queue or stack data structure in which each element additionally has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority.
Priority Queue는 Queue나 Stack 같은 일반적인 자료구조에 우선순위(priority)라는 요소가 추가된 데이터 타입이다. Priority Queue 에선 우선순위가 높은 엘리먼트가 먼저 배출된다.
- Wikipedia
An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.
Priority Queue는 Priority Heap에 기반하고 있다. Priority Queue의 엘리먼트 들은 자연적인 순서나 생성 시 제공되는 Comparator에 의해 정렬된다.
- docs.oracle
우선순위큐는(Priority Queue) 큐와 비슷하게 데이터를 넣고 뺄 수 있는 자료구조이지만 배출되는 순서가 스택이나 큐처럼 입력 순서에 의해 결정되는 것이 아닌 우선순위에 의해 결정됩니다. java의 경우 Heap을 활용해 Priority Queue를 구현하고 있으며, 값을 비교하기 위해 엘리먼트는 Comparator를 준수하고 있어야 합니다.
Heap 이란?
Priority Queue를 알아보려는데 갑자기 Heap이라는게 튀어나옵니다. Heap은 또 무엇일까요?
In computer science, a heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The heap is one maximally efficient implementation of an abstract data type called a priority queue.
Heap은 완전한 이진트리 구조를 가지고 있으며 Heap의 속성을 축 중하는 Tree에 기반한 자료구조입니다. 여기서 Heap의 속성이란 모든 부모 노드가 자식 노드보다 크거나 같다는 조건을 충족하는 최대 힙(max heap) 혹은 모든 모든 부모 노드가 자식 노드보다 작거나 같다는 조건을 충족하는 최소 힙(min heap)을 이야기한다. Heap은 Priority Queue라고 하는 자료구조의 가장 효율적인 구현 중 하나이다.
- Wikipedia
Heap은 데이터를 특정한 순서대로 저장하되 효율적으로 저장하기 위한 자료구조 입니다.
위 영상이 max heap의 insert과정을 잘 보여줍니다. heap에 새로운 데이터가 들어오게 되면 heap의 성질을 충족하고 있는지 부모 노드의 값과 비교하고, 충족되지 않을 시 부모와 자식 노드의 위치를 순차적으로 바꾸는 과정으로 heap의 성질을 충족하도록 만듭니다. 그리고 이 과정을 heapify라고 부릅니다. 여기서 주목해야 할 점은 완전한 이진트리라는 구조 덕에 logN의 시간 복잡도로 빠르게 정렬할 수 있다는 것입니다.
remove혹은 poll의 과정도 비슷합니다. 다만 차이가 있다면 root노드와 마지막 노드의 위치를 바꾼 뒤 기존의 root노드를 제거하고 나서 heapify를 한다는 것입니다. 이때도 insert와 동일하게 logN의 시간 복잡도를 보장합니다.
ref.
https://en.wikipedia.org/wiki/Priority_queue
https://en.wikipedia.org/wiki/Heap_(data_structure)
https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html
https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm