[DataStructure] PriorityQueue (Java)

1. PriorityQueue

java 11

Module java.base
Package java.util
Class PriorityQueue<E>
java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractQueue<E>
java.util.PriorityQueue<E>
Type Parameters:
E - the type of elements held in this queue
All Implemented Interfaces:
Serializable, Iterable<E>, Collection<E>, Queue<E>

public class PriorityQueue<E>
extends AbstractQueue<E>
implements Serializable

2. 설명

우선순위 힙을 기반으로 하는 크기제한이 없는 priority queue 입니다.

priority queue의 element는 자연 순서에 따라 정렬되거나 사용되는 Constructor에 따라 queue 생성 시 제공된 Comparator에 의해 정렬됩니다. priority queue는 null 요소를 허용하지 않습니다. 자연 순서에 의존하는 priority queue는 비교할 수 없는 개체의 삽입도 허용하지 않습니다(이렇게 하면 ClassCastException이 발생할 수 있습니다).

이 queue의 HEAD는 지정된 순서와 관련하여 가장 작은 element입니다. 여러 element가 최소값으로 연결되어 있으면 HEAD가 해당 요소 중 하나입니다. 연결은 임의로 끊어집니다. queue 검색 작업은 queue의 HEAD에 있는 element를 poll, remove, peek 및 access합니다.

priority queue는 은 크기 제한이 없지만 queue에 요소를 저장하는 데 사용되는 배열의 크기를 제어하는 내부 용량이 있습니다. 항상 최소한 대기열 크기만큼 큽니다. element가 priority queue에 추가되면 용량이 자동으로 늘어납니다. 성장 정책의 세부 사항은 지정되지 않습니다.

이 class와 iterator는 Collection 및 Iterator 인터페이스의 모든 선택적 메서드를 구현합니다. iterator() 메서드에 제공된 Iterator와 spliterator() 메서드에 제공된 Spliterator는 특정 순서로 priority queue의 element를 순회한다고 보장되지 않습니다. 정렬된 순회가 필요한 경우 Arrays.sort(pq.toArray()) 사용을 고려하십시오.

이 구현은 동기화되지 않습니다. 스레드 중 하나가 큐를 수정하는 경우 여러 스레드가 PriorityQueue 인스턴스에 동시에 액세스해서는 안 됩니다. 대신 스레드로부터 안전한 PriorityBlockingQueue 클래스를 사용하십시오.

구현 참고 사항: 이 구현은 queue에 추가하고 queue에서 빼는 메서드(offer, poll, remove() 및 add)에 대해 O(log(n)) 시간을 제공합니다. remove(Object) 및 contains(Object) O(n)시간이고 검색 방법(peek, element 및 size)에 대한 O(log(1)) 시간을 제공합니다.

이 Class는 Java Collections Framework의 멤버입니다.

2.1 Since

1.5

2.2 See Also

Serialized Form

3.1 Heap (참고사이트)

힙이란 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조입니다.
여러값들 중에서 최솟값과 최대값을 빠르게 찾아내도록 만들어진 자료 구조입니다.
힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지합니다.

3.1.1 Heap의 종류

• 최대 힙(max heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 = key(부모 노드) >= key(자식 노드)
• 최소 힙(min heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 = key(부모 노드) <= key(자식 노드)

3.1.2 Heap의 구현 (참고 사이트)

힙을 저장하는 표준적인 자료구조는 배열입니다.
구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않습니다.

힙에서의 부모 노드와 자식 노드의 관계
왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2

3.1.3 Heap의 삽입

힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.

3.1.4 Heap의 삭제

최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다.
최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다.
삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
힙을 재구성한다.

3. PriorityQueue 내림차순 오름차순 자바 소스

참고사이트

3. 생성자

PriorityQueue()
Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.
PriorityQueue​(int initialCapacity)
Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.
PriorityQueue​(int initialCapacity, Comparator<? super E> comparator)
Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.
PriorityQueue​(Collection<? extends E> c)
Creates a PriorityQueue containing the elements in the specified collection.
PriorityQueue​(Comparator<? super E> comparator)
Creates a PriorityQueue with the default initial capacity and whose elements are ordered according to the specified comparator.
PriorityQueue​(PriorityQueue<? extends E> c)
Creates a PriorityQueue containing the elements in the specified priority queue.
PriorityQueue​(SortedSet<? extends E> c)
Creates a PriorityQueue containing the elements in the specified sorted set.

4. 메서드

boolean add​(E e)
Inserts the specified element into this priority queue.
void clear()
Removes all of the elements from this priority queue.
Comparator comparator() Returns the comparator used to order the elements in this queue, or null if this queue is sorted according to the natural ordering of its elements. boolean contains​(Object o) Returns true if this queue contains the specified element. void forEach​(Consumer action) Performs the given action for each element of the Iterable until all elements have been processed or the action throws an exception. Iterator iterator() Returns an iterator over the elements in this queue. boolean offer​(E e) Inserts the specified element into this priority queue. boolean remove​(Object o) Removes a single instance of the specified element from this queue, if it is present. boolean removeAll​(Collection c)
Removes all of this collection's elements that are also contained in the specified collection (optional operation).
boolean removeIf​(Predicate filter) Removes all of the elements of this collection that satisfy the given predicate. boolean retainAll​(Collection c)
Retains only the elements in this collection that are contained in the specified collection (optional operation).
Spliterator spliterator()
Creates a late-binding and fail-fast Spliterator over the elements in this queue.
Object[] toArray()
Returns an array containing all of the elements in this queue.
T[] toArray​(T[] a)
Returns an array containing all of the elements in this queue; the runtime type of the returned array is that of the specified array.

#### Methods declared in interface java.util.Collection ####
clear, containsAll, equals, hashCode, isEmpty, parallelStream, removeAll, removeIf, retainAll, spliterator, stream, toArray, toArray, toArray

#### Methods declared in interface java.lang.Iterable ####
forEach

5. 시간복잡도

offer(Object), poll(), remove(), add(Object) = O(log(n))
remove(Object), contains(Object) = O(n)
peek(), element(), size() = O(1)

참고링크

6. 공간복잡도

대부분의 Collection들은 O(n)
참고링크
참고링크