堆

如何手写一个堆？堆就是一个完全二叉树。

完全二叉树的特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

对于最小堆，根节点一定小于左右子节点。但是左右子节点相互之间的大小不确定。

1. 向堆中插入一个数 heap[++size] = x; up(size);
2. 求集合中的最小值 heap[1]
3. 删除最小值 heap[1] = heap[size]; size--; down(1);
4. 删除任意一个数x heap[k] = heap[size]; size--; down(k); up(k);
5. 修改任意一个元素 heap[k] = x; up(k); down(k);

其中重要的一点：

堆排序

import java.io.*;
import java.util.Scanner;
public class Main{
    static int n, m;
    static int[] heap = new int[100010];
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String[] t = scan.nextLine().split(" ");
        n = Integer.parseInt(t[0]); m = Integer.parseInt(t[1]);
        for (int i = 1; i <= n; i++){
            heap[i] = scan.nextInt();
        }
        //从n/2开始down，这样也可以延伸到n
        for (int i = n / 2; i != 0; i --){
            down(i);
        }
        while (m-- != 0){
            System.out.print(heap[1] + " ");
            heap[1] = heap[n--];
            down(1);
        }
    }
    //维护一个堆
    public static void down(int idx){
        int tmp = idx;
        if (idx * 2 <= n && heap[idx * 2] < heap[tmp]) tmp = idx * 2;
        if (idx * 2 + 1 <= n && heap[idx * 2 + 1] < heap[tmp]) tmp = idx * 2 + 1;
        if (tmp != idx){
            int t = heap[tmp];
            heap[tmp] = heap[idx];
            heap[idx] = t;
            down(tmp);
        }
    }
    public static void up(int idx){
        int tmp = idx;
        if (idx / 2 >= 1 && heap[idx / 2] > heap[tmp]) tmp = idx / 2;
        if (tmp != idx){
            int t = heap[tmp];
            heap[tmp] = heap[idx];
            heap[idx] = t;
            up(tmp);
        }
    }
}

大根堆/插排+二分53. 最小的k个数

大根堆

大根堆中是最符合条件的k个人。

从前往后遍历，前k个人一开始都是符合条件的。堆首A是最危险的，他很可能被踢掉。

进来一个人B，B < A, A被竞争走了。更换堆首C。从前到后扫描一遍

这样复杂度是nlogk+k

插排

从前向后遍历，每次二分找出第一个<=当前数的数，把当前数插入到这个数后面

复杂度(n, nlogn)+k

**但是移动的时候需要o(n) 就相当于o(n logn)，而且要处理二分出左右边界的情况，不合适

思路是看y总视频的，手动模拟了栈，出了不少坑。

1. 对堆进行排序,不要执行up操作

2. 对结果集中每次加入堆首，不是heap[i]

3. 堆的下沉操作,注意heap起始坐标一定是从1开始,到n/k结束，从0开始会导致堆首和1无法交换

   把0改成1，k-1没有改成k，导致一致出错

1. 进行down操作的时候，t代表这个数最终的坐标，k代表这个数初始的坐标，因此是和heap[t]比较

   我开始写的是和k比较

class Solution {
    int k;
    int[] heap;
    public List<Integer> getLeastNumbers_Solution(int[] input, int k) {
        if (input.length == 0) return new ArrayList<Integer>();
        this.k = k;
        heap = new int[k + 1];
        //堆中没有填满k个数，更新heap
        for(int i = 1; i <= k; i ++)
            heap[i] = input[i - 1];
        //对当前堆进行排序,不要执行up操作
        for (int i = k / 2; i >= 1; i--)
            down(i);
        //如果将剩下的数和堆首比较，如果<堆首，更新堆首，并使用down更新堆首
        for (int i = k; i < input.length; i ++){
            if (input[i] < heap[1]){
                //System.out.println(heap[1]);
                heap[1]=input[i];
                down(1);
               // System.out.println(heap[1]);
            }
        }
        List<Integer> res = new ArrayList<Integer>();
        //插入堆首到res中，将堆首和队尾进行交换，同时将堆个数-1，down堆首
        for (int i = 1; i <= k; i ++){
            //每次加入堆首，不是heap[i]
            res.add(heap[1]);
            int tmp = heap[1];
            heap[1] = heap[this.k];
            heap[this.k] = tmp;
            this.k--;
            down(1);
        }
        //结果就是res的反转
        Collections.reverse(res);
        return res;
    }
    //堆的下沉操作,注意heap起始坐标一定是从1开始,到n/k结束，从0开始会导致堆首和1无法交换
    //t代表这个数最终的坐标，k代表这个数初始的坐标，因此是和heap[t]比较
    public void down(int k){
        int t = k;
        if (2 * k <= this.k && heap[2*k] > heap[t]) t = 2 * k;
        if (2 *k + 1 <= this.k && heap[2*k + 1] > heap[t]) t = 2*k + 1;
        if (t != k){
            int tmp = heap[t];
            heap[t] = heap[k];
            heap[k] = tmp;
            down(t);
        }
    }
}

两个堆构造两个相对大小的集合54. 数据流中的中位数

求中位数，如果能求出两个集合：

1. 一个集合中s1的数都比另一个集合s2的数大或等
2. 两个集合元素相差不超过1

中位数两边是 s1的最小值 & s2最大值

一个大根堆s2，一个小根堆s1恰好能满足这样的性质

1. 先将数插入到大根堆。
2. 如果两个堆之间出现了逆序元素(s1的堆首 < s2的堆首)，交换堆首元素 满足性质1
3. 如果两个堆之间元素个数相差>=2，将s1的堆首插入s2中。 满足性质2

class Solution {
    PriorityQueue<Integer> s1 = new PriorityQueue();
    PriorityQueue<Integer> s2 = new PriorityQueue<>(( a,  b)-> b - a);
    public void insert(Integer num) {
        //先把数插入到小根堆s1
        s1.offer(num);
        //维护性质1
        while (s2.size() > 0 && s1.peek() < s2.peek() ){
            Integer a1 = s1.poll();
            Integer a2 = s2.poll();
            s2.offer(a1); s1.offer(a2);
        }
        //维护性质2
        while (s1.size() > s2.size() + 1 ){
            s2.offer(s1.poll());
        }
    }
    public Double getMedian() {
        if (s1.size() != s2.size()) return s1.peek().doubleValue();
        else return (s1.peek() + s2.peek()) / 2.0;
    }
}

最小堆+合并链表23. 合并K个升序链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        //最小堆+合并链表 o(logn * mn)
        //如果使用多路归并，o(mnn)
        // 插入对logn ，从堆中拿最小值，堆删除这个值，对应的数组下标后移一位，再加入这个值
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b)->a.val - b.val);
        int n = lists.length; 
        if (n == 0) return null;
        ListNode  dummy = new ListNode(-1), pre = dummy;
        //加入前n个
        for (int i = 0; i < n; i ++)
            if (lists[i] != null) heap.add(lists[i]);
        while (!heap.isEmpty()){
            //取出最小元素
            ListNode num = heap.poll();
            if (num.next != null) heap.add(num.next);
            pre.next = num;
            pre = num;
        }
        return dummy.next;
    }
}