JAVA 用 List 实现堆

大顶堆：每个父节点都大于子节点

小顶堆：每个父节点都小于子节点

在堆中，每次加入元素或者移除元素，都要调整堆的位置，使其满足堆的定义。

常用于 topK 问题，k 个最大/最小元素，每次弹出大顶堆/小顶堆 堆顶元素即可。

以及堆排序问题，堆排序可以看成是将待排序的数组元素依次加入堆（每次加入都调整堆）构建一个初始大顶/小顶堆。再依次弹出堆顶元素（每次弹出都调整堆）。

堆是用完全二叉树实现的，而完全二叉树可以用数组来表示。

1. 若array[0，...，n-1]表示一颗完全二叉树的顺序存储模式，则双亲节点指针和孩子结点指针之间的内在关系如下：

        　　任意一节点指针 i：父节点：i==0 ? null : (i-1)/2

        　　　　　　　　　　  左孩子：2*i + 1

        　　　　　　　　　　  右孩子：2*i + 2

2. 堆的定义：n个关键字序列array[0，...，n-1]，当且仅当满足下列要求：(0 <= i <= (n-1)/2)

　　　　　　① array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]； 称为小根堆；

　　　　　　② array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]； 称为大根堆；

以下以小顶堆为例，说明两个基本问题

1、如何将元素加入堆？

　　前情：每次加入元素，都会调整堆，使其符合堆的定义。所以每次元素加入的一定是一个符合定义的堆。

　　每次将元素加入堆的末尾，从末尾逐步将这个元素调整到合适的位置。

　　每次调整都至少应该使得 【要调整的这个元素（新加入堆末尾）、其父节点、其兄弟节点】 三者满足小顶堆的定义：父节点比两个孩子节点都小

　　由于我们强调过前提是 元素加入的一定是一个符合定义的堆，所以 其父节点和其兄弟节点 一定满足堆的定义，即父节点一定比兄弟节点小

　　所以我们只需保证一个：就是其父节点比这个新加入的元素小，如果不满足，就要交换父节点和这个节点

　　交换后，这个元素的新位置、新的父节点、新的兄弟节点 三者可能仍然不满足小顶堆的定义，继续与新的父节点比较，进行调整

　　........

　　直到这个元素上浮到一个符合定义的位置：父节点比自己和兄弟节点都小，就完成了堆的调整。

/*
      先加入到底部最后一个，再从下往上上升，每当判断父节点比自己大（小顶堆）则交换
     */
    public void offer(Integer e) {// 先加入到底部，最后一个
        list.add(e);
        if (list.isEmpty()) {
            return;
        }
        int thisIndex = list.size() - 1;
        int parentIndex = (thisIndex - 1) /2;
        // 每次都 offer 的 话，那么现在肯定是一个小顶堆，父节点比已有的左节点（有可能没有左节点）小
        // 【所以先不用关注左节点，只关注父节点】
        // 一直从底向上调整到父节点比自己小
        while (parentIndex >= 0 && list.get(parentIndex) > list.get(thisIndex)) {
            //小顶堆，如果父节点大于当前节点，则交换位置
            swapListE(list, parentIndex, thisIndex);
            // 现在这个节点下标等于之前父节点的
            thisIndex = parentIndex;
            // 新的父节点下标
            parentIndex = (thisIndex - 1) /2;
        }
    }

    // 获取小顶堆顶端的元素
    public Integer peek() {
        if (list.isEmpty()) {
            return null;
        }
        return list.get(0);
    }

2、如何移除堆顶元素？

　　将堆顶元素移除，并将堆末尾元素放到堆顶，再调整堆，使新的堆顶到它合适的位置

　　同样，要使得至少 【要调整的这个元素（从堆末尾到堆顶的），它的左孩子，它的右孩子】 三者符合小顶堆的定义，这个元素要比它的左右孩子都小。如果不符合，就要进行调整

　　调整时，简单说就是将三者中最小的放到顶。细分有以下几种情况

1、当前元素没有左右孩子：符合堆的定义，不用调整

2、当前元素只有一个左孩子（完全二叉树不可能只有右孩子）：比左孩子小，则符合堆的定义，不用调整；比左孩子大，则与左孩子进行交换

3、当前元素有左、右两个孩子：

　　a.比左右两孩子都小，符合堆的定义，不用调整

　　b.处于两个孩子中间，则与比自己小的那个交换

　　c.比两个孩子都大，则与两个孩子中较小的那个进行交换

交换后，这个元素的新位置、新的左孩子、新的右孩子 三者可能仍然不满足小顶堆的定义，继续与新的左右孩子比较，进行调整

