二叉堆

1、思考

设计一种数据结构，用来存放整数，用来提供3个接口：

• 1、添加元素
• 2、获取最大值
• 3、删除最大值

image.png

	获取最大值	删除最大值	添加元素
动态数组 / 双向链表	O(n)	O(n)	O(1)
有序的动态数组 / 双向链表	O(1)	O(1)	O(n)	全排序有点浪费
BBST	O(logn)	O(logn)	O(logn)	杀鸡用了牛刀

有没有更好的数据结构？

堆：获取最大值：O(1)；删除最大值：O(logn)；添加元素：O(logn)。

2、堆（Heap）

堆（Heap）：也是一种树状的数据结构（注意不要和内存模型中的“堆空间”混淆），常见的堆有：

• 1、二叉堆：Binary Heap，它的逻辑数据结构和完全二叉树相同，所以又叫完全二叉堆。但是其物理结构是数组。
• 2、多叉堆
• 3、索引堆
• 4、二项堆
• 5、斐波那契堆
• 6、左倾堆
• 7、斜堆
  堆有一个重要的性质：任意节点的值总是>=(<=)子节点的值。

• 如果任意节点的值总是>=子节点的值，称为：最大堆、大根对、大顶堆。
• 如果任意节点的值总是<=子节点的值，称为：最小堆、小根堆、小顶堆。
  image.png
  由此可见：堆中的元素需要具有可比较性和二叉搜索树相同。

2.1、接口设计

public interface Heap<E> {

    int size(); //元素的数量
    
    boolean isEmpty();//是否为空
    
    void clear();//清空元素
    
    void add(E element);//添加元素
    
    E get();//获取堆顶元素
    
    E remove();//删除堆顶元素
    
    E replace(E element);//删除堆顶元素并新增一个新的元素
}

3、二叉堆（Binary Heap）

• 二叉堆的逻辑结构就是一个完全二叉树，所以也叫完全二叉堆。
• 鉴于完全二叉树是从上到下，从左到右依次排列的，二叉堆的底层（物理结构）一般使用数组来实现。
  image.png
• 索引i的规律（n是元素的数量）

1、如果i = 0，它是根节点
2、如果i > 0 ，它的父节点的索引=floor(( i - 1) /2)
3、如果 2i + 1 <= n - 1，它的左子节点的索引=2i+1；
如果2i + 1 > n - 1，它无左子节点。
4、如果2i + 2 <= n - 1，它的右子节点的索引=2i + 2
如果2i + 2 > n - 1，它没有右子节点。

3.1、get()

get()方法是获取堆顶元素，堆顶元素就是数组索引为0的元素

/**
 * 获取堆顶元素
 */
@Override
public E get() {
    emptyCheck();
    return elements[0];
}

3.2、最大堆-添加add(E element)

以下图为例，描述一下添加的流程

image.png
添加流程总结如下：
node为新添加的节点
循环执行如下操作：

• 1、如果node的值 > 父节点的值，则与父节点交换位置。
• 2、如果node的值 < 父节点的值，或者没有父节点，则退出循环。
  这个循环过程叫做：上滤（Sift Up）。

上滤的时间复杂度为：O(logn)
具体实现

@Override
public void add(E element) {
    elementEmptyCheck(element);
    ensureCapacity(size + 1);
    // 1、先添加到数组的最后
    elements[size] = element;
    siftUp(size);
    size++;
}

/**
 * 上滤指定位置的元素
 * 
 * @param index
 */
private void siftUp(int index) {
    E element = elements[index];
    // index>0表示有父节点
    while (index > 0) {
        int parentIndex = (index - 1) >> 1;
        E parentElement = elements[parentIndex];
        if (compare(element, parentElement) <= 0)
            break;
                //交换位置
        E temp = elements[index];
        elements[index] = elements[parentIndex];
        elements[parentIndex] = temp;
        // 重新赋值index
        index = parentIndex;
    }
}

最大堆-添加的优化

• 一般交换元素的位置需要3行代码，可以进一步优化：
  将新添加的节点备份，确定最终位置后才摆放上去：
  image.png
  优化后的代码如下

