Heap/Priority Queue Questions for Placement 2026 (with Solutions)

Last Updated: March 2026

---

Overview

Heaps are specialized tree-based data structures that satisfy the heap property. A Min-Heap ensures the parent node is smaller than or equal to its children, while a Max-Heap ensures the parent is greater than or equal to its children. Priority Queues, typically implemented using heaps, are essential for scheduling, resource allocation, and optimization problems.

Companies Focused on Heap/Priority Queue

• Google: Median finder, merge k sorted arrays, meeting rooms
• Amazon: Top K frequent elements, task scheduler
• Microsoft: Sliding window median, k closest points
• Meta: Find median from data stream, sky line problem
• Netflix: Content recommendation using priority queues
• Uber: Driver-rider matching with priority scoring

---

Core Concepts

Binary Heap Properties

For a node at index i in array representation:
- Parent index: (i - 1) // 2
- Left child: 2 * i + 1
- Right child: 2 * i + 2

Min-Heap Property: parent <= children
Max-Heap Property: parent >= children

Visual Representation of Min-Heap:

        1          <- Root (minimum element)
       / \
      3   5
     / \  / \
    7  9 8  10

Heap Operations

Operation	Time Complexity	Description
Insert	O(log n)	Add element and heapify up
Extract Min/Max	O(log n)	Remove root and heapify down
Peek	O(1)	View root element
Build Heap	O(n)	Convert array to heap
Heapify	O(log n)	Maintain heap property

Types of Heaps

1. Binary Heap: Complete binary tree, array-based
2. Fibonacci Heap: Advanced heap with amortized O(1) insert
3. Binomial Heap: Supports efficient union operation
4. Pairing Heap: Simple and efficient in practice

---

20 Frequently Asked Coding Questions

---

Question 1: Implement Min Heap from Scratch

Problem: Implement a min heap with insert, extract_min, and peek operations.

class MinHeap:
    def __init__(self):
        self.heap = []
    
    def parent(self, i):
        return (i - 1) // 2
    
    def left_child(self, i):
        return 2 * i + 1
    
    def right_child(self, i):
        return 2 * i + 2
    
    def insert(self, key):
        self.heap.append(key)
        self._heapify_up(len(self.heap) - 1)
    
    def _heapify_up(self, i):
        while i > 0 and self.heap[self.parent(i)] > self.heap[i]:
            self.heap[i], self.heap[self.parent(i)] = \
                self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)
    
    def extract_min(self):
        if not self.heap:
            return None
        
        min_val = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        
        if self.heap:
            self._heapify_down(0)
        
        return min_val
    
    def _heapify_down(self, i):
        min_idx = i
        left = self.left_child(i)
        right = self.right_child(i)
        
        if left < len(self.heap) and self.heap[left] < self.heap[min_idx]:
            min_idx = left
        
        if right < len(self.heap) and self.heap[right] < self.heap[min_idx]:
            min_idx = right
        
        if i != min_idx:
            self.heap[i], self.heap[min_idx] = self.heap[min_idx], self.heap[i]
            self._heapify_down(min_idx)
    
    def peek(self):
        return self.heap[0] if self.heap else None
    
    def size(self):
        return len(self.heap)

# Driver Code
heap = MinHeap()
heap.insert(3)
heap.insert(1)
heap.insert(4)
heap.insert(1)
heap.insert(5)
print(heap.peek())         # Output: 1
print(heap.extract_min())  # Output: 1
print(heap.extract_min())  # Output: 1
print(heap.peek())         # Output: 3

Time Complexity: Insert O(log n), Extract O(log n), Peek O(1)
Space Complexity: O(n)

---

Question 2: Kth Largest Element in an Array

Problem: Find the kth largest element in an unsorted array.

import heapq

