堆（Heap）

  • 堆也是一种树状的数据结构，不要跟内存模型中的堆空间混淆，常见的堆有
    • 二叉堆（Binary Heap），完全二叉堆
    • 多叉堆（D-Heap、D-ary Heap）
    • 索引堆（Index Heap）
    • 二项堆（Binomial Heap）
    • 斐波那契堆（Fibonacci Heap）
    • 左倾堆（Leftist Heap），左式堆
    • 斜堆（Skew Heap）

  • 堆的一个重要性质：任意节点的值总是 >= (<=) 其子节点的值

    • 如果任意节点的值总是大于等于其子节点的值，称为最大堆、大顶堆、大根堆
    • 如果任意节点的值总是小于等于其子节点的值，称为最小堆、小顶堆、小根堆
    • 堆中的元素必须具备可比较性（跟二叉搜索树是一样的）

      堆的接口设计

  • int size();//元素的数量

  • boolean isEmpty();//堆是否为空
  • void clear();//清空堆
  • void add(E element);//往堆中添加元素
  • E get();//获取堆顶元素
  • E remove();//删除堆顶元素
  • E replace(E element);//删除堆顶元素，并新添加一个元素

二叉堆（Binary Heap）

  • 二叉堆的逻辑结构就是一颗完全二叉树，所以也叫完全二叉堆
  • 鉴于完全二叉树的一些特性，二叉堆的底层（物理结构）一般用用数组实现

  • 索引 i 的规律（n是元素数量）：

    • 如果 i 等于0，它是根节点
    • 如果 i > 0，它的父节点索引是 floor（ (i-1)/2 ）
    • 如果2i+1 <= n-1，它的左子节点索引是 2i+1
    • 如果2i+1 > n-1，它没有左子节点
    • 如果2i+2 <= n-1，它的右子节点索引是 2i+2
    • 如果2i+2 > n-1，它没有右子节点

      获取最大值

  • 最大堆的特点就是 ，根节点是最大的，对应索引位置为0的元素

    2.   @Override
    3.   public E get() {
    4.       emptyCheck();
    5.       return elements[0];
    6.   }
    8.   private void emptyCheck() {
    9.       if (size == 0) {
    10.           throw new IndexOutOfBoundsException("heap is empty");
    11.       }
    12.   }

    最大堆-添加元素

    image.png
    image.png

    最大堆-删除元素

    image.pngimage.png