Session 33: Heap using Priority Queue

Original Session

Date: 19 Jan 2025

Topic: Heap using Priority Queue

Concept: Heap Youtube here GFG here

Heap Insert → Inserted at last/leaf node then buble swapped with parent until reach to correct position.

Heap delete → Removed root node, inserted last/leaf node to root then swap with its children until reached its correct position.

MaxHeap: Max at top and descending tree.

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

OR using Comparator

PriorityQueue<Integer> maxHeap = new PriorityQueue<>( (a,b) → b - a);

maxHeap.add(arr[i]);

maxHeap.remove();

maxHeap.peek();

MinHeap: Min at top and ascending tree.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

OR using Comparator

PriorityQueue<Integer> maxHeap = new PriorityQueue<>( (a,b) → a - b);

Trick:

find smallestElement → MaxHeap

fin largestElement → MinHeap

Programs

215. Kth Largest Element in an Array

leetcode here

public int findKthLargest(int[] nums, int k) {
        
        PriorityQueue<Integer> minHeap = new PriorityQueue();

        for (int num: nums) {

            minHeap.add(num);
            if (minHeap.size() > k) {
                minHeap.remove();
            }
        }

        return minHeap.peek();
}

k largest elements

GFG here


List<Integer> kLargest(int nums[], int k) {
        // write code here
        
        PriorityQueue<Integer> minHeap = new PriorityQueue();

        for (int num: nums) {

            minHeap.add(num);
            if (minHeap.size() > k) {
                minHeap.remove();
            }
        } 
        
        List<Integer> list = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            list.add(minHeap.poll());
        }
        Collections.reverse(list);
        return list;
    }

Nearly sorted

GFG here

public void nearlySorted(int[] arr, int k) {
        // code
        
        PriorityQueue<Integer> minHeap = new PriorityQueue();
        
        for (int n: arr) {
            minHeap.add(n);
        }
        
        int index = 0;
        for (int n: arr) {
            if (minHeap.size() > k) {
                arr[index] = minHeap.remove();
                index ++;
            }
        }
        
        while (minHeap.size() > 0) {
            arr[index] = minHeap.remove();
            index ++;
        }
    }

973. K Closest Points to Origin

leetcode here

public int[][] kClosest(int[][] points, int k) {
        
        PriorityQueue<int[]> maxHeap = new PriorityQueue( (a,b)->
            ( distance((int[]) b) - distance((int[]) a))
        );

        for (int[] point: points) {
            maxHeap.add(point);

            if (maxHeap.size() > k) {
                maxHeap.remove();
            }
        }

        int[][] res = new int[maxHeap.size()][2];
        int index = 0;
        while (!maxHeap.isEmpty()) {
            int[] point = maxHeap.remove();
            res[index][0] = point[0];
            res[index][1] = point[1];
            index++;
        }

        return res;
    }

    private int distance(int[] points) {
        return points[0] * points[0] + points[1] * points[1];
    }

871. Minimum Number of Refueling Stops

leetcode here

// Logic is to go to the furthest petrol pump which we can reach with 
// existing fuel.
public int minRefuelStops(int target, int startFuel, int[][] stations) {
        
        PriorityQueue<int[]> pq = new PriorityQueue( (a,b) -> ((int[])b)[1] - ((int[])a)[1]);
        int stops = 0, start = 0, dist = startFuel, n = stations.length;

        while (dist < target) {

            while (start < n && dist >= stations[start][0]) {
                pq.add(stations[start]);
                start ++;
            }

            if (pq.isEmpty()) {
                return -1;
            }

            dist+= pq.remove()[1];
            stops ++;
        }

        return stops;
    }