class Solution:
    def findKthLargest(self, nums, k):
        # Use min-heap of size k
        min_heap = nums[:k]
        heapq.heapify(min_heap)
        
        for num in nums[k:]:
            if num > min_heap[0]:
                heapq.heapreplace(min_heap, num)
        
        return min_heap[0]
    
    # Alternative: QuickSelect approach (average O(n))
    def findKthLargestQuickSelect(self, nums, k):
        def partition(left, right, pivot_idx):
            pivot = nums[pivot_idx]
            # Move pivot to end
            nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
            store_idx = left
            
            for i in range(left, right):
                if nums[i] < pivot:
                    nums[store_idx], nums[i] = nums[i], nums[store_idx]
                    store_idx += 1
            
            # Move pivot to final place
            nums[right], nums[store_idx] = nums[store_idx], nums[right]
            return store_idx
        
        def select(left, right, k_smallest):
            if left == right:
                return nums[left]
            
            pivot_idx = (left + right) // 2
            pivot_idx = partition(left, right, pivot_idx)
            
            if k_smallest == pivot_idx:
                return nums[k_smallest]
            elif k_smallest < pivot_idx:
                return select(left, pivot_idx - 1, k_smallest)
            else:
                return select(pivot_idx + 1, right, k_smallest)
        
        return select(0, len(nums) - 1, len(nums) - k)

# Driver Code
nums = [3, 2, 1, 5, 6, 4]
k = 2
sol = Solution()
print(sol.findKthLargest(nums, k))  # Output: 5

Time Complexity: O(n log k)
Space Complexity: O(k)

---

Question 3: Merge K Sorted Arrays

Problem: Merge k sorted arrays into one sorted array.

import heapq

class Solution:
    def mergeKArrays(self, arr, k):
        """
        arr: list of k sorted arrays
        k: number of arrays
        """
        result = []
        # Min heap: (value, array_index, element_index)
        min_heap = []
        
        # Push first element of each array
        for i in range(k):
            if arr[i]:
                heapq.heappush(min_heap, (arr[i][0], i, 0))
        
        while min_heap:
            val, arr_idx, elem_idx = heapq.heappop(min_heap)
            result.append(val)
            
            # Push next element from same array
            if elem_idx + 1 < len(arr[arr_idx]):
                next_val = arr[arr_idx][elem_idx + 1]
                heapq.heappush(min_heap, (next_val, arr_idx, elem_idx + 1))
        
        return result

# Driver Code
arr = [
    [1, 3, 5, 7],
    [2, 4, 6, 8],
    [0, 9, 10, 11]
]
k = 3
sol = Solution()
print(sol.mergeKArrays(arr, k))
# Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Time Complexity: O(N log k) where N = total elements
Space Complexity: O(k)

---

Question 4: Top K Frequent Elements

Problem: Return the k most frequent elements.

from collections import Counter
import heapq

class Solution:
    def topKFrequent(self, nums, k):
        # Count frequencies
        freq_map = Counter(nums)
        
        # Use min-heap based on frequency
        min_heap = []
        
        for num, freq in freq_map.items():
            heapq.heappush(min_heap, (freq, num))
            if len(min_heap) > k:
                heapq.heappop(min_heap)
        
        # Extract elements
        return [num for freq, num in min_heap]
    
    # Alternative: Bucket Sort approach (O(n))
    def topKFrequentBucket(self, nums, k):
        freq_map = Counter(nums)
        
        # Bucket by frequency
        buckets = [[] for _ in range(len(nums) + 1)]
        for num, freq in freq_map.items():
            buckets[freq].append(num)
        
        result = []
        for i in range(len(buckets) - 1, 0, -1):
            for num in buckets[i]:
                result.append(num)
                if len(result) == k:
                    return result
        
        return result

# Driver Code
nums = [1, 1, 1, 2, 2, 3]
k = 2
sol = Solution()
print(sol.topKFrequent(nums, k))  # Output: [1, 2]

Time Complexity: O(n log k)
Space Complexity: O(n)

---

Question 5: Find Median from Data Stream

Problem: Design a data structure to find the median of a stream of numbers.

import heapq

class MedianFinder:
    def __init__(self):
        # Max heap for lower half (store negatives)
        self.small = []
        # Min heap for upper half
        self.large = []
    
    def addNum(self, num: int) -> None:
        # Add to max heap (small)
        heapq.heappush(self.small, -num)
        
        # Balance: move largest from small to large
        if self.small and self.large and (-self.small[0]) > self.large[0]:
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        
        # Balance sizes
        if len(self.small) > len(self.large) + 1:
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        
        if len(self.large) > len(self.small):
            val = heapq.heappop(self.large)
            heapq.heappush(self.small, -val)
    
    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