........

　　直到这个元素下沉到一个符合定义的位置：父节点比自己和兄弟节点都小，就完成了堆的调整。

/*
      弹出顶端，再把底部最后拉到最顶端，在从上往下依次下沉，每当判断孩子节点比自己小（小顶堆）
     */
    public Integer poll() {
        if (list.isEmpty()) {
            return null;
        }
        // 暂存顶部元素
        Integer topE = list.get(0);
        if (list.size() == 1) {
            list.remove(0);
            return topE;
        }
        // 将底部元素交换到顶部
        swapListE(list, 0, list.size() - 1);
        // 移除要弹出的曾经的顶部元素
        list.remove(list.size() - 1);
         /*
            要使得至少 【要调整的这个元素（从堆末尾到堆顶的），它的左孩子，它的右孩子】 三者符合小顶堆的定义
            如果符合定义，则返回 -1 ，如果不符合定义，则返回要交换的那个元素的下标
         */
        int thisIndex = 0;int needSwapChirldrenIndex = getNeedSwapChirldrenIndex(list, thisIndex);
        while(needSwapChirldrenIndex != -1) {
            swapListE(list, thisIndex, needSwapChirldrenIndex);
            thisIndex = needSwapChirldrenIndex;
            needSwapChirldrenIndex = getNeedSwapChirldrenIndex(list, thisIndex);
        }
        return topE;
    }

    /* 判断根节点和它的左右孩子是否满足小顶堆，满足则返回 -1，不满足则返回要交换的那个元素的下标，几种情况
            1、当前元素没有左右孩子：不用交换，返回 -1
            1、当前元素只有左孩子：比左孩子小不用交换返回-1；比左孩子大与左孩子交换，返回左孩 index
            2、当前元素有左右两个孩子
                a、比左右孩子都小，不用交换，返回 -1
                b、处于两孩子中间，则与比自己小的那个交换
                c、比两个孩子都大，则与两个孩子中较小的那个交换
         */
    // 该方法判断根节点和它的左右孩子是否满足小顶堆，满足则返回 -1，不满足则返回要交换的那个元素的下标
    private int getNeedSwapChirldrenIndex(List<Integer> list, int rootIndex) {
        Integer rootValue = list.get(rootIndex);
        int leftIndex = 2*rootIndex + 1;
        int rightIndex = 2*rootIndex + 2;
        Integer leftValue = null;
        Integer rightValue = null;
        if (leftIndex > 0 && leftIndex < list.size()) {
            leftValue = list.get(leftIndex);
        }
        if (rightIndex > 0 && rightIndex < list.size()) {
            rightValue = list.get(rightIndex);
        }
        // 返回 -1 , 表示符合大顶堆
        // 左右孩子都没有，符合
        if (leftValue == null && rightValue == null) {
            return -1;
        }
        // 只有左孩子
        else if (rightValue == null)  {
            if (rootValue > leftValue) {
                // 不符合，返回左孩子的下标，要与左孩子交换
                return leftIndex;
            }
            else {
                // 符合，返回 -1
                return -1;
            }
        }
        // 完全二叉树，没有 只有右孩子 的情况
        else if (leftValue == null)  {
            return -1;
        }
        // 左右孩子都有
        else {
            // 比两个孩子都小，不用交换
            if (rootValue < leftValue && rootValue < rightValue) {
                return -1;
            }
            // 小于左孩子，大于右孩子。与右孩子交换
            else if (rootValue < leftValue && rootValue > rightValue) {
                return rightIndex;
            }
            // 小于右孩子，大于左孩子。与左孩子交换
            else if (rootValue < rightValue && rootValue > leftValue) {
                return leftIndex;
            }
            // 比左右孩子都大
            else if (rootValue > rightValue && rootValue > leftValue) {
                // 与两个孩子中较小的那个交换
                if (leftValue < rightValue) {
                    return leftIndex;
                }
                else {
                    return rightIndex;
                }
            }
            else {
                return -1;
            }
        }
    }

3、堆排序

可以看成是将待排序的数组元素依次加入堆（每次加入都调整堆）构建一个初始大顶/小顶堆。再依次弹出堆顶元素（每次弹出都调整堆），每次弹出最大/最小，相当于完成了排序。

private static void heapOrder(int[] arr) {
        Heap heap = new Heap();
        for (int e : arr) {
            heap.offer(e);
        }
        for (int i=0;i<arr.length;i++) {
            arr[i] = heap.poll();
        }
    }

4、Java 优先级队列的用法

待补充