I just want to know if Java's PriorityQueue collection automatically heapifies, if any of the keys used in the comparator is mutated, or do i need to explicitly call heapify, to order the binary tree ?
I am experimenting with the data structure to use it in a cache like setting, where an object in the collection should be immediately moved to the head, as soon as it is referenced.
Asked
Active
Viewed 807 times
3
akhil
- 31
- 5
-
You can create a very effective cache by combining a hash map and a linked list. See https://stackoverflow.com/questions/22002814/is-this-algorithm-implementation-lru-or-mru for an example. It's in C#, but you should be able to convert it to Java easily enough. – Jim Mischel Jun 28 '17 at 13:55
1 Answers
3
The queue automatically heapifies on operations that mutates the queue itself, namely offer, poll, remove and add.
If you mutate an element you have to remove and re-insert it. The priority queue has no way of knowing that an element has been updated.
Jean Logeart
- 52,687
- 11
- 83
- 118