# Driver Code
medianFinder = MedianFinder()
medianFinder.addNum(1)
medianFinder.addNum(2)
print(medianFinder.findMedian())  # Output: 1.5
medianFinder.addNum(3)
print(medianFinder.findMedian())  # Output: 2.0

Time Complexity: Add O(log n), Find O(1)
Space Complexity: O(n)

---

Question 6: K Closest Points to Origin

Problem: Return the k closest points to the origin (0, 0).

import heapq

class Solution:
    def kClosest(self, points, k):
        # Max heap approach (store negative distances)
        max_heap = []
        
        for x, y in points:
            dist = x * x + y * y  # Squared distance (avoid sqrt)
            heapq.heappush(max_heap, (-dist, x, y))
            
            if len(max_heap) > k:
                heapq.heappop(max_heap)
        
        return [[x, y] for dist, x, y in max_heap]

# Driver Code
points = [[1, 3], [-2, 2], [5, 8], [0, 1]]
k = 2
sol = Solution()
print(sol.kClosest(points, k))  # Output: [[0, 1], [-2, 2]]

Time Complexity: O(n log k)
Space Complexity: O(k)

---

Question 7: Task Scheduler

Problem: Find the least number of intervals to complete all tasks with cooling time.

from collections import Counter
import heapq

class Solution:
    def leastInterval(self, tasks, n):
        # Count task frequencies
        freq = Counter(tasks)
        
        # Max heap of frequencies
        max_heap = [-count for count in freq.values()]
        heapq.heapify(max_heap)
        
        time = 0
        # Queue for tasks in cooldown: (available_time, count)
        queue = []
        
        while max_heap or queue:
            time += 1
            
            if max_heap:
                count = 1 + heapq.heappop(max_heap)  # Increment since negative
                if count != 0:
                    queue.append((time + n, count))
            
            # Check if any task is ready
            if queue and queue[0][0] == time:
                _, count = queue.pop(0)
                heapq.heappush(max_heap, count)
        
        return time

# Driver Code
tasks = ["A", "A", "A", "B", "B", "B"]
n = 2
sol = Solution()
print(sol.leastInterval(tasks, n))  # Output: 8 (A -> B -> idle -> A -> B -> idle -> A -> B)

Time Complexity: O(n log k) where k = unique tasks
Space Complexity: O(k)

---

Question 8: Reorganize String

Problem: Rearrange string so no two adjacent characters are the same.

from collections import Counter
import heapq

class Solution:
    def reorganizeString(self, s: str) -> str:
        # Count frequencies
        freq = Counter(s)
        
        # Max heap: (-count, char)
        max_heap = [(-count, char) for char, count in freq.items()]
        heapq.heapify(max_heap)
        
        result = []
        prev_count, prev_char = 0, ''
        
        while max_heap:
            count, char = heapq.heappop(max_heap)
            result.append(char)
            
            # Push previous char back if it still has count
            if prev_count < 0:
                heapq.heappush(max_heap, (prev_count, prev_char))
            
            prev_count, prev_char = count + 1, char
        
        result_str = ''.join(result)
        return result_str if len(result_str) == len(s) else ""

# Driver Code
s = "aab"
sol = Solution()
print(sol.reorganizeString(s))  # Output: "aba"

s2 = "aaab"
print(sol.reorganizeString(s2))  # Output: "" (not possible)

Time Complexity: O(n log k)
Space Complexity: O(k)

---

Question 9: Sliding Window Median

Problem: Find the median of each sliding window of size k.

import heapq

