Min-Heap vs Max-Heap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

import heapq
from queue import PriorityQueue  # Thread-safe alternative
 
# ========== BASIC OPERATIONS ==========
 
# Create a heap from a list
data = [5, 7, 9, 1, 3]
heapq.heapify(data)  # In-place, O(n) - transforms list into min-heap
print(data)  # [1, 3, 9, 7, 5] - min at index 0
 
# Push element - O(log n)
heapq.heappush(data, 2)
 
# Pop minimum - O(log n)
minimum = heapq.heappop(data)  # Returns 1
 
# Peek without popping - O(1)
current_min = data[0]  # 2
 
# Push then pop (optimized) - O(log n)
result = heapq.heappushpop(data, 4)  # Push 4, pop and return min
 
# Pop then push (optimized) - O(log n)
result = heapq.heapreplace(data, 0)  # Pop min, then push 0
 
# ========== UTILITY FUNCTIONS ==========
 
# Get n smallest elements - more efficient than sorting
nums = [10, 4, 6, 2, 8, 1, 9, 3]
smallest_3 = heapq.nsmallest(3, nums)  # [1, 2, 3]
 
# Get n largest elements
largest_3 = heapq.nlargest(3, nums)  # [10, 9, 8]
 
# With key function
words = ["apple", "pie", "banana", "cherry"]
shortest = heapq.nsmallest(2, words, key=len)  # ['pie', 'apple']
 
# ========== MAX-HEAP PATTERNS ==========
 
# Pattern 1: Negate values (most common)
max_heap = []
for val in [3, 1, 4, 1, 5]:
    heapq.heappush(max_heap, -val)
 
maximum = -heapq.heappop(max_heap)  # 5
 
# Pattern 2: Tuple with negated key
tasks = []
heapq.heappush(tasks, (-priority, task_id, task_data))
neg_pri, tid, data = heapq.heappop(tasks)
actual_priority = -neg_pri
 
# Pattern 3: Wrapper class (see Page 3 for implementation)
# from myutils import MaxHeapItem
# heap.push(MaxHeapItem(value))
 
# ========== THREAD-SAFE PRIORITY QUEUE ==========
 
# For multi-threaded applications, use queue.PriorityQueue
pq = PriorityQueue()
pq.put((2, "medium"))
pq.put((1, "high"))
pq.put((3, "low"))
 
# Blocks if empty, thread-safe
priority, task = pq.get()  # (1, "high")
 
# ========== COMMON INTERVIEW PATTERNS ==========
 
def merge_k_sorted_lists(lists):
    """Merge k sorted lists using heapq."""
    result = []
    heap = []
    
    # Initialize with first element from each list
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
    
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        
        if elem_idx + 1 < len(lists[list_idx]):
            next_val = lists[list_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
    
    return result
 
 
def kth_largest(nums, k):
    """Find kth largest using min-heap of size k."""
    # Min-heap automatically maintains k largest
    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]  # kth largest

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

import java.util.*;
 
public class HeapOperations {
    
