개인 공부/자료구조
std::priority_queue
chaeD2
2022. 5. 19. 17:35
개요
heap이라 불리는 유용한 구조 제공.
heap은 컨테이너에서 가장 작거나 큰 원소에 빠르게 접근할 수 있는 자료구조.
시간 복잡도
최소/최대 원소에 접근하는 동작은 O(1), 원소 삽입은 O(logn)로 동작.
특징
최소/최대 원소에 대해서만 원소 제거가 가능.
stack이나 queue와 달리 vector를 기본 컨테이너로 사용.
비교자는 std::less가 기본.
언제든 특정 위치에 있는 원소 하나만을 참조하면 되기 때문에, 반복자를 지원하지 않는다.
더 자세한 내용은
https://en.cppreference.com/w/cpp/container/priority_queue
std::priority_queue - cppreference.com
template< class T, class Container = std::vector , class Compare = std::less > class priority_queue; A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarit
en.cppreference.com