Using Priority Queue - How to Succeed in Algorithms Interview
Applications of Priority Queue
Implementation
- Use poll, peek, offer
- Don’t use remove (if need update it: just keep the old one and add a new one)
- Alternation: use TreeSet/Map
Order - How to add elements
for (int i = 0; i + 1 < nums.length; ++i) {
heap.offer(new Node(i, i+1));
}
Node node = null;
for (; k > 0; --k) {
node = heap.poll();
if (node.nei + 1 < nums.length) {
heap.offer(new Node(node.root, node.nei + 1));
}
}
Merge k sorted list
- Element: [outerIndex, innerIndex]
- Iterator
Examples
public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
List<Interval> res = new ArrayList<Interval>();
PriorityQueue<Node> minHeap = new PriorityQueue<Node>(
(a, b) -> schedule.get(a.employee).get(a.index).start - schedule.get(b.employee).get(b.index).start);
int start = Integer.MAX_VALUE;
for (int i = 0; i < schedule.size(); i++) {
minHeap.add(new Node(i, 0));
start = Math.min(start, schedule.get(i).get(0).start);
}
while (!minHeap.isEmpty()) {
Node cur = minHeap.poll();
if (start < schedule.get(cur.employee).get(cur.index).start) {
res.add(new Interval(start, schedule.get(cur.employee).get(cur.index).start));
}
start = Math.max(start, schedule.get(cur.employee).get(cur.index).end);
cur.index++;
if (cur.index < schedule.get(cur.employee).size()) {
minHeap.add(cur);
}
}
return res;
}
class Node {
int employee;
int index;
public Node(int employee, int index) {
this.employee = employee;
this.index = index;
}
}
Examples
public int nthSuperUglyNumber(int n, int[] primes) {
int[] ugly = new int[n];
int[] idx = new int[primes.length];
int[] val = new int[primes.length];
Arrays.fill(val, 1);
int next = 1;
for (int i = 0; i < n; i++) {
ugly[i] = next;
next = Integer.MAX_VALUE;
for (int j = 0; j < primes.length; j++) {
//skip duplicate and avoid extra multiplication
if (val[j] == ugly[i]) val[j] = ugly[idx[j]++] * primes[j];
//find next ugly number
next = Math.min(next, val[j]);
}
}
return ugly[n - 1];
}
public int nthSuperUglyNumberHeap(int n, int[] primes) {
int[] ugly = new int[n];
PriorityQueue<Num> pq = new PriorityQueue<>();
for (int i = 0; i < primes.length; i++) pq.add(new Num(primes[i], 1, primes[i]));
ugly[0] = 1;
for (int i = 1; i < n; i++) {
ugly[i] = pq.peek().val;
while (pq.peek().val == ugly[i]) {
Num nxt = pq.poll();
pq.add(new Num(nxt.p * ugly[nxt.idx], nxt.idx + 1, nxt.p));
}
}
return ugly[n - 1];
}
public int minRefuelStops(int target, int startFuel, int[][] stations) {
int curFarthest = startFuel, refuel = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
for (int[] station : stations) {
// check if we can reach this station
// if we cannot reach this station, refuel the gas from the previous station with most gas
// redo the operation until we get enough gas to reach this station
while (curFarthest < station[0]) {
if (pq.isEmpty()) return -1; // if we reful in each station but still cannot reach this station, return -1
curFarthest += pq.poll();
refuel++;
}
pq.offer(station[1]);
}
// now we have reached the last station, check if we can reach the target
while (curFarthest < target) {
if (pq.isEmpty()) return -1;
curFarthest += pq.poll();
refuel++;
}
return refuel;
}
public int minRefuelStops(int target, int cur, int[][] s) {
Queue<Integer> pq = new PriorityQueue<>();
int i = 0, res;
for (res = 0; cur < target; res++) {
while (i < s.length && s[i][0] <= cur)
pq.offer(-s[i++][1]);
if (pq.isEmpty()) return -1;
cur += -pq.poll();
}
return res;
}
Poll multiple elements - slots
public String rearrangeString(String str, int k) {
if(k<=1){ return str; }
int[] count = new int[26];
for(int i=0; i<str.length(); i++){
count[str.charAt(i)-'a']++;
}
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->b[0]-a[0]);
for(int i=0; i<count.length; i++){ pq.add(new int[]{ count[i], i}); }
char[] result = new char[str.length()];
int idx = 0;
int start = 0;
while(!pq.isEmpty()){
int[] num = pq.remove();
for(int i=0; i<num[0]; i++){
result[idx] = (char)(num[1]+'a');
if(idx>0 && result[idx-1]==result[idx]){ return ""; }
idx+=k;
if(idx>=str.length()){ idx=++start; }
}
}
return new String(result);
}
public String rearrangeString(String str, int k) {
for(char c: map.keySet())
queue.offer(c);
StringBuilder sb = new StringBuilder();
int len = str.length();
while(!queue.isEmpty()){
int cnt = Math.min(k, len);
ArrayList<Character> temp = new ArrayList<Character>();
for(int i=0; i<cnt; i++){
if(queue.isEmpty())//\\
return "";
char c = queue.poll();
sb.append(String.valueOf(c));
map.put(c, map.get(c)-1);
if(map.get(c)>0){
temp.add(c);
}
len--;
}
for(char c: temp)
queue.offer(c);
}
return sb.toString();
}
public int leastInterval(char[] tasks, int n) {
Map<Character, Integer> counts = new HashMap<Character, Integer>();
for (char t : tasks) {
counts.put(t, counts.getOrDefault(t, 0) + 1);
}
PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
pq.addAll(counts.values());
int alltime = 0;
int cycle = n + 1;
while (!pq.isEmpty()) {
int worktime = 0;
List<Integer> tmp = new ArrayList<Integer>();
for (int i = 0; i < cycle; i++) {
if (!pq.isEmpty()) {
tmp.add(pq.poll());
worktime++;
}
}
for (int cnt : tmp) {
if (--cnt > 0) {
pq.offer(cnt);
}
}
alltime += !pq.isEmpty() ? cycle : worktime;
}
return alltime;
}
Min/MaxHeap(TreeSet)
BFS + PriorityQueue
Dijkstra
Examples
public int kthSmallest(final int[][] matrix, int k) {
int c = 0;
PriorityQueue<int[]> queue = new PriorityQueue<>(
k, (o1, o2) -> matrix[o1[0]][o1[1]] - matrix[o2[0]][o2[1]]);
queue.offer(new int[] {0, 0});
while (true) {
int[] pair = queue.poll();
if (++c == k) {
return matrix[pair[0]][pair[1]];
}
if (pair[0] == 0 && pair[1] + 1 < matrix[0].length) {
queue.offer(new int[] {0, pair[1] + 1});
}
if (pair[0] + 1 < matrix.length) {
queue.offer(new int[] {pair[0] + 1, pair[1]});
}
}
}
// O(KlogK)
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
PriorityQueue<int[]> que = new PriorityQueue<>((a,b)->a[0]+a[1]-b[0]-b[1]);
List<int[]> res = new ArrayList<>();
if(nums1.length==0 || nums2.length==0 || k==0) return res;
for(int i=0; i<nums1.length && i<k; i++) que.offer(new int[]{nums1[i], nums2[0], 0});
while(k-- > 0 && !que.isEmpty()){
int[] cur = que.poll();
res.add(new int[]{cur[0], cur[1]});
if(cur[2] == nums2.length-1) continue;
que.offer(new int[]{cur[0],nums2[cur[2]+1], cur[2]+1});
}
return res;
}
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> res = new LinkedList<>();
if(nums1==null || nums1.length==0 || nums2==null || nums2.length==0) {
return res;
}
PriorityQueue<int[]> minQ = new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] pair1, int[] pair2) {
return (nums1[pair1[0]]+nums2[pair1[1]])-(nums1[pair2[0]]+nums2[pair2[1]]);
}
});
minQ.offer(new int[]{0, 0});
while (k>0 && !minQ.isEmpty()) {
int[] pair=minQ.poll();
int i = pair[0];
int j = pair[1];
res.add(new int[]{nums1[i], nums2[j]});
k--;
if(j+1<nums2.length) {
minQ.offer(new int[]{i, j+1});
}
if(j==0 && i+1<nums1.length){
minQ.offer(new int[] {i+1, 0});
}
}
return res;
}
