Heap & Priority Queue

import heapq
 
# Min Heap (mặc định)
heap = []
heapq.heappush(heap, 30)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)
 
print(heap[0])          # Xem min: 10
print(heapq.heappop(heap))  # Lấy min: 10
 
# Max Heap: đảo dấu
max_heap = []
heapq.heappush(max_heap, -30)
print(-heapq.heappop(max_heap))  # 30

import java.util.PriorityQueue
 
// Min Heap (mặc định)
val minHeap = PriorityQueue<Int>()
minHeap.add(30)
minHeap.add(10)
minHeap.add(20)
 
println(minHeap.peek())  // 10
println(minHeap.poll())  // 10
 
// Max Heap
val maxHeap = PriorityQueue<Int>(reverseOrder())
maxHeap.add(30)
println(maxHeap.poll())  // 30

import 'package:collection/collection.dart';
 
// Min Heap
var minHeap = PriorityQueue<int>();
minHeap.add(30);
minHeap.add(10);
minHeap.add(20);
 
print(minHeap.first);      // 10
print(minHeap.removeFirst()); // 10
 
// Max Heap
var maxHeap = PriorityQueue<int>((a, b) => b.compareTo(a));

// Swift không có PriorityQueue built-in
// Dùng Array và sort, hoặc implement Heap
 
struct MinHeap<T: Comparable> {
    private var items = [T]()
    
    mutating func push(_ item: T) {
        items.append(item)
        siftUp(items.count - 1)
    }
    
    mutating func pop() -> T? {
        guard !items.isEmpty else { return nil }
        items.swapAt(0, items.count - 1)
        let item = items.removeLast()
        if !items.isEmpty { siftDown(0) }
        return item
    }
    
    var peek: T? { items.first }
}

import java.util.PriorityQueue;
 
// Min Heap (mặc định)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(30);
minHeap.add(10);
minHeap.add(20);
 
System.out.println(minHeap.peek());  // 10
System.out.println(minHeap.poll());  // 10
 
// Max Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

import heapq
 
def k_largest(nums, k):
    return heapq.nlargest(k, nums)
 
# Hoặc dùng min heap kích thước k
def k_largest_heap(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)
    
    for num in nums[k:]:
        if num > heap[0]:
            heapq.heapreplace(heap, num)
    
    return sorted(heap, reverse=True)

fun kLargest(nums: List<Int>, k: Int): List<Int> {
    val minHeap = PriorityQueue<Int>()
    
    for (num in nums) {
        minHeap.add(num)
        if (minHeap.size > k) {
            minHeap.poll()
        }
    }
    
    return minHeap.toList().sortedDescending()
}

List<int> kLargest(List<int> nums, int k) {
  var minHeap = PriorityQueue<int>();
  
  for (int num in nums) {
    minHeap.add(num);
    if (minHeap.length > k) {
      minHeap.removeFirst();
    }
  }
  
  var result = minHeap.toList();
  result.sort((a, b) => b.compareTo(a));
  return result;
}

func kLargest(_ nums: [Int], _ k: Int) -> [Int] {
    var sorted = nums.sorted(by: >)
    return Array(sorted.prefix(k))
}

List<Integer> kLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    for (int num : nums) {
        minHeap.add(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    
    List<Integer> result = new ArrayList<>(minHeap);
    Collections.sort(result, Collections.reverseOrder());
    return result;
}