Menu
Why did they name PriorityQueue if you can't insertWithPriority? It seems very similar to a heap. Are there any differences? If no difference, then why was it named PriorityQueue and not Heap?
370
The priority queue is working on the queue and the heap is working on the tree data structure. The priority queue is stored array value in a simple form while the heap is stored array value in a sorted form. The heap provides multiple functions and operations than the priority queue.
1. In a Min-Heap the key present at the root node must be less than or equal to among the keys present at all of its children. In a Max-Heap the key present at the root node must be greater than or equal to among the keys present at all of its children.
priority_queue supports a constructor that requires two extra arguments to make it min-heap. priority_queue <Type, vector<Type>, ComparisonType > min_heap; `The third parameter, 'Comparison Type' can either be a function or factor (aka function object) that must have bool as return-type and must have 2 arguments.
Differences between PriorityQueue and TreeSetTreeSet 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.
The default PriorityQueue is implemented with Min-Heap, that is the top element is the minimum one in the heap.
In order to implement a max-heap, you can create your own Comparator:
import java.util.Comparator; public class MyComparator implements Comparator<Integer> { public int compare( Integer x, Integer y ) { return y - x; } } So, you can create a min-heap and max-heap in the following way:
PriorityQueue minHeap=new PriorityQueue(); PriorityQueue maxHeap=new PriorityQueue(size, new MyComparator()); For max-heap you can use:
PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder()); 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
