# Heap

## Heapify

```java
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/](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/merge-k-sorted-lists/description/) [https://leetcode.com/problems/find-k-pairs-with-smallest-sums/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/kth-smallest-element-in-a-sorted-matrix/) [https://leetcode.com/problems/meeting-rooms-ii/](https://leetcode.com/problems/meeting-rooms-ii/)

### median problem

[https://leetcode.com/problems/find-median-from-data-stream/](https://leetcode.com/problems/find-median-from-data-stream/)
