I am Harisai

A priority queue is an abstract data type that stores elements with associated priorities, where the element with the highest priority is always served first. It differs from a regular queue in that elements are not processed in a First-In, First-Out (FIFO) order but are instead served based on their priority value.

Priority queues are implemented using data structures like a binary heap, which can be a min-heap for the smallest element or a max-heap for the largest, and are utilised in algorithms such as Dijkstra’s shortest path algorithm.

Characteristics

• Priority-based processing: Elements are retrieved based on their assigned priority, not their arrival order.
• Highest priority first: The element with the highest priority is always removed first.
• Equal priority handling: If two elements have the same priority, the one that arrived earlier is typically processed first.
• Dynamic maintenance: The queue is reorganized after insertions or deletions to maintain the priority order.

Example 1: ☁️ Priority Queues with Azure Service Bus: Process What Matters First

Why does it matter? Not all work is equal. High-priority tasks (VIP clients, compliance flows, critical ops) shouldn’t wait behind bulk jobs. A priority queue ensures “urgent first, bulk later,” protecting SLAs and user experience.

Example 2: ✈️ airline check‑in where premium flyers are served before standard passengers.

In an airport queue, travellers arrive continuously, but not all tickets are equal. A priority queue model checks in by always serving premium status or business-class passengers ahead of economy, regardless of arrival order.

Example 3: 💻 Operating System Task Scheduling Your computer doesn’t handle all tasks equally; it prioritizes system-critical processes over background downloads. Even if you queue a large file transfer first, the CPU prioritizes mouse movements or UI updates so your screen doesn’t freeze. This ensures urgent tasks get resources immediately.

Implementations of Priority Queue

• Unsorted Array 🐢

  The simplest “lazy” approach where you just push() elements into an array as they arrive. It’s very fast to add items, but slow to remove them because you have to search the entire list every time to find the highest priority.

• Sorted Array 📉

  Here, you place elements in their correct position immediately to keep the array sorted by priority. This makes retrieving the top item instant, but adding new items takes longer because you have to shift existing elements to make room.

• Binary Heap (The Gold Standard) ⚡

  This is the most efficient and common implementation, using a tree structure (mapped to an array) to organize data. It offers the perfect balance, making both insertion and removal operations very fast O(log n). The only drawback is the lack of a native stable algorithm.

• External Libraries 📦

  Since native JavaScript doesn’t have a built-in PriorityQueue class (unlike Java or Python), developers often skip writing raw code and use optimized packages like datastructures-js or google-closure-library for production apps.

🤔 Heap vs. Priority Queue: What’s the difference?

Think of a Priority Queue as a “Job Description” 📄 and a Heap as the best “Employee” 👷 for the role. A Priority Queue is an Abstract Data Type (ADT), which means it only defines the behaviour (e.g., “I must always fetch the highest priority item next”).

1. It doesn’t care how the data is stored behind the scenes. A Heap, on the other hand, is a specific, concrete Data Structure.
2. While you could implement a Priority Queue using a simple array or a linked list, we almost always use a Heap because it is the most efficient way to handle the job without slowing down as the queue grows.

A Few Leetcode Problems

K^th Largest element in an array

Approach 1: Using an Array

Intuition: Maintain an array of size k that always holds the current k largest numbers seen. Track the index of the smallest element inside this array; that element represents the current k-th largest. When a new number arrives that’s larger than this minimum, replace it and recompute the minimum.

Implementation

var findKthLargest = function(nums, k) {
    let top = [];
    let minIndex = -1;

    for (let i = 0; i < nums.length; i++) {
        const val = nums[i];
        if (top.length < k) {
            top.push(val);
            if (top.length === k) {
                minIndex = 0;
                for (let t = 1; t < k; t++) {
                     if (top[t] < top[minIndex]) minIndex = t;
                }
            }
        } else {
            if (val > top[minIndex]) {
                top[minIndex] = val;
                // recompute minIndex
                minIndex = 0;
                for (let t = 1; t < k; t++) {
                    if (top[t] < top[minIndex]) minIndex = t;
                }
            }
        }
    }
    return top.length === k ? top[minIndex] : null;
};

