import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    int siftDown(List<Integer> heap, int i) {
        int n = heap.size();
        while (2 * i + 1 < n) {
            int child = 2 * i + 1;
            if (child + 1 < n && heap.get(child + 1) < heap.get(child)) {
                child++;
            }
            if (heap.get(child) >= heap.get(i)) {
                break;
            }
            Collections.swap(heap, i, child);
            i = child;
        }
        return i;
    }

    int pop(List<Integer> heap) {
        int smallest = heap.get(0);
        int last = heap.remove(heap.size() - 1);
        if (!heap.isEmpty()) {
            heap.set(0, last);
            siftDown(heap, 0);
        }
        return smallest;
    }

    List<Integer> popMany(List<Integer> heap, int pops) {
        List<Integer> popped = new ArrayList<>();
        for (int t = 0; t < pops; t++) {
            popped.add(pop(heap));
        }
        return popped;
    }
}
More from Heaps & Priority Queues