class DualHeap:
    def __init__(self, k):
        self.small = []  # Max heap (negatives)
        self.large = []  # Min heap
        self.delayed = {}  # Delayed deletions
        self.k = k
        self.small_size = 0
        self.large_size = 0
    
    def prune(self, heap):
        while heap:
            num = -heap[0] if heap is self.small else heap[0]
            if num in self.delayed and self.delayed[num] > 0:
                self.delayed[num] -= 1
                heapq.heappop(heap)
            else:
                break
    
    def make_balance(self):
        # Balance sizes
        if self.small_size > self.large_size + 1:
            heapq.heappush(self.large, -heapq.heappop(self.small))
            self.small_size -= 1
            self.large_size += 1
            self.prune(self.small)
        elif self.small_size < self.large_size:
            heapq.heappush(self.small, -heapq.heappop(self.large))
            self.small_size += 1
            self.large_size -= 1
            self.prune(self.large)
    
    def insert(self, num):
        if not self.small or num <= -self.small[0]:
            heapq.heappush(self.small, -num)
            self.small_size += 1
        else:
            heapq.heappush(self.large, num)
            self.large_size += 1
        self.make_balance()
    
    def erase(self, num):
        self.delayed[num] = self.delayed.get(num, 0) + 1
        if num <= -self.small[0]:
            self.small_size -= 1
            if num == -self.small[0]:
                self.prune(self.small)
        else:
            self.large_size -= 1
            if num == self.large[0]:
                self.prune(self.large)
        self.make_balance()
    
    def get_median(self):
        return -self.small[0] if self.k % 2 == 1 else (-self.small[0] + self.large[0]) / 2

class Solution:
    def medianSlidingWindow(self, nums, k):
        dh = DualHeap(k)
        result = []
        
        for i, num in enumerate(nums):
            dh.insert(num)
            
            if i >= k:
                dh.erase(nums[i - k])
            
            if i >= k - 1:
                result.append(dh.get_median())
        
        return result

# Driver Code
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
sol = Solution()
print(sol.medianSlidingWindow(nums, k))  # Output: [1, -1, -1, 3, 5, 6]

Time Complexity: O(n log k)
Space Complexity: O(k)

---

Question 10: Design Twitter

Problem: Design a simplified version of Twitter with post, follow, and getNewsFeed.

import heapq
from collections import defaultdict

class Twitter:
    def __init__(self):
        self.timestamp = 0
        self.tweets = defaultdict(list)  # userId -> [(timestamp, tweetId)]
        self.following = defaultdict(set)  # userId -> {followeeIds}
    
    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets[userId].append((self.timestamp, tweetId))
        self.timestamp -= 1  # Decrease for max heap simulation
    
    def getNewsFeed(self, userId: int):
        # Min heap to get 10 most recent tweets
        min_heap = []
        
        # Add user's own tweets
        self._add_tweets_to_heap(userId, min_heap)
        
        # Add followees' tweets
        for followeeId in self.following[userId]:
            self._add_tweets_to_heap(followeeId, min_heap)
        
        # Extract results
        result = []
        while min_heap and len(result) < 10:
            timestamp, tweetId, followeeId, tweetIdx = heapq.heappop(min_heap)
            result.append(tweetId)
            
            # Add next tweet from same user if exists
            if tweetIdx + 1 < len(self.tweets[followeeId]):
                next_ts, next_tid = self.tweets[followeeId][tweetIdx + 1]
                heapq.heappush(min_heap, (next_ts, next_tid, followeeId, tweetIdx + 1))
        
        return result
    
    def _add_tweets_to_heap(self, userId, heap):
        if self.tweets[userId]:
            idx = len(self.tweets[userId]) - 1
            timestamp, tweetId = self.tweets[userId][idx]
            heapq.heappush(heap, (timestamp, tweetId, userId, idx))
    
    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId != followeeId:
            self.following[followerId].add(followeeId)
    
    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].discard(followeeId)

# Driver Code
twitter = Twitter()
twitter.postTweet(1, 5)
twitter.postTweet(1, 3)
print(twitter.getNewsFeed(1))  # Output: [3, 5]
twitter.follow(1, 2)
twitter.postTweet(2, 6)
print(twitter.getNewsFeed(1))  # Output: [6, 3, 5]

Time Complexity: Post O(1), GetNewsFeed O(k log k)
Space Complexity: O(users × tweets)

---

Question 11: Minimum Cost to Connect Sticks

Problem: Connect sticks with minimum cost (Huffman coding variant).

import heapq

class Solution:
    def connectSticks(self, sticks):
        if len(sticks) <= 1:
            return 0
        
        heapq.heapify(sticks)
        total_cost = 0
        
        while len(sticks) > 1:
            # Connect two smallest sticks
            a = heapq.heappop(sticks)
            b = heapq.heappop(sticks)
            cost = a + b
            total_cost += cost
            heapq.heappush(sticks, cost)
        
        return total_cost

# Driver Code
sticks = [2, 4, 3]
sol = Solution()
print(sol.connectSticks(sticks))  # Output: 14 (2+3=5, 5+4=9, total=14)

