Menu
Seems they both let you retrieve the minimum, which is what I need for Prim's algorithm, and force me to remove and reinsert a key to update its value. Is there any advantage of using one over the other, not just for this example, but generally speaking?
672
TreeSet uses the Set underlying data structure. In PriorityQueue, apart from the root rest of the elements may or may not follow any order. In TreeSet all the elements remain in the sorted order. Using PriorityQueue, we can retrieve largest or smallest element in O(1) time.
A PriorityQueue is what is called a binary heap. It is only ordered/sorted in the sense that the first element is the least. In other word, it only cares about what is in the front of the queue, the rest are "ordered" when needed.
It will take O(log N) time to insert and delete each element in the priority queue. Based on heap structure, priority queue also has two types max- priority queue and min - priority queue. Let's focus on Max Priority Queue.
The default PriorityQueue is implemented with Min-Heap, that is the top element is the minimum one in the heap.
Generally speaking, it is less work to track only the minimum element, using a heap.
A tree is more organized, and it requires more computation to maintain that organization. But if you need to access any key, and not just the minimum, a heap will not suffice, and the extra overhead of the tree is justified.
104
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
