heap
Min heap: The value of each node is smaller than or equal to the values of its children. The root node holds the minimum value. A min heap always prioritizes the minimum value.
**Max heap:** The value of each node is greater than or equal to the values of its children. The root node holds the maximum value. A max heap always prioritizes the maximum value.
** Priority queue:** A priority queue is an abstract data type retrieves elements based on their custom priority. It is often implemented using a heap for efficiency.
**Add**: This inserts a new element into the heap, which takes O(logn)O(logn)time. **Delete**: This removes the root element and rebalances the heap, taking O(logn)O(logn) time. **Peek**: This retrieves the smallest or largest element in O(1)O(1).
Single Heap Heaps are powerful because they allow us to maintain order (minimum or maximum) without needing full sorting, making operations much faster than other data structures like arrays or linked lists. They are also used when we need to repeatedly access the smallest or largest element in a dataset.
2 Heap One common use case is when we need to efficiently track a dataset’s smallest and largest elements, such as finding the median or balancing data streams. By maintaining one min heap for the smaller half of the data and one max heap for the larger half, we can quickly access the median or adjust the distribution of elements. Another use case is for problems involving intervals or ranges, where one heap can store one set of values (e.g., start times), and the other tracks the complementary set (e.g., end times) to efficiently identify valid intervals or ranges.
Does your problem match this pattern?
Linear data: If the input data is linear, it can be sorted or unsorted. I
A heap efficiently finds the maximum or minimum elements if the data is unsorted. Operations like insertion and deletion take O(logn)O(logn) time, ensuring fast access to the top elements.
If the data is sorted, a heap can still be useful when frequent insertions and deletions are required, as it allows for efficient updates and retrieval of the highest or lowest elements, with both insertion and deletion operations also taking O(logn)O(logn) time.
Stream of data: The input data continuously arrives in real time, often in an unpredictable order, requiring efficient handling and processing as it flows in. Heaps automatically enforce priority ordering (e.g., largest weight, smallest cost, highest frequency). This saves you from manually resorting to or scanning each time your data changes.
Calculation of maxima and minima: The input data can be categorized into two parts, and we need to repeatedly calculate two maxima, two minima, or one maximum and one minimum from each set.
Efficient retrieval of extreme values: The solution needs to retrieve or update the min or max element repeatedly but cannot afford a full sort each time; a heap-based priority queue offers O(logn)O(logn) insertion/removal and O(1)O(1)retrieval.
Custom priority-based selection: The problem involves selecting the next element based on specific priority at each step, such as processing the largest task or earliest event.IPO
An investor is looking to maximize their capital by undertaking a set of profitable projects. Due to limited time and resources, they can complete at most k distinct projects.
There are nn available projects. Each project i has:
A profit of profits[i] earned upon completion. A minimum capital requirement of capital[i] needed to start the project.
The investor starts with an initial capital of c. After completing a project, its profit is immediately added to the investor’s current capital.
The goal is to choose up to k different projects in a way that maximizes the investor’s final capital. Return the maximum capital achievable after completing these projects.
It is guaranteed that the answer fits within a 32-bit signed integer.
public static int maximumCapital(int c, int k, int[] capitals, int[] profits) {
int n = capitals.length;
int currentCapital = c;
PriorityQueue<int[]> capitalMinHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
for (int i = 0; i < n; ++i) {
capitalMinHeap.offer(new int[] { capitals[i], i });
}
PriorityQueue<int[]> profitsMaxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
int i = 0;
while (i < k) {
while (!capitalMinHeap.isEmpty() && capitalMinHeap.peek()[0] <= currentCapital) {
int[] j = capitalMinHeap.poll();
profitsMaxHeap.offer(new int[] { profits[j[1]] });
}
if (profitsMaxHeap.isEmpty()) {
break;
}
int x = profitsMaxHeap.poll()[0];
currentCapital += x;
i++;
}
return currentCapital;
}`
Find Median from Data Stream
Let’s solve the Find Median from Data Stream problem using the Heaps pattern.
Statement
Design a data structure that stores a dynamically changing list of integers and can find the median in constant time, O(1)O(1), as the list grows. To do that, implement a class named MedianOfStream with the following functionality:
Constructor(): Initializes an instance of the class.
insertNum(int num): Adds a new integer num to the data structure.
findMedian(): Returns the median of all integers added so far.
Note: The median is the middle value in a sorted list of integers.
For an odd-sized list (e.g., [4,5,6][4,5,6]), the median is the middle element: 55.
For an even-sized list (e.g., [2,4,6,8][2,4,6,8]), the median is the average of the two middle elements: (4+6)/2=5(4+6)/2=5.class MedianOfStream {
PriorityQueue<Integer> maxHeapForSmallNum;
PriorityQueue<Integer> minHeapForLargeNum;
public MedianOfStream() {
maxHeapForSmallNum = new PriorityQueue<>((a, b) -> b - a);
minHeapForLargeNum = new PriorityQueue<>((a, b) -> a - b);
}
public void insertNum(int num) {
if (maxHeapForSmallNum.isEmpty() || maxHeapForSmallNum.peek() >= num)
maxHeapForSmallNum.add(num);
else
minHeapForLargeNum.add(num);
if (maxHeapForSmallNum.size() > minHeapForLargeNum.size() + 1)
minHeapForLargeNum.add(maxHeapForSmallNum.poll());
else if (maxHeapForSmallNum.size() < minHeapForLargeNum.size())
maxHeapForSmallNum.add(minHeapForLargeNum.poll());
}
public double findMedian() {
if (maxHeapForSmallNum.size() == minHeapForLargeNum.size()) {
return maxHeapForSmallNum.peek() / 2.0 + minHeapForLargeNum.peek() / 2.0;
}
return maxHeapForSmallNum.peek();
}
Sliding Window Median
Let’s solve the Sliding Window Median problem using the Heaps pattern.
Statement
Given an integer array, nums, and an integer, k, there is a sliding window of size k, which is moving from the very left to the very right of the array. We can only see the k numbers in the window. Each time the sliding window moves right by one position.
Given this scenario, return the median of the each window. Answers within 10−510−5 of the actual value will be accepted.
Constraints:
1≤1≤ k ≤≤ nums.length ≤103≤103 −231≤−231≤ nums[i] ≤231−1≤231−1
public static double[] medianSlidingWindow(int[] nums, int k) {
// To store the medians
List<Double> medians = new ArrayList<Double>();</Double></Double>
// To keep track of the numbers that need to be removed from the heaps
HashMap<Integer, Integer> outgoingNum = new HashMap<>();
// Max heap
PriorityQueue<Integer> smallList = new PriorityQueue<>(Collections.reverseOrder());
// Min heap
PriorityQueue<Integer> largeList = new PriorityQueue<>();
// Initialize the max heap
for (int i = 0; i < k; i++)
smallList.offer(nums[i]);
// Transfer the top 50% of the numbers from max heap to min heap
for (int i = 0; i < k / 2; i++)
largeList.offer(smallList.poll());
// Variable to keep the heaps balanced
int balance = 0;
int i = k;
while (true) {
// If the window size is odd
if ((k & 1) == 1)
medians.add((double) (smallList.peek()));
else
medians.add((double) ((long)smallList.peek() + (long)largeList.peek()) * 0.5);
// Break the loop if all elements have been processed
if (i >= nums.length)
break;
// Outgoing number
int outNum = nums[i - k];
// Incoming number
int inNum = nums[i];
i++;
// If the outgoing number is from max heap
if (outNum <= smallList.peek())
balance -= 1;
else
balance += 1;
// Add/Update the outgoing number in the hash map
if (outgoingNum.containsKey(outNum))
outgoingNum.put(outNum, outgoingNum.get(outNum) + 1);
else
outgoingNum.put(outNum, 1);
// If the incoming number is less than the top of the max heap, add it in that heap
// Otherwise, add it in the min heap
if (smallList.size() > 0 && inNum <= smallList.peek()) {
balance += 1;
smallList.offer(inNum);
} else {
balance -= 1;
largeList.offer(inNum);
}
// Re-balance the heaps
if (balance < 0)
smallList.offer(largeList.poll());
else if (balance > 0)
largeList.offer(smallList.poll());
// Since the heaps have been balanced, we reset the balance variable to 0.
// This ensures that the two heaps contain the correct elements for the calculations to be performed on the elements in the next window.
balance = 0;
// Remove invalid numbers present in the hash map from top of max heap
while (smallList.size() > 0 && outgoingNum.containsKey(smallList.peek()) && outgoingNum.get(smallList.peek()) > 0)
outgoingNum.put(smallList.peek(), outgoingNum.get(smallList.poll()) - 1);
// Remove invalid numbers present in the hash map from top of min heap
while (largeList.size() > 0 && outgoingNum.containsKey(largeList.peek()) && outgoingNum.get(largeList.peek()) > 0)
outgoingNum.put(largeList.peek(), outgoingNum.get(largeList.poll()) - 1);
}
double[] arr = medians.stream().mapToDouble(Double::doubleValue).toArray();
return arr;
}Schedule Tasks on Minimum Machines
Let’s solve the Schedule Tasks on Minimum Machines problem using the Heaps pattern.
Statement
We are given an input array, tasks, where tasks[i] =[starti,endi]=[starti,endi] represents the start and end times of nn tasks. Our goal is to schedule these tasks on machines given the following criteria:
A machine can execute only one task at a time. A machine can begin executing a new task immediately after completing the previous one. An unlimited number of machines are available.
Find the minimum number of machines required to complete these nn tasks.
public static int minimumMachines(int[][] tasks) {
Arrays.sort(tasks, Comparator.comparingInt(a -> a[0]));
PriorityQueue<Integer> machines = new PriorityQueue<>();
for (int[] task : tasks) {
int start = task[0];
int end = task[1];
if (!machines.isEmpty() && machines.peek() <= start)
machines.poll();
machines.add(end);
}
return machines.size();
}Meeting Rooms III
**
Let’s solve the Meeting Rooms III problem using the Heaps pattern.**
Statement
Given an integer, rooms, which represents the total number of rooms, where each room is numbered from 0 to rooms - 1. Additionally, you are given a 2D2D integer array called meetings, where each element meetings[i] = [starti,endi][starti,endi] indicates that a meeting will be held in the half-closed interval [starti,endi)[starti,endi). Each startistarti is unique.
Meetings are allocated to rooms in the following manner:
Each meeting will take place in the unused room with the lowest number. If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting. When a room is vacated, the meeting with the earliest original start time is given priority for that room.
Your task is to determine the room number that hosted the most meetings. If there are multiple rooms, return the room with the lowest number.
Note: A half-closed interval [a, b) is the interval between a and b, including a and not including b.
public static int mostBooked(int[][] meetings, int rooms) {
// Count array to track the number of meetings each room holds
int[] count = new int[rooms];
// Create min-heaps for available rooms and used rooms
PriorityQueue<Integer> available = new PriorityQueue<Integer>();
PriorityQueue<long[]> usedRooms = new PriorityQueue<long[]>((a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1]));
// Initialize the available rooms heap
for (int i = 0; i < rooms; i++) {
available.offer(i);
}
// Sort the meetings by their start time
Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0]));
for (int i = 0; i < meetings.length; i++) {
long start_time = meetings[i][0];
long end_time = meetings[i][1];
// Free up rooms that have finished their meetings by the current start time
while (!usedRooms.isEmpty() && usedRooms.peek()[0] <= start_time) {
int room = (int) usedRooms.poll()[1];
available.offer(room);
}
// If no rooms are available, delay the meeting until a room becomes free
if (available.isEmpty()) {
long end = usedRooms.peek()[0];
int room = (int) usedRooms.poll()[1];
end_time = end + (end_time - start_time);
available.offer(room);
}
// Allocate the meeting to the available room with the lowest number
int room = available.poll();
usedRooms.offer(new long[]{end_time, room});
count[room]++;
}
// Room that held the most meetings
int maxMeetingsRoom = 0;
for (int i = 1; i < rooms; i++) {
if (count[i] > count[maxMeetingsRoom]) {
maxMeetingsRoom = i;
}
}
return maxMeetingsRoom;
}Largest Number After Digit Swaps by Parity
You are given a positive integer num. You can swap any two digits of num as long as they share the same parity (both are odd or both are even).
Your task is to return the largest possible value of num after performing any number of such swaps.
Constraints:
1≤1≤ num ≤109≤109
public static int largestInteger(int num) {
// Convert the number into a list of digits
String numStr = Integer.toString(num);
int[] digits = new int[numStr.length()];
for (int i = 0; i < numStr.length(); i++) {
digits[i] = numStr.charAt(i) - ‘0’;
}
// Create two heaps for odd and even digits
PriorityQueue<Integer> oddHeap = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> evenHeap = new PriorityQueue<>(Collections.reverseOrder());
// Fill the heaps
for (int d : digits) {
if (d % 2 == 0) {
evenHeap.add(d); // Use max-heap for even digits
} else {
oddHeap.add(d); // Use max-heap for odd digits
}
}
// Construct the result
StringBuilder result = new StringBuilder();
for (int d : digits) {
if (d % 2 == 0) {
// Get the largest even digit
result.append(evenHeap.poll());
} else {
// Get the largest odd digit
result.append(oddHeap.poll());
}
}
// Convert the result string back to an integer
return Integer.parseInt(result.toString());
}Find Right Interval
You are given an array of intervals where each interval is represented by a pair [starti,endi][starti,endi]. The startistarti values are unique, meaning no two intervals begin at the same time.
The task is to find the right interval for each interval in the list. The right interval for an interval ii is an interval jj such that startj>=endistartj>=endi and startjstartj is minimized (i.e., it is the smallest start time among all valid intervals that is greater than or equal to endiendi). Note that ii may equal jj.
Return an array of right interval indexes for each interval ii. If no right interval exists for interval ii, then put −1−1 at index ii.
public static int[] findRightInterval(int[][] intervals) {
// Initialize the result array with -1, default for no right interval.
int[] result = new int[intervals.length];
Arrays.fill(result, -1);
// Min-heap for end points
PriorityQueue<int[]> endHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
// Populate the endHeap with intervals (end points along with their indices).
for (int i = 0; i < intervals.length; i++) {
endHeap.offer(new int[]{i, intervals[i][1]});
}
// Min-heap for start points
PriorityQueue<int[]> startHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
// Populate the startHeap with intervals (start points along with their indices).
for (int i = 0; i < intervals.length; i++) {
startHeap.offer(new int[]{intervals[i][0], i});
}
// Process each interval based on its end points (from endHeap).
while (!endHeap.isEmpty()) {
// Get the interval with the smallest end point.
int[] endInterval = endHeap.poll();
int index = endInterval[0];
int endValue = endInterval[1];
// Remove all start points from startHeap that are smaller than the current end point.
while (!startHeap.isEmpty() && startHeap.peek()[0] < endValue) {
startHeap.poll();
}
// If startHeap is not empty, the top element is the smallest valid right interval.
if (!startHeap.isEmpty()) {
result[index] = startHeap.peek()[1]; // Get the index of the right interval.
}
}
// Return the result array, which contains the indices of the right intervals or -1 if none exist.
return result;
}
Longest Happy String
A string is considered happy if it meets the following conditions:
It comprises only the characters 'a', 'b', and 'c'.
It does not contain the substrings "aaa", "bbb", or "ccc".
The total occurrences of:
The character 'a' does not exceed a.
The character 'b' does not exceed b.
The character 'c' does not exceed c.You are given three integers, a, b, and c, representing the maximum allowable occurrences of ‘a’, ‘b’, and ‘c’, respectively. Your task is to return the longest possible happy string. If there are multiple valid longest happy strings, return any one of them. If no such string can be formed, return an empty string “”.
public String longestDiverseString(int a, int b, int c)
{
// Max heap to store character counts
PriorityQueue<Pair> pq = new PriorityQueue<>((p1, p2) -> p2.count - p1.count);
// Add characters to heap if their count is greater than 0
if (a > 0) pq.add(new Pair(a, 'a'));
if (b > 0) pq.add(new Pair(b, 'b'));
if (c > 0) pq.add(new Pair(c, 'c'));
StringBuilder result = new StringBuilder();
while (!pq.isEmpty()) {
Pair top = pq.poll();
// Check if adding this character violates the "no three consecutive" rule
int len = result.length();
if (len >= 2 && result.charAt(len - 1) == top.ch && result.charAt(len - 2) == top.ch) {
// If no other characters are available, break
if (pq.isEmpty()) break;
// Use the next most frequent character instead
Pair second = pq.poll();
result.append(second.ch);
// Reduce its count and add it back if more are available
if (--second.count > 0) pq.add(second);
// Push the original character back for future use
pq.add(top);
} else {
// If no violation, add the current character to result
result.append(top.ch);
if (--top.count > 0) pq.add(top);
}
}
return result.toString();
}
// Helper class for storing character counts
static class Pair {
int count;
char ch;
Pair(int count, char ch) {
this.count = count;
this.ch = ch;
}
}
Maximum Average Pass Ratio
A school has several classes of students, each taking a final exam. You are provided a 2D integer array, classes, where classes[i] = [passi, totali]. Here, passi represents the number of students in the ithith class who are expected to pass the exam, and totali represents the total number of students in that class.
Additionally, you are given an integer, extraStudents, which denotes the number of brilliant extra students guaranteed to pass their exams. These students can be assigned to any class, and your goal is to distribute them to maximize the average pass ratio across all classes.
The pass ratio for a class is defined as the ratio of the number of students passing to the total number of students in the class:
Pass Ratio=passi/totali
Pass Ratio=passi/totali
The average pass ratio is the sum of the pass ratios of all classes divided by the total number of classes:
Average Pass Ratio=∑(Pass Ratio of each class)Total Number of Classes
Average Pass Ratio=Total Number of Classes∑(Pass Ratio of each class)
Your task is to return the maximum achievable average pass ratio after assigning all extraStudents to the classes. Answers within 10−510−5 of the actual answer will be accepted.
// Helper function to calculate the pass ratio gain when adding a student
public static double gain(int passes, int total) {
return ((double) (passes + 1) / (total + 1)) - ((double) passes / total);
}
public static double maxAverageRatio(int[][] classes, int extraStudents) {
// Create a max-heap (priority queue) based on the gain value
PriorityQueue<double[]> maxHeap = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));
// Populate the heap with initial values
for (int[] cls : classes) {
maxHeap.offer(new double[]{gain(cls[0], cls[1]), cls[0], cls[1]});
}
// Distribute the extra students
for (int i = 0; i < extraStudents; i++) {
double[] top = maxHeap.poll(); // Extract the class with max gain
int passes = (int) top[1] + 1;
int total = (int) top[2] + 1;
maxHeap.offer(new double[]{gain(passes, total), passes, total});
}
// Calculate the final average pass ratio
double totalRatio = 0.0;
for (double[] cls : maxHeap) {
totalRatio += cls[1] / cls[2];
}
return totalRatio / classes.length;
}The Number of the Smallest Unoccupied Chair
At a party, nn friends, numbered from 00 to n−1n−1, arrive and leave at different times. There are infinitely many chairs, numbered 00 onwards. Each arriving friend sits on the smallest available chair at that moment.
For example, if chairs 00, 11, and 55 are occupied when a friend arrives, they will sit on chair number 22.
When a friend leaves, their chair becomes immediately available. If another friend arrives simultaneously, they can take that chair.
You are given a 00-indexed 2D2D list times, where times[i] =[arrivali,leavingi]=[arrivali,leavingi] represents the arrival and departure times of the ithith friend. All arrival times are unique.
Given an integer target_friend, return the chair number that target_friend will sit on.
public static int smallestChair(int[][] times, int targetFriend) {
List<int[]> sortedFriends = new ArrayList<>();
for (int i = 0; i < times.length; i++) {
sortedFriends.add(new int[]{i, times[i][0], times[i][1]});
}
sortedFriends.sort(Comparator.comparingInt(a -> a[1]));
PriorityQueue<Integer> availableChairs = new PriorityQueue<>();
PriorityQueue<int[]> occupiedChairs = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
int chairIndex = 0;
for (int[] friendData : sortedFriends) {
int friendId = friendData[0];
int arrival = friendData[1];
int leaving = friendData[2];
while (!occupiedChairs.isEmpty() && occupiedChairs.peek()[0] <= arrival) {
int freedChair = occupiedChairs.poll()[1];
availableChairs.offer(freedChair);
}
int assignedChair;
if (!availableChairs.isEmpty()) {
assignedChair = availableChairs.poll();
} else {
assignedChair = chairIndex;
chairIndex++;
}
occupiedChairs.offer(new int[]{leaving, assignedChair});
if (friendId == targetFriend) {
return assignedChair;
}
}
return -1;
}