Time Complexity: O(n log n)
Space Complexity: O(n)

---

Question 12: Sort Characters By Frequency

Problem: Sort string in decreasing order based on character frequency.

from collections import Counter
import heapq

class Solution:
    def frequencySort(self, s: str) -> str:
        # Count frequencies
        freq = Counter(s)
        
        # Build max heap
        max_heap = [(-count, char) for char, count in freq.items()]
        heapq.heapify(max_heap)
        
        result = []
        while max_heap:
            count, char = heapq.heappop(max_heap)
            result.append(char * (-count))
        
        return ''.join(result)
    
    # Alternative: Bucket sort (O(n))
    def frequencySortBucket(self, s: str) -> str:
        freq = Counter(s)
        
        # Bucket by frequency
        buckets = [[] for _ in range(len(s) + 1)]
        for char, count in freq.items():
            buckets[count].append(char)
        
        result = []
        for i in range(len(buckets) - 1, 0, -1):
            for char in buckets[i]:
                result.append(char * i)
        
        return ''.join(result)

# Driver Code
s = "tree"
sol = Solution()
print(sol.frequencySort(s))  # Output: "eert" or "eetr"

Time Complexity: O(n log k)
Space Complexity: O(n)

---

Question 13: Find K Pairs with Smallest Sums

Problem: Find k pairs with smallest sums from two sorted arrays.

import heapq

class Solution:
    def kSmallestPairs(self, nums1, nums2, k):
        if not nums1 or not nums2:
            return []
        
        result = []
        # Min heap: (sum, i, j) where i is index in nums1, j in nums2
        min_heap = [(nums1[0] + nums2[0], 0, 0)]
        visited = set([(0, 0)])
        
        while min_heap and len(result) < k:
            sum_val, i, j = heapq.heappop(min_heap)
            result.append([nums1[i], nums2[j]])
            
            # Push next pairs
            if i + 1 < len(nums1) and (i + 1, j) not in visited:
                heapq.heappush(min_heap, (nums1[i + 1] + nums2[j], i + 1, j))
                visited.add((i + 1, j))
            
            if j + 1 < len(nums2) and (i, j + 1) not in visited:
                heapq.heappush(min_heap, (nums1[i] + nums2[j + 1], i, j + 1))
                visited.add((i, j + 1))
        
        return result

# Driver Code
nums1 = [1, 7, 11]
nums2 = [2, 4, 6]
k = 3
sol = Solution()
print(sol.kSmallestPairs(nums1, nums2, k))
# Output: [[1, 2], [1, 4], [1, 6]]

Time Complexity: O(k log k)
Space Complexity: O(k)

---

Question 14: Meeting Rooms II

Problem: Find minimum number of meeting rooms required.

import heapq

class Solution:
    def minMeetingRooms(self, intervals):
        if not intervals:
            return 0
        
        # Sort by start time
        intervals.sort(key=lambda x: x[0])
        
        # Min heap of end times
        min_heap = [intervals[0][1]]
        
        for i in range(1, len(intervals)):
            start, end = intervals[i]
            
            # If earliest ending meeting finishes before current starts
            if min_heap[0] <= start:
                heapq.heappop(min_heap)
            
            heapq.heappush(min_heap, end)
        
        return len(min_heap)

# Driver Code
intervals = [[0, 30], [5, 10], [15, 20]]
sol = Solution()
print(sol.minMeetingRooms(intervals))  # Output: 2

Time Complexity: O(n log n)
Space Complexity: O(n)

---

Question 15: Ugly Number II

Problem: Find the nth ugly number (prime factors only 2, 3, 5).

import heapq

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        seen = {1}
        min_heap = [1]
        
        for _ in range(n):
            ugly = heapq.heappop(min_heap)
            
            for factor in [2, 3, 5]:
                next_ugly = ugly * factor
                if next_ugly not in seen:
                    seen.add(next_ugly)
                    heapq.heappush(min_heap, next_ugly)
        
        return ugly
    
    # Optimized DP approach
    def nthUglyNumberDP(self, n: int) -> int:
        ugly = [1] * n
        i2 = i3 = i5 = 0
        
        for i in range(1, n):
            next2, next3, next5 = 2 * ugly[i2], 3 * ugly[i3], 5 * ugly[i5]
            ugly[i] = min(next2, next3, next5)
            
            if ugly[i] == next2:
                i2 += 1
            if ugly[i] == next3:
                i3 += 1
            if ugly[i] == next5:
                i5 += 1
        
        return ugly[-1]

