实现一个简单的小顶堆（MinHeap）

Java实现小顶堆

二叉堆

二叉堆在逻辑结构上完全可以看成是一棵完全二叉树，完全二叉树的性质：

• 非叶子节点层次尽可能排满
• 叶子节点数量为：2^(h-1)个（h>=1），如果不满，则叶子节点要尽可能的靠左排列

按照排序的规则可划分为：

• 小顶堆（小根堆）
• 大顶堆（大根堆）

实现

使用ArrayList动态数组实现二叉堆

为什么不用链表？

数组和链表在入队和出队的操作上的时间复杂度都是O(logn)，但是由于链表需要使用额外的空间来存储节点之间的父子关系，而数组的地址是连续且固定的，可以用简单的公式来表示父子关系，因此采用动态数组而不是链表

父子节点索引关系

父节点索引：parentIndex = (index - 1) / 2（index表示不管是左子节点还是右子节点都可以，计算机在运算时会默认向下取整）

左子节点索引：leftIndex = parentIndex * 2 + 1

右子节点索引：rightIndex = parentIndex * 2 + 2

代码

package Queue;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class MinHeap<E> {
    private List<E> list;
    private Comparator<E> comparator;

    /**
     * todo 构造器
     * 1.空参构造器
     * 2.指定比较器（Comparator）创建最小堆
     * 3.指定数组创建最小堆
     * 4.指定容量创建最小堆
     * 5.指定容量和比较器创建最小堆
     * @param <E>
     */

    /**
     * 空参构造器
     */
    public MinHeap() {
        list = new ArrayList<>();
    }

    /**
     * 指定比较器
     */
    public MinHeap(Comparator<E> comparator) {
        list = new ArrayList<>();
        this.comparator = comparator;
    }

    /**
     * 指定数组
     */
    public MinHeap(E[] array) {
        list = new ArrayList<>(Arrays.asList(array));
        // todo 定义一个方法，将数组转成堆，因为没有指定Comparator，所以使用自然排序
        heapify();
    }

    /**
     * 指定容量
     */
    public MinHeap(int capacity) {
        list = new ArrayList<>(capacity);
    }

    /**
     * 指定容量和比较器
     */
    public MinHeap(int capacity, Comparator<E> comparator) {
        list = new ArrayList<>(capacity);
        this.comparator = comparator;
    }

    /**
     * todo 定义常用方法
     * 1.返回堆中的元素个数
     * 2.判断堆是否为空
     * 3.获取当前节点的父节点索引
     * 4.获取当前节点的左子节点
     * 5.获取当前节点的右子节点
     *
     * 父节点索引和左右子节点索引的关系：
     *  leftIndex = parentIndex * 2 + 1;
     *  rightIndex = parentIndex * 2 + 2;
     *  下面这里不管是leftIndex还是rightIndex都可以，因为计算机会向下取整
     *  parentIndex = (leftIndex - 1) / 2;
     */

    /**
     * 返回最小堆中的元素个数
     * @return
     */
    public int size() {
        return list.size();
    }

    /**
     * 判断堆是否为空
     * @return
     */
    public boolean isEmpty() {
        return list.isEmpty();
    }

    /**
     * 获取当前节点的父节点索引
     * @param index
     * @return
     */
    public int parentIndex(int index) {
        if (index == 0) {
            throw new IllegalArgumentException();
        }
        return (index - 1) / 2;
    }

    /**
     * 获取当前节点的左子节点索引
     * @param index
     * @return
     */
    public int leftIndex(int index) {
        return index * 2 + 1;
    }

    /**
     * 获取当前节点的右子节点
     * @param index
     * @return
     */
    public int rightIndex(int index) {
        return index * 2 + 2;
    }

    /**
     * todo 添加元素的操作
     * 1.把元素添加到数组的末尾
     * 2.判断小顶堆是否失衡，失衡就进行siftUp操作让小顶堆保持平衡
     *
     * todo siftUp
     * 将元素和其父节点比较，比父节点小则跟父节点交换值，循环这种操作直至新元素无法交换
     */
    public void add(E e) {
        // 将新元素添加到数组末尾
        list.add(e);
        siftUp(list.size() - 1);
    }

    private void siftUp(int index) {
        // 将元素索引和其父节点索引比较，比父节点小则跟父节点交换值，循环这种操作直至新元素无法交换
        if (comparator != null) {
            // 指定了比较器
            while (index > 0 && comparator.compare(list.get(parentIndex(index)), list.get(index)) > 0) {
                E tempElement = list.get(index);
                list.set(index, list.get(parentIndex(index)));
                list.set(parentIndex(index), tempElement);
                // 子父节点交换值后要把当前索引赋值为父索引
                index = parentIndex(index);
            }
        } else {
            // 没有指定比较器
            while (index > 0 && ((Comparable) list.get(parentIndex(index))).compareTo(list.get(index)) > 0) {
                E tempElement = list.get(index);
                list.set(index, list.get(parentIndex(index)));
                list.set(parentIndex(index), tempElement);
                index = parentIndex(index);
            }
        }
    }

    /**
     * todo 弹出元素的操作
     * 1.弹出数组第一个元素
     * 2.将数组末端元素移到堆顶
     * 3.判断堆是否失衡，失衡就进行siftDown操作让堆保持平衡
     *
     * todo siftDown
     * 将当前节点的值和min(左子节点, 右子节点)比较，比子节点的值大就交换，否则就结束循环
     */
    public E poll() {
        if (list.isEmpty() || list == null) {
            return null;
        }
        E popElement = list.get(0);
        list.set(0, list.get(list.size() - 1));
        list.remove(list.size() - 1);
        siftDown(0);
        return popElement;
    }

    private void siftDown(int index) {
        if (comparator != null) {
            // 有指定的比较器
            while (leftIndex(index) < list.size()) {
                int tempIndex = leftIndex(index);
                // 如果右子节点存在且其值小于左子节点就替换掉tempindex的值
                if (rightIndex(index) < list.size() && comparator.compare(list.get(leftIndex(index)), list.get(rightIndex(index))) > 0) {
                    tempIndex = rightIndex(index);
                }
                // 如果当前节点的值小于等于子节点的值就退出
                if (comparator.compare(list.get(index), list.get(tempIndex)) <= 0) {
                    break;
                }
                E tempElement = list.get(tempIndex);
                list.set(tempIndex, list.get(index));
                list.set(index, tempElement);
                index = tempIndex;
            }
        } else {
            // 没有指定的比较器
            while (leftIndex(index) < list.size()) {
                int tempIndex = leftIndex(index);
                if (rightIndex(index) < list.size() && ((Comparable) list.get(leftIndex(index))).compareTo(list.get(rightIndex(index))) > 0) {
                    tempIndex = rightIndex(index);
                }
                if (((Comparable) list.get(index)).compareTo(list.get(tempIndex)) <= 0) {
                    break;
                }
                E tempElement = list.get(tempIndex);
                list.set(tempIndex, list.get(index));
                list.set(index, tempElement);
                index = tempIndex;
            }
        }
    }

    /**
     * 将数组转成堆
     */
    private void heapify() {
        // 将最后一个非叶子节点的元素往前遍历并使用siftDown操作插入到堆中
        for (int i = parentIndex(list.size() - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

    /**
     * 查看堆顶元素
     * @return
     */
    public E peek() {
        if (list.isEmpty() || list == null) {
            return null;
        }
        return list.get(0);
    }

}

测试小顶堆：

• 往小顶堆中添加1000_0000个元素
• 定义一个长度为1000_0000的数组，将小顶堆中的元素弹出并保存到数组中
• 判断数组中下一个元素的值是否大于上一个元素的值，大于则证明小顶堆错了

package Queue;

import java.util.concurrent.ThreadLocalRandom;

public class testMinHeap {
    public static void main(String[] args) {
        int n = 1000_0000;
        MinHeap<Integer> minHeap = new MinHeap<Integer>();

        // 往堆中随机存放一千万个元素
        for (int i = 0; i < n; i++) {
            int element = ThreadLocalRandom.current().nextInt(0, n);
            minHeap.add(element);
        }
        int[] arr = new int[n];

        // 将堆中的元素弹出并存到数组中
        for (int i = 0; i < n; i++) {
            arr[i] = minHeap.poll();
        }

        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1] > arr[i]) {
                throw new RuntimeException("error heap");
            }
        }
        System.out.println("小顶堆顺序正确！");
    }
}