Java PriorityQueue Complexity


Java TreeMap, TreeSet, and PriorityQueue have something in common, they all maintain some kind of ordering.
HashSet is implemented using a HashMap, TreeSet is implemented using a TreeMap. The TreeMap itself is implemented using a red-black tree which is a self-balancing binary search tree. On the other hand, a HashMap has an average time complexity of O(1) for put(), contains() and remove() operations. The worst-case time complexity for those operations is O(log n) since Java 8, and O(n) before that. Big O complexities are as follows.

PriorityQueue

log(n) operations: offer(), poll(), remove(), add()
O(1) opearations: peek(), size()
O(n) operations: remove(object), contains(object)

HashMap

log(n) operations: get(), put(), contains(), remove()
O(n) operations: clone(), equals(), hashCode(), toArray(), toString()
O(1) opearations: clear(), isEMpty(), size()

TreeMap

log(n) operations: get(), put(), containsKey() and remove()
O(n) operations: clone(), equals(), hashCode(), toArray(), toString(), containsValue()
O(1) opearations: clear(), isEMpty(), size()

TreeSet

log(n) operations: add(), contains(), remove()
O(1) opearations: clear(), first(), isEMpty(), size(), last(), pollFirst(), pollLast()
O(n) operations: clone(), equals(), hashCode(), toArray() and toString()

No comments :

Post a Comment

Please leave your message queries or suggetions.