# Driver Code
n = 10
sol = Solution()
print(sol.nthUglyNumber(n))  # Output: 12

Time Complexity: O(n log n) for heap, O(n) for DP
Space Complexity: O(n)

---

Question 16: Cheapest Flights Within K Stops

Problem: Find cheapest price from src to dst with at most k stops using modified Dijkstra.

import heapq
from collections import defaultdict

class Solution:
    def findCheapestPrice(self, n, flights, src, dst, k):
        # Build graph
        graph = defaultdict(list)
        for u, v, price in flights:
            graph[u].append((v, price))
        
        # (cost, stops, node)
        min_heap = [(0, 0, src)]
        
        while min_heap:
            cost, stops, node = heapq.heappop(min_heap)
            
            if node == dst:
                return cost
            
            if stops > k:
                continue
            
            for neighbor, price in graph[node]:
                new_cost = cost + price
                heapq.heappush(min_heap, (new_cost, stops + 1, neighbor))
        
        return -1

# Driver Code
n = 4
flights = [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]]
src, dst, k = 0, 3, 1
sol = Solution()
print(sol.findCheapestPrice(n, flights, src, dst, k))  # Output: 700

Time Complexity: O(E × k log(V × k))
Space Complexity: O(V × k)

---

Question 17: Find Kth Smallest Pair Distance

Problem: Find kth smallest distance among all pairs in array.

import heapq

class Solution:
    def smallestDistancePair(self, nums, k):
        nums.sort()
        n = len(nums)
        
        # Binary search on distance
        left, right = 0, nums[-1] - nums[0]
        
        while left < right:
            mid = left + (right - left) // 2
            count = self._count_pairs(nums, mid)
            
            if count < k:
                left = mid + 1
            else:
                right = mid
        
        return left
    
    def _count_pairs(self, nums, max_dist):
        count = 0
        j = 0
        for i in range(len(nums)):
            while j < len(nums) and nums[j] - nums[i] <= max_dist:
                j += 1
            count += j - i - 1
        return count

# Driver Code
nums = [1, 3, 1]
k = 1
sol = Solution()
print(sol.smallestDistancePair(nums, k))  # Output: 0

Time Complexity: O(n log(max_distance))
Space Complexity: O(1)

---

Question 18: Car Pooling

Problem: Determine if car can accommodate all trips given capacity.

import heapq

class Solution:
    def carPooling(self, trips, capacity):
        # Sort by start location
        trips.sort(key=lambda x: x[1])
        
        # Min heap of (end_location, passengers)
        min_heap = []
        current_passengers = 0
        
        for passengers, start, end in trips:
            # Remove passengers who have reached destination
            while min_heap and min_heap[0][0] <= start:
                current_passengers -= min_heap[0][1]
                heapq.heappop(min_heap)
            
            # Add current passengers
            current_passengers += passengers
            if current_passengers > capacity:
                return False
            
            heapq.heappush(min_heap, (end, passengers))
        
        return True
    
    # Alternative: Timeline approach (O(n log n))
    def carPoolingTimeline(self, trips, capacity):
        timeline = []
        for passengers, start, end in trips:
            timeline.append((start, passengers))
            timeline.append((end, -passengers))
        
        timeline.sort()
        
        current = 0
        for _, passengers in timeline:
            current += passengers
            if current > capacity:
                return False
        
        return True

# Driver Code
trips = [[2, 1, 5], [3, 3, 7]]
capacity = 4
sol = Solution()
print(sol.carPooling(trips, capacity))  # Output: False

Time Complexity: O(n log n)
Space Complexity: O(n)

---

Question 19: Single Threaded CPU

Problem: Simulate a single-threaded CPU processing tasks.

import heapq