    public static void main(String[] args) {
        // ========== BASIC USAGE ==========
        
        // Min-heap (default) for integers
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(5);
        minHeap.add(1);
        minHeap.add(3);
        
        System.out.println(minHeap.peek());   // 1 (minimum)
        System.out.println(minHeap.poll());   // 1 (remove minimum)
        System.out.println(minHeap.poll());   // 3
        
        // ========== MAX-HEAP ==========
        
        // Method 1: Collections.reverseOrder()
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.addAll(Arrays.asList(5, 1, 3));
        System.out.println(maxHeap.poll());   // 5 (maximum)
        
        // Method 2: Lambda comparator
        PriorityQueue<Integer> maxHeap2 = new PriorityQueue<>((a, b) -> b - a);
        
        // Method 3: Comparator.reverseOrder()
        PriorityQueue<Integer> maxHeap3 = new PriorityQueue<>(Comparator.reverseOrder());
        
        // ========== CUSTOM OBJECTS ==========
        
        // Task class with priority
        class Task {
            String name;
            int priority;
            
            Task(String name, int priority) {
                this.name = name;
                this.priority = priority;
            }
        }
        
        // Min-heap by priority
        PriorityQueue<Task> taskQueue = new PriorityQueue<>(
            Comparator.comparingInt(t -> t.priority)
        );
        
        // Max-heap by priority
        PriorityQueue<Task> maxTaskQueue = new PriorityQueue<>(
            Comparator.comparingInt((Task t) -> t.priority).reversed()
        );
        
        // Multi-level sorting: priority first, then name
        PriorityQueue<Task> complexQueue = new PriorityQueue<>(
            Comparator.comparingInt((Task t) -> t.priority)
                      .thenComparing(t -> t.name)
        );
        
        // ========== USEFUL PATTERNS ==========
        
        // K largest elements using min-heap of size k
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        
        PriorityQueue<Integer> kLargestHeap = new PriorityQueue<>();
        for (int num : nums) {
            kLargestHeap.offer(num);
            if (kLargestHeap.size() > k) {
                kLargestHeap.poll();
            }
        }
        // kLargestHeap now contains [5, 6]
        
        // Median finder using two heaps
        PriorityQueue<Integer> maxHeapLower = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minHeapUpper = new PriorityQueue<>();
        
        // ========== THREAD-SAFE VERSION ==========
        
        // import java.util.concurrent.PriorityBlockingQueue;
        // PriorityBlockingQueue<Task> concurrentQueue = new PriorityBlockingQueue<>();
        
        // ========== API NOTES ==========
        
        // add() vs offer() - both add element, add() throws on capacity limits (rare)
        // remove() vs poll() - both remove min, remove() throws if empty, poll() returns null
        // element() vs peek() - both return min, element() throws if empty, peek() returns null
        
        // Size and capacity
        // PriorityQueue grows dynamically, initial capacity is 11
        PriorityQueue<Integer> withCapacity = new PriorityQueue<>(100);
    }
    
    // ========== DIJKSTRA EXAMPLE ==========
    
    public Map<Integer, Integer> dijkstra(Map<Integer, List<int[]>> graph, int start) {
        // graph: node -> list of [neighbor, weight]
        Map<Integer, Integer> distances = new HashMap<>();
        distances.put(start, 0);
        
        // Min-heap: [distance, node]
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            Comparator.comparingInt(a -> a[0])
        );
        pq.offer(new int[]{0, start});
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int dist = current[0];
            int node = current[1];
            
            if (dist > distances.getOrDefault(node, Integer.MAX_VALUE)) {
                continue;
            }
            
            for (int[] edge : graph.getOrDefault(node, List.of())) {
                int neighbor = edge[0];
                int weight = edge[1];
                int newDist = dist + weight;
                
                if (newDist < distances.getOrDefault(neighbor, Integer.MAX_VALUE)) {
                    distances.put(neighbor, newDist);
                    pq.offer(new int[]{newDist, neighbor});
                }
            }
        }
        
        return distances;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

#include <iostream>
#include <queue>
#include <vector>
#include <functional>  // for greater<>
#include <utility>     // for pair
 
// ========== BASIC USAGE ==========
 
void basicUsage() {
    // Max-heap (DEFAULT in C++)
    std::priority_queue<int> maxHeap;
    maxHeap.push(5);
    maxHeap.push(1);
    maxHeap.push(3);
    
    std::cout << maxHeap.top();  // 5 (maximum)
    maxHeap.pop();               // removes 5
    std::cout << maxHeap.top();  // 3
    
    // Min-heap using greater<>
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    minHeap.push(5);
    minHeap.push(1);
    minHeap.push(3);
    
    std::cout << minHeap.top();  // 1 (minimum)
}
 
// ========== CUSTOM COMPARATORS ==========
 
struct Task {
    std::string name;
    int priority;
    double deadline;
};
 
// Functor comparator for tasks
struct TaskCompare {
    bool operator()(const Task& a, const Task& b) const {
        // Note: Returns true if 'a' has LOWER priority than 'b'
        // This is opposite from what you might expect!
        // In priority_queue, true means 'a' goes below 'b'
        return a.priority < b.priority;  // Max-heap by priority
    }
};
 
void customComparators() {
    // Using functor
    std::priority_queue<Task, std::vector<Task>, TaskCompare> taskQueue;
    
    // Using lambda (C++11+)
    auto cmp = [](const Task& a, const Task& b) {
        return a.deadline > b.deadline;  // Min-heap by deadline (earlier first)
    };
    std::priority_queue<Task, std::vector<Task>, decltype(cmp)> deadlineQueue(cmp);
    
    // With pairs: min-heap by first element
    std::priority_queue<
        std::pair<int, std::string>,
        std::vector<std::pair<int, std::string>>,
        std::greater<std::pair<int, std::string>>
    > pairMinHeap;
    
    pairMinHeap.push({3, "task3"});
    pairMinHeap.push({1, "task1"});
    pairMinHeap.push({2, "task2"});
    // top() returns {1, "task1"}
}
 
