堆

1. 堆的特点(二叉堆)

• 堆的父节点一定比子节点的值要大(或小)，称为大根堆(或小根堆)

• 二叉堆的逻辑结构就是一棵完全二叉树，所以也叫完全二叉堆

• 二叉堆的底层结构一般使用数组实现

  i	0	1	2	3	4	5	6	7	8	9
  value	72	68	50	43	38	47	21	14	40	3

• 索引的i的规律

  如果i = 0，它是根节点

  如果i > 0，它的父节点编号为floor(i - 1) / 2

  如果2*i + 1 <= n - 1，它的左子节点编号为2*i + 1

  如果2*i + 1 > n - 1，它无左子节点

  如果2*i + 2 <= n - 1，它的右子节点编号为2 * i + 2

  如果2*i + 2 > n - 1，它无右子节点

2. 主要方法

public interface Heap <E>{
    int size(); // 元素的数量
    boolean isEmpty(); // 对是否为空
    void clear(); //清空堆
    void add(E element); // 添加元素
    E get(); // 获取堆顶元素
    E remove(); // 删除堆顶元素
    E replace(E element); // 删除堆顶元素的同时添加一个元素
}

2.1 属性和构造函数

1. 属性

   private E[] elements;
   private int size;
   private Comparator<E> comparator;
   private static final int DEFAULT_CAPACITY = 10;
   

2. 构造函数

   public BinaryHeap(Comparator<E> comparator) {
       this.comparator = comparator;
       this.elements = (E[]) new Object[DEFAULT_CAPACITY];
       this.size = 0;
   }
   
   public BinaryHeap() {
   	this(null);
   }
   

2.2 几个辅助方法

1. 比较，插入堆中的元素必须是可比较的

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

2. 检查heap是否为空

   private void emptyCheck() {
       if (size == 0) {
       	throw new IndexOutOfBoundsException("Heap is empty");
       }
   }
   

3. 检查插入的元素是否为null，堆中不允许插入null值

   private void elementNotNullCheck(E element) {
       if (element == null) {
       	throw new IllegalArgumentException("Element is not null");
       }
   }
   

4. 数组扩容

   private void ensureCapacity(int capacity){
       if (elements.length >= capacity) {
       	return;
       }
       // 扩容数组的容量为原来的1.5倍
       E []newElements = (E[])new Object[elements.length + (elements.length >> 1)];
       for(int i = 0; i < size; i++){
       	newElements[i] = elements[i];
       }
       elements = newElements;
   }
   

3. 添加元素

假设现在添加的元素为node

1. 如果node大于父节点与父节点交换位置
2. 如果node小于或者等于父节点，或者node没有父节点，退出循环

以上的过程称为上滤Sift Up，时间复杂度为O(logn)

public void add(E element) {
    // 检查元素是否为空, 二叉堆不允许插入null值
    elementNotNullCheck(element);
    // 检查数组容量
    ensureCapacity(size + 1);
    elements[size++] = element;
    siftUp(size - 1);
}

// 上滤
private void siftUp(int index) {
    E element = elements[index];
    int parent;
    while(index > 0) {
        parent = (index - 1) >> 1;

        // 小于父节点无需上滤
        if (compare(elements[parent], element) >= 0) return;

        // 将父元素放在index的位置
        elements[index] = elements[parent];
        index = parent;
    }
    // 将要添加的元素放在指定的位置
    elements[index] = element;
}

4. 删除元素

4.1 删除堆顶元素

堆的删除就是删除堆顶元素。原理就是利用数组的最后一个元素覆盖堆顶的元素，然后对堆顶元素进行下滤

具体步骤

1. 用最后一个节点覆盖根节点

2. 删除最后一个节点

3. 循环执行以下操作

   如果node < 子节点，从子节点中选出最大的与node进行交换

   如果node >= 子节点或者没有子节点，结束循环

时间复杂度O(logn)

public E remove() {
    emptyCheck();

    E root = elements[0];
    elements[0] = elements[size - 1];
    elements[--size] = null;

    siftDown(0);
    return root;
}

private void siftDown(int index) {
    E element = elements[index];

    int half = size >> 1; // 非叶子节点的个数
    // 第一个叶子节点的索引 == 非叶子节点的个数
    // index应该是非叶子节点
    while (index < half) {
        // index 的节点有2种情况
        // 1. 只有左子节点
        // 2. 同时有左右子节点
        int child  = (index << 1) + 1; // 默认为左子节点

        // 选出最大子节点
        if (child + 1 < size && compare(elements[child], elements[child + 1]) < 0) {
            child++;
        }

        if (compare(element, elements[child]) >= 0) break; // 如果比子节点大，结束循环

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

4.2 删除堆顶并插入一个元素

public E replace(E element) {
    elementNotNullCheck(element);

    E root = null;
    if (size != 0) {
        root = elements[0];
        elements[0] = element;
        siftDown(0);
    } else {
        elements[size++] = element;
    }
    return root;
}

5. 建堆

给定一个数组，原地建堆

添加一个构造器

public BinaryHeap(E []elements, Comparator<E> comparator) {
    super(comparator);
    if (elements == null || elements.length == 0) {
    	this.elements = (E[]) new Object[DEFAULT_CAPACITY];
    } else {
        // 保存数组
        this.elements = (E[]) new Object[Math.max(elements.length, DEFAULT_CAPACITY)];
        for(int i = 0; i < elements.length; i++) {
        	this.elements[i] = elements[i];
        }
        size = elements.length;
        heapify();
    }
}

5.1 自上而下的上滤

从堆顶开始，对每一个元素进行上滤，第一个元素没必要进行上滤

时间复杂度O(nlogn)

private void heapify() {
    // 自上而下上滤
    for(int i = 1; i < elements.length; i++) {
    	siftUp(i);
    }
}

5.2 自下而上的下滤

从堆底的第一个非叶子节点开始读每个元素进行下滤。(叶子节点没必要进行下滤)

时间复杂度O(n)

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