• Time Complexity: O(Nk)
• Space Complexity: O(k)

Why is it O(Nk)?

1. Outer Loop (N): You iterate through every number in the input array nums.
2. Inner Operation (k): You maintain a simple array (top) of size k. When a new number is added, you perform a linear scan for (let t = 1; t < k; t++) to find the new minimum index.
3. Calculation: N times * K scan cost = O(Nk)

Worst-Case Scenario

• Input: The array is sorted in ascending order.
• Effect: Every single element is larger than the current minimum in top. The code is forced to re-scan the top array (k times) for every single index of N.

Comparison to Optimal Solution:

This approach is slow for large k because it uses a standard array scan.

• Current (Array Scan): O(N k)
• Optimal (Min-Heap): O(N log k)

  (A Heap finds/updates the minimum in logarithmic time rather than linear time.)

Approach 2: Using PriorityQueue

Key idea: Maintain a min-heap (size at most k). The heap always contains the k largest elements seen so far. The smallest among these k elements (heap root) is the k-th largest overall.

Algorithm:

1. Initialize an empty min-heap.
2. For each number x in nums:
   • Push x into the heap.
   • If heap size exceeds k, pop the smallest (root).
3. After processing all elements, the heap root is the k-th largest.

Why it works?

• At any time, the heap stores the best k candidates (largest k numbers).
• Keeping only k elements ensures O(n log k) time complexity.
• The smallest among these k candidates is exactly the k-th largest.

Complexity:

• Time: O(n log k) — each insert/pop is O(log k), done n times.
• Space: O(k) — heap stores at most k elements.

Correctness invariants:

• Size invariant: heap.size() ≤ k.
• Order invariant: heap contains the k largest values seen so far.
• Result invariant: after full scan, heap.min = k-th largest.

Edge cases:

• k = 1 → returns the maximum element.
• k = nums.length → returns the minimum element.
• Duplicates are naturally handled; relative order does not matter.
• Validate k: 1 ≤ k ≤ nums.length; otherwise throw/return error.

Alternate approaches:

• Quick-select (average O(n), worst O(n²)) for in-place selection; good when minimizing extra space.
• Sort descending and pick index k-1 (O(n log n)); simplest but slower than heap/quick-select for large n.

 K^th largest element in stream

🧠 Core Idea: Kth largest means:

• If k = 3 → we want the 3rd largest at any time.
• Maintain a min-heap of size k that always stores the top k largest elements seen so far.
• The root of this min-heap will always be the k^th largest.

Why min-heap?

Because the smallest among the top k elements (i.e., the kth largest) should always sit at the root.

⚙️ Constructor Logic (K^thLargest)

• Create an empty MinPriorityQueue (min-heap).
• Save k.
• Insert initial numbers one by one using this.add().

That ensures the heap is always in a correct state.

🧩 How add(val) Works?

1. Insert the new value into heap → heap.enqueue(val).
2. If heap grows bigger than k → remove the smallest → heap.dequeue().

   This ensures heap size NEVER exceeds k.

3. After balancing, the heap.front() (min element) is the kth largest.

🧠 Why removing the smallest works?

A min-heap keeps the smallest at the top. If size > k → we remove the root → the smallest among the elements. So only the k largest elements remain inside.

Thus, after every insertion:

• The root = smallest among the top k = kth largest overall.

Implementation

var KthLargest = function(k, nums) {
    this.heap = new MinPriorityQueue();
    this.k = k;

    for(let i=0; i < nums.length; i++){
        this.add(nums[i])
    }
    return null
};

KthLargest.prototype.add = function(val) {
    this.heap.enqueue(val);
    if (this.heap.size() > this.k){
        this.heap.dequeue()
    }
    return this.heap.front()
};

⏱️ Time Complexity

Each add:

• enqueue → O(log k)
• maybe dequeue → O(log k)

So every update is very fast, even for huge streams.

