Java Queue

Both PriorityQueue and LinkedList implement Java Queue interface.

There are these methods. Every is a pair. The first one will throw error on failure. The second will return special value instead of throwing error.

• add(e) offer(e)
• remove() poll()
• element() peek()

For LinkedList, we can call removeFirst()

Java PriorityQueue

java PriorityQueue implements java.util.AbstractQueue class which extends java.util.Collection

The head of the queue is the least element with respect to the specified ordering. However, can provide Collections.reverseOrder() in the constructor to create a max heap.

useful methods:

• peek()
• poll()

methods from java.util.Collection

• size()
• add()
• isEmpty()

Here is a Leetcode problem leetcode 1046 which can be solved by max heap

import java.util.*;
class Solution {
    public int lastStoneWeight(int[] stones) {
        //create a max heap. The head has the max value
        var q = new PriorityQueue<Integer>(Collections.reverseOrder());

        //add element into heap
        for (int s: stones) {
            q.add(s);
        }

        while(q.size()>1) {
            int x = q.poll();
            int y = q.poll();

            if (x != y) {
            	//put result stone back into queue
                q.add(Math.abs(x-y));
            }
		}

        //check q.size
        if (q.size()==1) {
            return q.poll();
        } else {
            return 0;
        }
    }
}

Tree Level Traversal

The below is a solution for LeetCode 104

public int maxDepth(TreeNode root) {
        if (root ==null) return 0;
        
        var myq = new LinkedList<TreeNode>();
        myq.add(root);
        var ans = 0;
        
        while(!myq.isEmpty()) {
            //queue only holde nodes of current level
            var size = myq.size();
            
            //every iteration is one level because of size
            for(int i=0; i<size; i++) {
                TreeNode cur = myq.poll();
                if (cur.left!=null) myq.add(cur.left);
                if (cur.right!=null) myq.add(cur.right);
             }
            
            ans++;
        }
        
        return ans;
        
    }

Use Paire as queue element

2462

Priority Queue using custom comparator

Leetcode 2099

class Solution {

  public int[] maxSubsequence(int[] nums, int k) {
    var pq = new PriorityQueue<int[]>((a, b) -> a[1] - b[1]);

    for (int i = 0; i < nums.length; i++) {
      int[] t = { i, nums[i] };
      if (pq.size() < k) {
        pq.add(t);
      } else {
        var e = pq.peek();
        if (e[1] < nums[i]) {
          pq.poll();
          pq.add(t);
        }
      }
    }

    int[] index = new int[k];
    int j = 0;
    while (pq.size() > 0) {
      var e = pq.poll();

      index[j] = e[0];
      j++;
    }

    Arrays.sort(index);

    int[] ans = new int[k];
    j = 0;
    for (int i : index) {
      ans[j] = nums[i];
      j++;
    }

    return ans;
  }
}

array as queue element

//See Leetcode 373
PriorityQueue<int[]> minHeap = new PriorityQueue<> ((a, b) -> (a[0] + a[1]) - (b[0] + b[1]));
       
//init. the last two elements are index for two array
minHeap.add(new int[]{nums1[0], nums2[0], 0 ,0});