// ========== COMMON PATTERNS ==========
 
// K largest elements
std::vector<int> kLargest(std::vector<int>& nums, int k) {
    // Min-heap of size k (smallest of the k largest = kth largest)
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    
    for (int num : nums) {
        minHeap.push(num);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }
    
    std::vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top());
        minHeap.pop();
    }
    return result;  // Note: not sorted
}
 
// Dijkstra's algorithm
#include <unordered_map>
#include <limits>
 
std::unordered_map<int, int> dijkstra(
    const std::unordered_map<int, std::vector<std::pair<int, int>>>& graph,
    int start
) {
    // graph: node -> vector of (neighbor, weight)
    std::unordered_map<int, int> distances;
    distances[start] = 0;
    
    // Min-heap: (distance, node)
    std::priority_queue<
        std::pair<int, int>,
        std::vector<std::pair<int, int>>,
        std::greater<std::pair<int, int>>
    > pq;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [dist, node] = pq.top();
        pq.pop();
        
        // Skip if we've found a shorter path
        if (distances.count(node) && dist > distances[node]) {
            continue;
        }
        
        auto it = graph.find(node);
        if (it == graph.end()) continue;
        
        for (auto [neighbor, weight] : it->second) {
            int newDist = dist + weight;
            
            if (!distances.count(neighbor) || newDist < distances[neighbor]) {
                distances[neighbor] = newDist;
                pq.push({newDist, neighbor});
            }
        }
    }
    
    return distances;
}
 
// ========== MAKE_HEAP ALTERNATIVE ==========
// For more control, use <algorithm> heap functions on vectors
 
#include <algorithm>
 
void heapAlgorithms() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
    
    // Create max-heap in-place
    std::make_heap(v.begin(), v.end());
    // v[0] is now maximum
    
    // Add element
    v.push_back(10);
    std::push_heap(v.begin(), v.end());
    
    // Remove maximum
    std::pop_heap(v.begin(), v.end());
    v.pop_back();
    
    // Sort the heap (destroys heap property)
    std::sort_heap(v.begin(), v.end());
    
    // Min-heap using greater<>
    std::vector<int> minV = {3, 1, 4, 1, 5};
    std::make_heap(minV.begin(), minV.end(), std::greater<int>());
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

// ========== IMPLEMENTING A HEAP ==========
 
/**
 * A complete MinHeap implementation in TypeScript.
 * This is a common interview expectation for JS/TS candidates.
 */
class MinHeap<T> {
    private heap: T[] = [];
    private compare: (a: T, b: T) => number;
    
    constructor(compareFn?: (a: T, b: T) => number) {
        // Default: natural ordering for numbers
        this.compare = compareFn || ((a, b) => (a as any) - (b as any));
    }
    
    private parent(i: number): number { return Math.floor((i - 1) / 2); }
    private left(i: number): number { return 2 * i + 1; }
    private right(i: number): number { return 2 * i + 2; }
    
    private swap(i: number, j: number): void {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }
    
    private heapifyUp(i: number): void {
        while (i > 0 && this.compare(this.heap[i], this.heap[this.parent(i)]) < 0) {
            this.swap(i, this.parent(i));
            i = this.parent(i);
        }
    }
    
    private heapifyDown(i: number): void {
        let smallest = i;
        const L = this.left(i);
        const R = this.right(i);
        
        if (L < this.heap.length && this.compare(this.heap[L], this.heap[smallest]) < 0) {
            smallest = L;
        }
        if (R < this.heap.length && this.compare(this.heap[R], this.heap[smallest]) < 0) {
            smallest = R;
        }
        
        if (smallest !== i) {
            this.swap(i, smallest);
            this.heapifyDown(smallest);
        }
    }
    
    push(val: T): void {
        this.heap.push(val);
        this.heapifyUp(this.heap.length - 1);
    }
    
