二叉堆

1. 思考

• Top k 问题： 从海量数据中获取前k个 最大值 或 最小值；
  比如从 一百万 个整数中，获取最大的1000个整数；

• 设计一种数据结构，用来存放整数元素，包括的操作是 获取最大值，添加元素，删除最大值：
  

  各数据结构的时间复杂度对比

• 为了能达到最优，使用 堆：
  堆：获取最大值时间复杂度O(1)，添加元素时间复杂度O(log n)，删除最大值时间复杂度O(log n)；

---

2. 堆 (Heap)

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

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

2. 堆的最重要性质：任意节点的值总是 或者 子节点的值：

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

---

3. 二叉堆 (Binary Heap)

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

最大二叉堆数据结构

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

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

• 二叉堆的接口设计

1. int size(); //返回二叉堆元素个数；
2. boolean isEmpty(); //判断是否为空；
3. void clear(); //清空二叉堆；
4. void add(E element); //添加元素；
5. E get(); //获取堆顶元素；
6. E remove(); //删除堆顶元素；
7. E replace(E element); //替换堆顶元素

---

4. 二叉堆 获取最大值

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

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

5. 二叉堆 添加元素

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

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

• 与父节点交互位置

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

• 退出循环

3. 这个过程叫做上滤(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）

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

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

• 将node与子节点交互位置；

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

• 退出循环；

4. 该过程称为下滤（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);

步骤如下：

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

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

3. 遍历结束后，存放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()，获取堆顶的节点，执行操作；