- Create (pqueue Q)
- Insert (elementtype item, pqueue Q)
- elementtype DeleteMin (pqueue Q)
- Unsorted linked list
- Insert is O(1); DeleteMin is O(N)
- Sorted linked list
- DeleteMin is O(1); Insert is O(N)
- Partially ordered, balanced binary tree, where the value
of a node is no greater than the value of its children (hence
the minimum value is at the root). To maintain balance after
deleting the root, move the rightmost leafnode to the root,
and percolate it downwards based on its value. To insert,
put new node at leftmost position in lowest level, and percolate
upwards based on its value.
- DeleteMin and Insert are O(log N) since the height of
a balanced binary tree of N nodes is log N.