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(logn)	O(logn)