### TreeMap

A Red-Black tree based

`NavigableMap`

implementation.

For the `containsKey`

, `get`

, `put`

and `remove`

operations, `TreeMap`

guarantees `log(n)`

time cost.
While `HashMap`

implements these four operation with `O(1)`

time complexity.
So when acting as a traditional hash table, `TreeMap`

is slower than `HashMap`

.

However, `TreeMap`

has its own advantages. It’s not just a simple `Map`

, but a `SortedMap`

.
It provides methods to get lowest and greatest key/entry more efficient than `HashMap`

.

`firstEntry()`

/`firstKey()`

/`pollFirstEntry()`

, to return/remove lowest key or entry.`lastKey()`

/`lastEntry()`

/`pollLastEntry()`

, for greatest key or entry.

To get the lowest or greatest, `HashMap`

does it in `O(n)`

time cost, while ** TreeMap only needs O(logn)**.
(

`TreeMap`

keeps going left or right to retrieve the lowest or greatest.)```
// TreeMap source code
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
```

*Check TreeMap Javadoc for more details.*

### PriorityQueue

An unbounded priority queue based on a priority heap.

The head of this queue is the least element with respect to the specified ordering.

So, for retrieving the lowest, `PriorityQueue`

is faster than `TreeMap`

.
`PriorityQueue`

provides `O(1)`

time cost, while `TreeMap`

provides `log(n)`

.

```
// PriorityQueue source code
public E peek() {
return (E) queue[0];
}
```

For removing the lowest in a `PriorityQueue`

, it’s an `O(logn)`

operation,
which is same as doing it a `TreeMap`

.

As its name indicates, `PriorityQueue`

is a better choice when it’s used as a priority queue,
that is, letting the lowest one be in the front of the queue.
Retrieving the lowest, removing it and letting the next lowest value be in the front of the queue
are fast, which are `O(logn)`

operations.

However, if sometimes we need to remove an **arbitrary** entry, not the lowest entry,
and want to retrieve the lowest fast, in this case, `TreeMap`

provides a better overall performance than `PriorityQueue`

.
For example, we have a composite operation which has the following operations.

- Add a new entry.
- Remove some existed entry, not the lowest.
- Retrieve the lowest entry.

For `PriorityQueue`

, the second step is the slowest operation, which is `O(n)`

.
So, the overall time cost of the composite operation using `PriorityQueue`

is `O(n)`

.
While using `TreeMap`

, all three steps cost `O(logn)`

, so the overall time cost is `O(logn)`

.

*Check PriorityQueue Javadoc for more details.*