    pop(): T | undefined {
        if (this.heap.length === 0) return undefined;
        if (this.heap.length === 1) return this.heap.pop();
        
        const min = this.heap[0];
        this.heap[0] = this.heap.pop()!;
        this.heapifyDown(0);
        return min;
    }
    
    peek(): T | undefined {
        return this.heap[0];
    }
    
    size(): number {
        return this.heap.length;
    }
    
    isEmpty(): boolean {
        return this.heap.length === 0;
    }
}
 
// MaxHeap by reversing the comparator
class MaxHeap<T> extends MinHeap<T> {
    constructor(compareFn?: (a: T, b: T) => number) {
        const reversed = compareFn 
            ? (a: T, b: T) => -compareFn(a, b)
            : (a: T, b: T) => (b as any) - (a as any);
        super(reversed);
    }
}
 
// ========== USAGE EXAMPLES ==========
 
// Numbers (default comparison)
const minHeap = new MinHeap<number>();
minHeap.push(5);
minHeap.push(1);
minHeap.push(3);
console.log(minHeap.pop());  // 1
 
const maxHeap = new MaxHeap<number>();
maxHeap.push(5);
maxHeap.push(1);
maxHeap.push(3);
console.log(maxHeap.pop());  // 5
 
// Custom objects
interface Task {
    name: string;
    priority: number;
}
 
const taskHeap = new MinHeap<Task>((a, b) => a.priority - b.priority);
taskHeap.push({ name: "low", priority: 3 });
taskHeap.push({ name: "high", priority: 1 });
console.log(taskHeap.pop()?.name);  // "high"
 
// ========== USING LIBRARIES ==========
 
// With @datastructures-js/priority-queue (npm install)
// import { MinPriorityQueue, MaxPriorityQueue } from '@datastructures-js/priority-queue';
//
// const pq = new MinPriorityQueue<number>();
// pq.enqueue(5);
// pq.enqueue(1);
// console.log(pq.dequeue().element);  // 1
//
// // With priority function
// const taskPQ = new MinPriorityQueue<Task>({ priority: (task) => task.priority });
 
// ========== LEETCODE ENVIRONMENT ==========
 
// LeetCode provides MinPriorityQueue and MaxPriorityQueue
// They work similarly to the library above:
//
// const pq = new MinPriorityQueue({ priority: (x) => x[0] });
// pq.enqueue([dist, node]);
// const { element } = pq.dequeue();
 
// ========== K-TH LARGEST ELEMENT ==========
 
function findKthLargest(nums: number[], k: number): number {
    const minHeap = new MinHeap<number>();
    
    for (const num of nums) {
        minHeap.push(num);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }
    
    return minHeap.peek()!;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182

package main
 
import (
	"container/heap"
	"fmt"
)
 
// ========== BASIC MIN-HEAP OF INTS ==========
 
// IntHeap implements heap.Interface for a min-heap of ints
type IntHeap []int
 
// Required by sort.Interface (which heap.Interface embeds)
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }  // Min-heap: smaller is "less"
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
 
// Required by heap.Interface
func (h *IntHeap) Push(x any) {
	*h = append(*h, x.(int))
}
 
func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}
 
// ========== MAX-HEAP (flip Less comparison) ==========
 
type MaxIntHeap []int
 
func (h MaxIntHeap) Len() int           { return len(h) }
func (h MaxIntHeap) Less(i, j int) bool { return h[i] > h[j] }  // Max-heap: larger is "less"
func (h MaxIntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MaxIntHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *MaxIntHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}
 
// ========== CUSTOM TYPE WITH PRIORITY ==========
 
type Item struct {
	value    string
	priority int
	index    int  // Needed for update operations
}
 
type PriorityQueue []*Item
 
func (pq PriorityQueue) Len() int { return len(pq) }
 
func (pq PriorityQueue) Less(i, j int) bool {
	// Min-heap by priority (lower priority number = higher urgency)
	return pq[i].priority < pq[j].priority
}
 
func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}
 
func (pq *PriorityQueue) Push(x any) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}
 
func (pq *PriorityQueue) Pop() any {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil  // Avoid memory leak
	item.index = -1 // For safety
	*pq = old[0 : n-1]
	return item
}
 
// Update modifies the priority of an item in the queue
func (pq *PriorityQueue) Update(item *Item, value string, priority int) {
	item.value = value
	item.priority = priority
	heap.Fix(pq, item.index)
}
 
// ========== USAGE ==========
 
