-1

Started learning dsa and came across priority queues but I am stuck at lambda expressions in priority queue in java.

Map<Integer, Integer> map = new HashMap<>();
PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->map.get(b)-map.get(a));

In the above expressions, how will this heap be a max heap, how a,b values are to be considered whats their source? I have understood that the lambda expressions return -ve or +ve values and on that basis, it's decided whether its going to be a max or min heap but what are a,b how are they evaluated, from where they are received.

Are a,b the values from heap? If they are, which values are they, the top ones or the bottom ones considering a max heap?

Robert
  • 7,394
  • 40
  • 45
  • 64
Namash Sharma
  • 1
  • 1
  • the lambda you provide, or rather the argument is supposed to be a comparator that compares one element in the priorityQueue to another to decide the ordering. – experiment unit 1998X Jul 21 '23 at 04:25
  • what is the one element and another element here. , is every element in the priority queue to be considered – Namash Sharma Jul 21 '23 at 04:28
  • extra reading: https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html – experiment unit 1998X Jul 21 '23 at 04:29
  • "_what is the one element and another element here_" – Any two elements in the queue. That lambda is an implementation of `Comparator`. As part of the implementation of `PriorityQueue`, that comparator's `compare` method will be invoked with two arguments when and as appropriate. – Slaw Jul 21 '23 at 04:46
  • "_how will this heap be a max heap_" – [`PriorityQueue`](https://docs.oracle.com/en/java/javase/20/docs/api/java.base/java/util/PriorityQueue.html) is a min heap. Of course, you can "reverse" the comparison, making it appear to be a max heap with respect to the element's natural ordering. But it's still technically a min heap, as the head is the "least" element as defined by the `Comparator`. – Slaw Jul 21 '23 at 04:51
  • Does this answer your question? [How do I use a PriorityQueue?](https://stackoverflow.com/questions/683041/how-do-i-use-a-priorityqueue) – trincot Jul 21 '23 at 06:12

1 Answers1

0

In the provided code, a and b represent the elements present in the heap (PriorityQueue). The lambda expression (a, b) -> map.get(b) - map.get(a) is used as the comparator for the PriorityQueue, which determines how elements are compared and ordered in the heap.

In a PriorityQueue, the elements are sorted based on the result of the comparator. The comparator is applied to the elements present in the queue to determine their relative order. In this case, the lambda expression compares the values of the keys in the map associated with elements a and b.

The lambda expression (a, b) -> map.get(b) - map.get(a) subtracts the value associated with element a from the value associated with element b. This means that the element with a higher value in the map will be considered greater, and therefore, will have a higher priority in the PriorityQueue. Consequently, the PriorityQueue will act as a max heap, where the element with the highest value in the map will be at the root (top) of the heap.

In other words, the lambda expression is used to define the priority or ordering of elements in the PriorityQueue, and by subtracting the values in reverse order (b - a), we create a max heap where the element with the highest value in the map has the highest priority.

vs01
  • 11
  • 1