Priority Queue

A priority queue is an abstract data type that maintains a multiset of items.

Underlying Data Structures

The following data structures can be considered to implement a priority queue, with differing time complexities:

Structure	Insert	removeMin
Unordered array	$O(1)$	$O(n)$
Ordered array	$O(n)$	$O(1)$
AVL tree	$O(\log n)$	$O(\log n)$
Binary Heap	$O(\log n)$	$O(\log n)$