func main() {
	// Min-heap of ints
	h := &IntHeap{5, 1, 3}
	heap.Init(h)
	
	heap.Push(h, 2)
	fmt.Printf("min: %d
", (*h)[0])  // 1
	
	for h.Len() > 0 {
		fmt.Printf("%d ", heap.Pop(h))  // 1 2 3 5
	}
	fmt.Println()
	
	// Priority queue with custom type
	pq := &PriorityQueue{
		{value: "task1", priority: 3},
		{value: "task2", priority: 1},
		{value: "task3", priority: 2},
	}
	heap.Init(pq)
	
	// Add new item
	item := &Item{value: "urgent", priority: 0}
	heap.Push(pq, item)
	
	// Process in priority order
	for pq.Len() > 0 {
		item := heap.Pop(pq).(*Item)
		fmt.Printf("(%d, %s) ", item.priority, item.value)
	}
	// Output: (0, urgent) (1, task2) (2, task3) (3, task1)
}
 
// ========== DIJKSTRA IN GO ==========
 
type Edge struct {
	to, weight int
}
 
type Node struct {
	id, dist int
}
 
type NodeHeap []Node
 
func (h NodeHeap) Len() int           { return len(h) }
func (h NodeHeap) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h NodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *NodeHeap) Push(x any)        { *h = append(*h, x.(Node)) }
func (h *NodeHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}
 
func dijkstra(graph [][]Edge, start int) []int {
	n := len(graph)
	dist := make([]int, n)
	for i := range dist {
		dist[i] = 1<<31 - 1
	}
	dist[start] = 0
	
	h := &NodeHeap{{start, 0}}
	heap.Init(h)
	
	for h.Len() > 0 {
		curr := heap.Pop(h).(Node)
		
		if curr.dist > dist[curr.id] {
			continue
		}
		
		for _, edge := range graph[curr.id] {
			newDist := curr.dist + edge.weight
			if newDist < dist[edge.to] {
				dist[edge.to] = newDist
				heap.Push(h, Node{edge.to, newDist})
			}
		}
	}
	
	return dist
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

use std::collections::BinaryHeap;
use std::cmp::Reverse;
 
fn main() {
    // ========== MAX-HEAP (DEFAULT) ==========
    
    let mut max_heap = BinaryHeap::new();
    max_heap.push(5);
    max_heap.push(1);
    max_heap.push(3);
    
    println!("max: {:?}", max_heap.peek());  // Some(5)
    println!("pop: {:?}", max_heap.pop());   // Some(5)
    
    // ========== MIN-HEAP USING REVERSE ==========
    
    let mut min_heap = BinaryHeap::new();
    min_heap.push(Reverse(5));
    min_heap.push(Reverse(1));
    min_heap.push(Reverse(3));
    
    // Note: values are wrapped in Reverse
    if let Some(Reverse(min)) = min_heap.pop() {
        println!("min: {}", min);  // 1
    }
    
    // ========== CUSTOM TYPES ==========
    
    #[derive(Eq, PartialEq)]
    struct Task {
        priority: i32,
        name: String,
    }
    
    // Implement Ord for max-heap ordering (higher priority = should come first)
    impl Ord for Task {
        fn cmp(&self, other: &Self) -> std::cmp::Ordering {
            self.priority.cmp(&other.priority)
        }
    }
    
    impl PartialOrd for Task {
        fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
            Some(self.cmp(other))
        }
    }
    
    let mut task_heap = BinaryHeap::new();
    task_heap.push(Task { priority: 1, name: "low".to_string() });
    task_heap.push(Task { priority: 5, name: "high".to_string() });
    
    if let Some(task) = task_heap.pop() {
        println!("Next task: {} (priority {})", task.name, task.priority);
        // "high" (priority 5)
    }
    
    // ========== MIN-HEAP FOR CUSTOM TYPE ==========
    
    // Option 1: Wrap entire struct in Reverse
    let mut min_task_heap: BinaryHeap<Reverse<Task>> = BinaryHeap::new();
    min_task_heap.push(Reverse(Task { priority: 5, name: "high".to_string() }));
    min_task_heap.push(Reverse(Task { priority: 1, name: "low".to_string() }));
    
    // Option 2: Implement Ord to give min-heap behavior
    #[derive(Eq, PartialEq)]
    struct MinTask {
        priority: i32,
        name: String,
    }
    
    impl Ord for MinTask {
        fn cmp(&self, other: &Self) -> std::cmp::Ordering {
            // Reverse comparison for min-heap behavior
            other.priority.cmp(&self.priority)
        }
    }
    
    impl PartialOrd for MinTask {
        fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
            Some(self.cmp(other))
        }
    }
    
    // ========== USEFUL METHODS ==========
    
    let nums = vec![5, 1, 3, 9, 7];
    
    // Create from iterator
    let heap: BinaryHeap<i32> = nums.iter().copied().collect();
    
    // Convert to sorted vec
    let sorted: Vec<i32> = heap.into_sorted_vec();
    
    // Peek_mut for in-place modification
    let mut heap2 = BinaryHeap::from(vec![1, 2, 3]);
    if let Some(mut top) = heap2.peek_mut() {
        *top = 10;  // Automatically re-heapifies when dropped
    }
}
 
