Heap

Heapify

private void heapify(ListNode[] lists, int i) {
        int min = i, l = 2*i+1, r = 2*i+2, n = lists.length;

        // compare root & left;
        if (l < n && lists[l] != null) {
            if (lists[min] == null || lists[l].val < lists[min].val) {
                min = l;
            }
        }

        // compare right & min
        if (r < n && lists[r] != null) {
            if (lists[min] == null || lists[r].val < lists[min].val) {
                min = r;
            }
        }

        // swap?
        if (min == i || lists[min] == null) {
            return; // already min, no need to swap.
        } else {

        // swap root & minIdx
            ListNode tmp = lists[i];
            lists[i] = lists[min];
            lists[min] = tmp;
        }

        // heapify minIdx
        heapify(lists, min);
    }

Kth element problem

without update, direct poll

https://leetcode.com/problems/top-k-frequent-elements/description/

update: poll and offer back

https://leetcode.com/problems/merge-k-sorted-lists/description/ https://leetcode.com/problems/find-k-pairs-with-smallest-sums/description/ https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/ https://leetcode.com/problems/meeting-rooms-ii/

median problem

https://leetcode.com/problems/find-median-from-data-stream/