💡 Important Points

• The heap stores only k elements, not the whole stream.
• this.heap.front() returns an object, usually { element: value } depending on the library.

But conceptually, it is the K^th largest value. Using a min-heap is the trick — max-heap would be inefficient here.

🪨 Last Stone Weight

🧠 Core Idea: The problem asks us to repeatedly smash the two heaviest stones together until only one (or none) remains.

• To do this efficiently, we need to constantly identify the two largest values in a collection that is changing every time we perform an operation.
• A Max-Priority Queue (Max-Heap) is the ideal tool here because it gives us instant access to the maximum element and re-organizes itself in O(log n) time after we add the “leftover” stone.

⚙️ The “Smash” Logic

1. Heapify: Put all stones into a Max-Heap.
2. Smash: While there is more than one stone:
   • Pull the heaviest stone (y).
   • Pull the second heaviest stone (x).
   • If x ≠ y, the new stone weight is y – x. Push this back into the heap.
   • If x = y, both are destroyed (do nothing).
3. Result: If one stone is left, return its weight; otherwise, return 0.

🧩 Why Max-Heap?

If we used a Sorted Array, we would have to re-sort or shift elements every time we added a leftover stone (O(n) per smash). With a Max-Heap, the “re-sorting” happens automatically in O(log n) time, making the algorithm significantly faster for large sets of stones.

⏱️ Complexity Analysis

• Time Complexity: O(n log n)
  • Building the initial heap takes O(n log n) (or O(n) if using a heapify-in-place method).
  • In each step of the while loop, we perform dequeue and enqueue operations which take O(log n). Since we reduce the number of stones in each step, we do this at most n times.
• Space Complexity: O(n)
  • We store all n stones in the Priority Queue.

💡 Key Takeaways

• Dynamic Sorting: Use a Priority Queue whenever you need to find the “extremum” (min or max) repeatedly while the data set is being modified.
• Handling the “Empty” Case: In JavaScript’s datastructures-js library, heap.dequeue() might return undefined if the heap is empty at the very end. The result ? result : 0 logic ensures we return 0 if no stones are left.

💻 Implementation

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function(stones) {
    // 1. Initialize Max-Heap
    let heap = new MaxPriorityQueue();

    // 2. Fill the heap with all stone weights
    for (let i = 0; i < stones.length; i++){
        heap.enqueue(stones[i]);
    }

    // 3. Process stones until 0 or 1 remains
    while(heap.size() > 1){
        let y = heap.dequeue().element; // Heaviest
        let x = heap.dequeue().element; // Second heaviest
        
        if (y !== x) {
            heap.enqueue(y - x); // Push the remainder back
        }
    }

    // 4. Return the last stone weight or 0
    let lastStone = heap.dequeue();
    return lastStone ? lastStone.element : 0;
};

📊 Top K Frequent Elements

🐢 Approach 1: The Brute Force (Sort Everything)

The most intuitive way to solve this is to count everything and then sort the entire list by frequency.

1. Count: Use a Hash Map to get frequencies (e.g., { "1": 3, "2": 2, "3": 1 }).
2. Convert: Turn that map into an array of pairs or objects.
3. Sort: Sort the entire array in descending order based on the frequency.
4. Slice: Take the first k elements.

Why is this “sub-optimal”?

If you have 1 million unique elements but only need the Top 2, sorting all 1 million is a waste of energy. Sorting takes O(N log N). We can do better!

⚡ Approach 2: The Optimized Way (Min-Heap)

The “VIP List” Analogy:

Imagine a club that only holds k people. To find the most frequent guests, you keep a list. If a new guest arrives with a higher frequency than the “least frequent” person currently in the club, you kick the loser out and let the new person in. By the end of the night, only the k most frequent guests remain.

Complexity:

• Time: O(N log k) — Since k is usually much smaller than N, this is significantly faster than sorting the whole dataset.
• Space: O(N) — To store the frequencies in a map.

💻 Implementation (Min-Heap)