@Override
public void add(E element) {
    elementEmptyCheck(element);
    ensureCapacity(size + 1);
    // 1、先添加到数组的最后
    elements[size] = element;
    siftUp(size);
    size++;
}

/**
 * 上滤指定位置的元素
 * 
 * @param index
 */
private void siftUp(int index) {
    E element = elements[index];
    // index > 0 表示有父节点
    while (index > 0) {
        int parentIndex = (index - 1) >> 1;
        E parentElement = elements[parentIndex];
        if (compare(element, parentElement) <= 0)
            break;
        //将父元素存储在index位置
        elements[index] = parentElement;
        //将父元素index赋值给
        index = parentIndex;
    }
    elements[index] = element;
}

3.3、最大堆-删除-remove()

remove()删除的是堆顶元素。
使用下图描述下删除的过程：

image.png
删除过程总结如下：

• 1、将最后一个节点的值覆盖根节点的值。
• 2、删除最后一个节点。
• 3、循环执行以下过程：(上图中的43为node)
  a、如果node<最大子节点的值，则交换位置。
  b、如果节点>=最大子节点的值，或没有子节点，则退出循环。
  这个过程称为下滤。
  具体的实现如下：

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

/**
 * 让指定位置的元素下滤
 * 
 * @param index
 */
private void siftDown(int index) {
    E element = elements[index];
    // 退出没有子节点或者指定位置的值大于子节点的值，二叉堆的逻辑结构是完全二叉树，所以叶子节点的个数为n/2
    int half = size >> 1;
    while (index < half) {
        // 完全二叉树如果有一个子节点肯定是左子节点
        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;
    }
}

3.4、replace()

replace()的作用是删除堆顶元素，并添加新元素

/**
 * 删除堆顶元素，并添加新元素
 */
@Override
public E replace(E element) {
    elementEmptyCheck(element);
    E root = null;
    if (size == 0) {
        elements[0] = element;
        size++;
    } else {
        root = elements[0];
        elements[0] = element;
        siftDown(0);
    }
    return root;
}

需要注意size==0的情况。如果数组为空，则直接添加即可。

4、最大堆-批量建堆（Heapify）

批量建堆就是将存在的一堆数据批量的添加到堆中，而不是遍历数组将元素一个一个添加到堆中。
批量建堆的方式有两种：

• 1、自上而下的上滤。
• 2、自下而上下滤。

4.1、自上而下的上滤

image.png

代码如下：

/**
 * 自上而下的上滤
 */
public void heapify1() {
    for (int i = 1; i < size; i++) {
        siftUp(i);
    }
}

4.2、自下而上的下滤

image.png

代码实现如下：

/**
 * 自下而上的下滤
 */
public void heapify2() {
    for (int i = ((size >> 1) - 1); i >= 0; i--) {
        siftDown(i);
    }
}

4.3、批量建堆-效率对比

image.png

• 1、自上而下的上滤

1、所有节点的深度之和
a、仅仅是叶子节点的个数就有n/2个，而且每一个叶子节点的深度都是O(logn)级别的，因此在叶子节点这一块就达到了O(nlogn)级别了。
b、O(nlogn)的时间复杂度足以对所有节点进行全排序。

• 2、自下而上的下滤

1、所有节点的高度之和
a、假设是满树，节点总数为n，树高为h，则n = 2^h - 1.
b、所有节点的高度之和H(n) = 2^0 * (h - 0) + 2^1 * (h - 1)+2 ^2 * (h-2)+....+2^(h-1) * (h-(h-1))
推导过程如下：
H(n)=h*(2^0 + 2^1 + ...+ 2^(h-1)) - [ 1 * 2^1 + 2 * 2^2 + 3 * 2^3 + ... + (h- 1) * 2^(h-1) ]
H(n)=2n-log2(n+1) = O(n)

5、如何构建小顶堆

在构建大顶堆时添加、删除时我们都是使用compare()方法进行比较的。

private int compare(E e1, E e2) {
    if (comparator != null)
        return comparator.compare(e1, e2);
    return ((Comparable<E>) e1).compareTo(e2);
}