Java heaps: keep the largest k values with a small priority queue

Java 8+. The program uses only JDK classes and runs without a framework.

Keep only candidates that can still win

A monitoring report needs the three largest queue-depth measurements. Maintain at most k values. Until the heap is full, every measurement becomes a candidate. After that, a value no larger than the smallest retained candidate cannot improve the final top-k set.

The program replaces the heap root only when a larger measurement arrives. It retains repeated measurements as separate samples because the report asks for values by occurrence. A report requiring distinct values needs a separate deduplication policy; replacing the heap with a set would change both membership and count.

PriorityQueue iteration is not sorted order. The program copies the final candidates and sorts that small result in descending order. Calling toString on the queue and labeling it a ranked report would be incorrect even if one test happened to display a useful order.

Choose behaviour for small inputs

When k exceeds the input length, this implementation returns every submitted value in descending order. A non-positive k is rejected. Those choices are part of the API contract; another valid API could insist on exactly k results and reject insufficient input.

The sample stores int measurements. If values are records, compare a stable priority field and add a tie-breaker when report order matters. Avoid subtraction-based comparators because subtraction can overflow. Read PriorityQueue for the standard collection’s basic contract.

Working program

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
public class QueueDepthLeaders {
    static List<Integer> largest(int[] depths, int limit) {
        if (limit < 1) throw new IllegalArgumentException("Positive limit required");
        PriorityQueue<Integer> retained = new PriorityQueue<>();
        for (int depth : depths) {
            if (retained.size() < limit) retained.add(depth);
            else if (depth > retained.peek()) {
                retained.poll();
                retained.add(depth);
            }
        }
        List<Integer> ranked = new ArrayList<>(retained);
        ranked.sort(Collections.reverseOrder());
        return ranked;
    }
    public static void main(String[] args) {
        System.out.println(largest(new int[]{7, 3, 12, 8, 12, 5}, 3));
        System.out.println(largest(new int[]{4}, 3));
    }
}

Output

[12, 12, 8]
[4]

Cost and failure boundaries

For n measurements and m=min(k,n) retained candidates, the scan takes O(n log(m+1)) work in the worst case for heap operations, followed by O(m log m) result sorting. Membership and returned-list storage are O(m), rather than copying and sorting all n measurements.

PriorityQueue growth can copy its backing array, so an individual insertion is not a hard constant allocation event. This example also boxes primitive int values into Integer objects. If the volume is high enough for those costs to matter, measure a primitive heap implementation against the simpler standard collection before adding custom storage.

Common Mistakes

• Do not mistake priority-queue iteration for ranked order.
• Do not remove duplicate values unless distinctness is required.
• Do not use subtraction as an overflow-prone comparator.

Connect the contracts

Compare the boundary explained in Full sorting trade-offs with the assumptions made by this program.

Compare the boundary explained in Heap-based distance processing with the assumptions made by this program.

Compare the Python boundary

Python heapq top-k: define ties before ranking frequencies.