Top-K 문제 — 힙 하나로 대량 데이터에서 상위 K개 뽑기

public static int[] topK(int[] arr, int k) {
    // 크기 k의 min-heap
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);

    for (int num : arr) {
        if (minHeap.size() < k) {
            minHeap.offer(num);
        } else if (num > minHeap.peek()) {
            minHeap.poll();   // 가장 작은 원소 제거
            minHeap.offer(num); // 새 원소 추가
        }
    }

    // 힙을 배열로 변환
    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) {
        result[i] = minHeap.poll();
    }
    return result;
}

// 매출 상위 K개 상품 찾기
public static List<Product> topKProducts(List<Product> products, int k) {
    PriorityQueue<Product> minHeap = new PriorityQueue<>(
        Comparator.comparingLong(Product::getRevenue) // 매출 기준 min-heap
    );

    for (Product p : products) {
        if (minHeap.size() < k) {
            minHeap.offer(p);
        } else if (p.getRevenue() > minHeap.peek().getRevenue()) {
            minHeap.poll();
            minHeap.offer(p);
        }
    }

    List<Product> result = new ArrayList<>(minHeap);
    result.sort(Comparator.comparingLong(Product::getRevenue).reversed());
    return result;
}

public static int quickSelect(int[] arr, int left, int right, int k) {
    if (left == right) return arr[left];

    int pivotIdx = partition(arr, left, right);

    if (k == pivotIdx) {
        return arr[k];
    } else if (k < pivotIdx) {
        return quickSelect(arr, left, pivotIdx - 1, k);
    } else {
        return quickSelect(arr, pivotIdx + 1, right, k);
    }
}

private static int partition(int[] arr, int left, int right) {
    // 랜덤 피벗 선택 (최악 O(n²) 방지)
    int randomIdx = left + new Random().nextInt(right - left + 1);
    swap(arr, randomIdx, right);

    int pivot = arr[right];
    int i = left;

    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            swap(arr, i, j);
            i++;
        }
    }
    swap(arr, i, right);
    return i;
}

public static int findKthLargest(int[] arr, int k) {
    // k번째로 큰 = (n-k)번째로 작은
    return quickSelect(arr, 0, arr.length - 1, arr.length - k);
}

public class StreamingTopK {
    private final PriorityQueue<Integer> minHeap;
    private final int k;

    public StreamingTopK(int k) {
        this.k = k;
        this.minHeap = new PriorityQueue<>(k);
    }

    // 새 데이터가 들어올 때마다 호출
    public void add(int value) {
        if (minHeap.size() < k) {
            minHeap.offer(value);
        } else if (value > minHeap.peek()) {
            minHeap.poll();
            minHeap.offer(value);
        }
    }

    // 현재 Top-K 반환
    public List<Integer> getTopK() {
        List<Integer> result = new ArrayList<>(minHeap);
        result.sort(Collections.reverseOrder());
        return result;
    }
}

public static List<Integer> topKFrequent(int[] nums, int k) {
    // 1. 빈도 계산
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
        freq.merge(num, 1, Integer::sum);
    }

    // 2. 빈도 기준 min-heap (크기 k)
    PriorityQueue<Map.Entry<Integer, Integer>> minHeap =
        new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));

    for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
        minHeap.offer(entry);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }

    // 3. 결과 추출
    List<Integer> result = new ArrayList<>();
    while (!minHeap.isEmpty()) {
        result.add(minHeap.poll().getKey());
    }
    Collections.reverse(result);
    return result;
}

public static List<Integer> topKFrequentBucket(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) freq.merge(num, 1, Integer::sum);

    // 빈도를 인덱스로 하는 버킷
    List<List<Integer>> buckets = new ArrayList<>();
    for (int i = 0; i <= nums.length; i++) {
        buckets.add(new ArrayList<>());
    }

    for (var entry : freq.entrySet()) {
        buckets.get(entry.getValue()).add(entry.getKey());
    }

    // 높은 빈도부터 k개 수집
    List<Integer> result = new ArrayList<>();
    for (int i = buckets.size() - 1; i >= 0 && result.size() < k; i--) {
        result.addAll(buckets.get(i));
    }
    return result.subList(0, k);
}

// Redis Sorted Set으로 인기 검색어 관리
// ZINCRBY search:trending "spring boot" 1    → 검색할 때마다 점수 증가
// ZREVRANGE search:trending 0 9              → 상위 10개 조회

// MapReduce Top-K 패턴 (개념)
// Map: 각 파티션에서 로컬 Top-K 추출
// Reduce: 모든 로컬 Top-K를 모아서 글로벌 Top-K 추출