// ========== DIJKSTRA IN RUST ==========
 
use std::collections::HashMap;
 
fn dijkstra(graph: &HashMap<i32, Vec<(i32, i32)>>, start: i32) -> HashMap<i32, i32> {
    let mut distances: HashMap<i32, i32> = HashMap::new();
    distances.insert(start, 0);
    
    // Min-heap: (Reverse(distance), node)
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0, start)));
    
    while let Some(Reverse((dist, node))) = heap.pop() {
        if let Some(&known_dist) = distances.get(&node) {
            if dist > known_dist {
                continue;
            }
        }
        
        if let Some(neighbors) = graph.get(&node) {
            for &(neighbor, weight) in neighbors {
                let new_dist = dist + weight;
                let is_shorter = distances
                    .get(&neighbor)
                    .map_or(true, |&d| new_dist < d);
                
                if is_shorter {
                    distances.insert(neighbor, new_dist);
                    heap.push(Reverse((new_dist, neighbor)));
                }
            }
        }
    }
    
    distances
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

// ========== C# (.NET 6+) ==========
// C# added PriorityQueue in .NET 6
 
using System.Collections.Generic;
 
public class CSharpHeaps
{
    public void Example()
    {
        // PriorityQueue<TElement, TPriority>
        // MIN-heap by priority (lower priority number = dequeued first)
        
        var pq = new PriorityQueue<string, int>();
        pq.Enqueue("low", 5);
        pq.Enqueue("high", 1);
        pq.Enqueue("medium", 3);
        
        string item = pq.Dequeue();  // "high" (priority 1)
        
        // Max-heap: negate priorities or use custom comparer
        var maxPq = new PriorityQueue<string, int>(
            Comparer<int>.Create((a, b) => b.CompareTo(a))
        );
        
        // Or simply negate
        var maxPqNegate = new PriorityQueue<string, int>();
        maxPqNegate.Enqueue("low", -5);  // Will come out first
        
        // TryDequeue for safe removal
        if (pq.TryDequeue(out string element, out int priority))
        {
            Console.WriteLine($"{element} with priority {priority}");
        }
        
        // EnqueueDequeue (optimized)
        var result = pq.EnqueueDequeue("new", 2);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

// ========== KOTLIN ==========
// Kotlin uses Java's PriorityQueue
 
import java.util.PriorityQueue
 
fun kotlinHeaps() {
    // Min-heap (default)
    val minHeap = PriorityQueue<Int>()
    minHeap.addAll(listOf(5, 1, 3))
    println(minHeap.poll())  // 1
    
    // Max-heap using compareByDescending
    val maxHeap = PriorityQueue<Int>(compareByDescending { it })
    maxHeap.addAll(listOf(5, 1, 3))
    println(maxHeap.poll())  // 5
    
    // Custom data class
    data class Task(val name: String, val priority: Int)
    
    // Min-heap by priority
    val taskQueue = PriorityQueue<Task>(compareBy { it.priority })
    taskQueue.add(Task("low", 5))
    taskQueue.add(Task("high", 1))
    println(taskQueue.poll())  // Task(name=high, priority=1)
    
    // Complex ordering
    val complexQueue = PriorityQueue<Task>(
        compareBy<Task> { it.priority }
            .thenBy { it.name }
    )
    
    // Max-heap with multiple criteria
    val maxComplexQueue = PriorityQueue<Task>(
        compareByDescending<Task> { it.priority }
            .thenBy { it.name }
    )
}