二叉堆

1. 思考

Top k 问题：从海量数据中获取前k个 最大值 或 最小值；
比如从 一百万 个整数中，获取最大的1000个整数；
设计一种数据结构，用来存放整数元素，包括的操作是 获取最大值，添加元素，删除最大值：

各数据结构的时间复杂度对比
为了能达到最优，使用堆：
堆：获取最大值时间复杂度O(1)，添加元素时间复杂度O(log n)，删除最大值时间复杂度O(log n)；

2. 堆 (Heap)

这里的堆是一种数据结构，不是指内存中堆，堆一般分为：

二叉堆（Binary Heap，完全二叉堆）；
多叉堆（D-heap、D-ary Heap）;
索引堆（Index Heap）;
二项堆（Binomial Heap）；
斐波那契堆（Fibonacci Heap）；
左倾堆（Leftist Heap）；
斜堆（Skew Heap）；

堆的最重要性质：任意节点的值总是 $\geq$ 或者 $\leq$ 子节点的值：

如果任意节点的值 $\geq$ 子节点的值，称为最大堆、大根堆、大顶堆；
如果任意节点的值 $\leq$ 子节点的值，称为最小堆、小根堆、小顶堆；

3. 二叉堆 (Binary Heap)

二叉堆的数据结构是一棵完全二叉树，因此也被称为完全二叉堆;
鉴于二叉堆的结构，底层可以用数组实现；

最大二叉堆数据结构

二叉堆的索引规律（从0开始，与数组对应）

i = 0 , 表示根节点；
i > 0 ，则父节点索引为floor( (i-1) / 2)；
如果 2i + 1 <= n - 1，它的左子树索引为 2i + 1 ；
如果 2*i + 1 > n - 1 ，该节点无左子树；
如果 2i + 2 <= n -1 ,该节点的右子节点索引为 2i + 2;
如果 2*i + 2 > n - 1，该节点无右子节点；

二叉堆的接口设计

int size(); $\qquad$ //返回二叉堆元素个数；
boolean isEmpty(); $\qquad$ //判断是否为空；
void clear(); $\qquad$ //清空二叉堆；
void add(E element); $\qquad$ //添加元素；
E get(); $\qquad$ //获取堆顶元素；
E remove(); $\qquad$ //删除堆顶元素；
E replace(E element); $\qquad$ //替换堆顶元素

4. 二叉堆获取最大值

获取堆顶，就能获取最大值

public E get() {
        emptyCheck();
        return elements[0];
    }

5. 二叉堆添加元素

二叉堆添加元素（添加85）

如果node的值 > 父节点的值；

与父节点交互位置

如果node的值 <= 父节点的值，或者node没有父节点；

退出循环

这个过程叫做上滤(Sift Up)；

时间复杂度为 O( log n)

// 添加元素
public void add(E element) {
        elementNotNullCheck(element);
        ensureCapacity(size + 1);
        elements[size++] = element;
        siftUp(size - 1);
    }
// 上滤
private void siftUp(int index) {
        E e = elements[index];
        while (index > 0) {
            int pindex = (index - 1) >> 1;
            E p = elements[pindex];
            if (compare(e, p) <= 0) return;
            
            // 交换index、pindex位置的内容
            E tmp = elements[index];
            elements[index] = elements[pindex];
            elements[pindex] = tmp;
            
            // 重新赋值index
            index = pindex;
        }
        
    }

6. 二叉堆删除最大值

二叉堆删除元素（删除85）

堆是一种数据结构，只能删除堆顶元素，所以删除 最大值，不能删除其他位置的，参考栈结构。删除的操作如下：

将存放堆的数组最后一个元素，覆盖堆顶（node），然后将数组最后一个元素删除；
如果该节点（node）的值 < 最大子节点的值；

将node与子节点交互位置；

如果该节点（node）的值 >= 最大子节点的值，或者已经没有子节点了；

退出循环；

该过程称为下滤（Shit Down）;

时间复杂度为 O( log n)

// 删除堆顶
public E remove() {
        emptyCheck();
        
        int lastIndex = --size;
        E root = elements[0];
        elements[0] = elements[lastIndex];
        elements[lastIndex] = null;
        
        siftDown(0);
        return root;
    }

     // 下滤
    private void siftDown(int index) {
        E element = elements[index];
        int half = size >> 1;
        // half 为第一个叶子节点索引
        while (index < half) { 
            // index的节点有2种情况
            // 1.只有左子节点
            // 2.同时有左右子节点
            
            // 获取左子节点
            int childIndex = (index << 1) + 1;
            E child = elements[childIndex];
            
            // 获取右子节点
            int rightIndex = childIndex + 1;
            
            // 选出最大的子节点
            if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
                child = elements[childIndex = rightIndex];
            }
            
            if (compare(element, child) >= 0) break;

            // 将子节点存放到index位置
            elements[index] = child;
            // 重新设置index
            index = childIndex;
        }
        elements[index] = element;
    }

6. 二叉堆替换堆顶元素

替换（replace）和删除最大值一样，都是替换堆顶元素，然后判断是否大于 最大子节点，如果大于，那么进行下滤，直到小于或者是叶子节点才退出循环；

public E replace(E element) {
        elementNotNullCheck(element);
        
        E root = null;
        if (size == 0) {
            elements[0] = element;
            size++;
        } else {
            root = elements[0];
            elements[0] = element; // 替换堆顶
            siftDown(0); //下滤
        }
        return root;
    }

7. 小顶堆的创建

以上所讲的都是大顶堆，小顶堆的创建非常简单，只要修改compare的函数就可以。

小顶堆

// 大顶堆的compare
public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }

// 小顶堆的compare
public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }

8. 应用

1. Top k 问题

从n个整数/浮点数中，取出k个最大值，其中 k 远远小于 n；
可以使用全排序进行来得出最大的k个值，但是时间复杂度为O( n log n);
使用二叉堆，时间复杂度为 O( n log k);

步骤如下：

创建一个小顶堆；
遍历这n个值；

先将 k 个值，添加到小顶堆中；
从第k+1个值开始，先获取堆顶元素（ heap.get() ），比较；
如果大于堆顶元素，替换堆顶，进行下滤操作；
如果小于等于堆顶元素，循环下一个元素；

遍历结束后，存放k个值的小顶堆，就是存放最大的k个值；

for (int i = 0; i < data.length; i++) {
            if (heap.size() < k) { // 前k个数添加到小顶堆
                heap.add(data[i]); 
            } else if (data[i] > heap.get()) { // 如果是第k + 1个数，并且大于堆顶元素
                heap.replace(data[i]); 
            }
        }

2. 优先级队列

创建一个大顶推；
设置队列节点的优先级权重；
以权重来实现作为compare的判断条件；
这样权重最大的节点，被放在堆顶，权重越小的就放在后面的节点；
在执行队列时，会调用remove()，获取堆顶的节点，执行操作；

1. 思考

2. 堆 (Heap)

3. 二叉堆 (Binary Heap)

4. 二叉堆 获取最大值

5. 二叉堆 添加元素

6. 二叉堆 删除最大值

6. 二叉堆 替换堆顶元素