var topKFrequent = function (nums, k) {
    // 1. Count frequencies: O(n)
    let map = {};
    for (let e of nums) {
        map[e] = (map[e] || 0) + 1;
    }

    // 2. Use Min-Heap to keep only the top k: O(m log k)
    let pq = new MinPriorityQueue({ priority: x => x.freq });

    for (let key in map) {
        pq.enqueue({ val: key, freq: map[key] });
        
        // The "Kick-out" logic: If we exceed size k, remove the smallest freq
        if (pq.size() > k) {
            pq.dequeue();
        }
    }

    // 3. Extract winners: O(k log k)
    let res = [];
    while (pq.size() > 0) {
        res.push(Number(pq.dequeue().element.val));
    }
    return res;
};

🏁 Method Comparison

Method	Time Complexity	Best Used When…
Brute Force Sort	O(N log N)	The dataset is very small and simplicity is key.
Min-Heap	O(N log k)	k is much smaller than N. This is the standard interview answer.
Bucket Sort	O(N)	You need the absolute maximum theoretical speed.

💬 What do you think?

The Min-Heap approach is the “Gold Standard” for interviews, but did you know there is a way to solve this in linear time, O(N), without using a Heap at all? It’s called Bucket Sort.

Would you like a deep dive into the O(N) Bucket Sort method in the next post? Let me know in the comments!

🟦 K^th Smallest Element in a Sorted Matrix

🧠 Core Idea

The matrix has a special property: every row and every column is sorted in ascending order.

• We could flatten the matrix and sort it, but that would take O(N^2 log N^2).
• Instead, we can treat this like a race. Since each row is already sorted, the smallest overall element must be at the start of one of the rows.
• By using a Min-Heap, we can efficiently track the “next smallest” candidate across all rows without looking at every single number.

⚙️ The “Merging” Strategy

1. Initialize: Push the first element of each row (the first column) into a Min-Heap. Each entry stores the value, the row index, and the column index.
2. Iterate: We need the k-th smallest, so we perform a loop k-1 times:
   • Pop the smallest element currently in the heap.
   • Look at the next element in that same row (move one column over).
   • If a next element exists, push it into the heap.
3. Result: After popping k-1 elements, the next element at the top of the heap is our winner!

Why does this work?

The heap always contains the “frontier” of the smallest available elements. By only adding the next element in a row after the current one is popped, we ensure the heap size stays small—at most min(N, K).

⏱️ Complexity Analysis

• Time: O(K log(min(N, K)))
  • We perform K insertions and K deletions.
  • The heap size is capped at min(N, K), making each operation very fast.
• Space: O(min(N, K))
  • We only store one element from each row (up to K rows) in the heap at any given time.

💡 Key Takeaways

• Sorted Frontiers: Whenever you have multiple sorted lists (or a sorted matrix) and need the “Top K” or “K-th Smallest,” think of a Min-Heap.
• Efficiency: We avoid looking at the entire matrix. If K is small, we only touch a tiny fraction of the data.

💻 Implementation

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function (matrix, k) {
    let n = matrix[0].length;
    let pq = new MinPriorityQueue(x => x.val);

    // 1. Add first column into heap till min(n, k)
    for (let i = 0; i < Math.min(n, k); i++) {
        pq.push({ val: matrix[i][0], row: i, col: 0 });
    }

    // 2. Add remaining elements till k-1
    for (let count = 0; count < k - 1; count++) {
        let { val, row, col } = pq.pop();
        if (col + 1 < n) {
            pq.push({ val: matrix[row][col + 1], row: row, col: col + 1 });
        }
    }
    
    // 3. The current top of the heap is the k-th smallest
    return pq.pop().val;
};

🏁 Method Comparison

Method	Time Complexity	Space Complexity	Best Used When…
Brute Force (Sort)	O(N2 log N)	O(N2)	The matrix is small and unsorted.
Min-Heap (This way)	O(K log N)	O(N)	K is small or the matrix is large.
Binary Search on Value	O(N log(Max-Min))	O(1)	You need an optimized space complexity