class Solution:
    def getOrder(self, tasks):
        # Add index to tasks and sort by enqueue time
        indexed_tasks = [(enqueue, process, i) for i, (enqueue, process) in enumerate(tasks)]
        indexed_tasks.sort()
        
        result = []
        min_heap = []  # (processing_time, index)
        time = 0
        i = 0
        n = len(tasks)
        
        while len(result) < n:
            # Add all available tasks to heap
            while i < n and indexed_tasks[i][0] <= time:
                enqueue, process, idx = indexed_tasks[i]
                heapq.heappush(min_heap, (process, idx))
                i += 1
            
            if min_heap:
                process, idx = heapq.heappop(min_heap)
                time += process
                result.append(idx)
            else:
                # Jump to next available task
                time = indexed_tasks[i][0]
        
        return result

# Driver Code
tasks = [[1, 2], [2, 4], [3, 2], [4, 1]]
sol = Solution()
print(sol.getOrder(tasks))  # Output: [0, 2, 3, 1]

Time Complexity: O(n log n)
Space Complexity: O(n)

---

Question 20: Maximal Score After Applying K Operations

Problem: Maximize score by picking largest element k times.

import heapq
import math

class Solution:
    def maxKelements(self, nums, k):
        # Max heap (store negatives)
        max_heap = [-num for num in nums]
        heapq.heapify(max_heap)
        
        score = 0
        
        for _ in range(k):
            # Pick largest
            largest = -heapq.heappop(max_heap)
            score += largest
            
            # Replace with ceil(largest / 3)
            new_val = math.ceil(largest / 3)
            heapq.heappush(max_heap, -new_val)
        
        return score

# Driver Code
nums = [10, 10, 10, 10, 10]
k = 5
sol = Solution()
print(sol.maxKelements(nums, k))  # Output: 50

Time Complexity: O(k log n)
Space Complexity: O(n)

---

MCQ Questions

Question 1

What is the time complexity of building a heap from an array of n elements?

• A) O(n log n)
• B) O(n²)
• C) O(n)
• D) O(log n)

---

Question 2

In a min-heap, where is the maximum element located?

• A) Root
• B) Always at index 1
• C) One of the leaf nodes
• D) Cannot be determined

---

Question 3

What is the height of a binary heap with n elements?

• A) O(n)
• B) O(log n)
• C) O(√n)
• D) O(1)

---

Question 4

Which data structure is best for implementing a priority queue?

• A) Array
• B) Linked List
• C) Binary Heap
• D) Stack

---

Question 5

The median of a stream can be efficiently found using:

• A) Single max-heap
• B) Single min-heap
• C) Two heaps (max-heap + min-heap)
• D) Binary Search Tree

---

Interview Tips for Heap/Priority Queue

1. Know when to use heaps:

   • Finding K largest/smallest elements
   • Merge K sorted lists/arrays
   • Scheduling problems
   • Median maintenance
   • Huffman coding

2. Common patterns:

   • K-way merge pattern
   • Two heaps for median
   • Top K elements pattern
   • Greedy with priority queue

3. Python heapq tips:

   • It's a min-heap by default
   • Use negative values for max-heap behavior
   • heapify() converts list to heap in O(n)
   • nlargest() and nsmallest() for quick access

4. Optimization techniques:

   • Lazy deletion for sliding window
   • Custom comparison with tuples
   • Bucket sort as alternative for frequency problems

5. Edge cases:

   • Empty input
   • Single element
   • All elements equal
   • Duplicate elements

---

Frequently Asked Questions

Q1: What is the difference between a heap and a priority queue?

A: A priority queue is an abstract data type (ADT) that defines operations. A heap is a specific data structure implementation commonly used to implement priority queues efficiently.

Q2: Why is heapify O(n) and not O(n log n)?

A: While n/2 elements might need to heapify down, most nodes are at lower levels with less distance to sink. The mathematical series converges to O(n).

Q3: Can heaps have duplicate values?

A: Yes, heaps can contain duplicate values. The heap property only concerns the relationship between parent and child, not uniqueness.

Q4: How do you implement a max-heap in Python?

A: Python's heapq is a min-heap. To simulate a max-heap, store negative values and negate them when extracting.

Q5: When should I use heap vs sorting?

A: Use heaps when you need only K elements from a large dataset (O(n log k) vs O(n log n)). Use sorting when you need the full ordered list.

---

Practice these heap problems to master priority queue concepts for your interviews. Focus on recognizing when a heap is the right tool for the problem.