数据结构篇|堆

一、什么是堆

堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

• 堆中某个节点的值总是不大于或不小于父节点的值
• 堆是一棵完全二叉树

二、实现一个堆

实现堆这里复用前面实现的数组对象，连接如下：

Array类

接着创建一个类叫做MaxHeap因为是基于二叉树，所以需要继承Comparable接口

public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;
    public MaxHeap(int capacity) {
        data = new Array<>(capacity);
    }
    public MaxHeap() {
        data = new Array<>();
    }
}

这里需要一个数组的参数data，如果知道需要的容量可以传入容量，否则直接进行初始化。

• getSize()、isEmpty()方法

    public int getSize() {
        return data.getSize();
    }

    public boolean isEmpty() {
        return data.isEmpty();
    }

这两个方法直接调用array类中的方法即可。

• parent()、leftChild()、rightChild()方法

    //根据传入的节点索引，计算父节点的索引
    private int parent(int index) {
        if (index == 0){
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        }
        return (index - 1) / 2;
    }

    //传入节点的索引计算左孩子的索引
    private int leftChild(int index){
        return (index * 2) + 1;
    }

    //传入节点的索引计算有孩子的索引
    private int rightChild(int index){
        return (index * 2) + 2;
    }

这三个方法是基于数组中的索引计算出父子节点的索引。

• swap()方法

    public void swap(int i, int j){
        if (i < 0 || i >= size || j < 0 || j >=size){
            throw new IllegalArgumentException("Index is illegal.");
        }

        E t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

堆只有在满足了它的性质才是合法的，对此可能就会需要将元素进行上浮和下沉等操作，而这两个操作的实质就是将某个节点与自己的父节点进行位置的交换，所以在Array类创建swap()方法，方法的实现显而易见，就是判断了参数合法性之后进行位置的交换即可。

• siftUp()方法

    private void siftUp(int k) {
        while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
            //将k位置的元素与k的父元素进行位置交换
            data.swap(k, parent(k));
            k = parent(k);
        }
    }

这个方法是通过传入索引并判断索引的合法性，进行元素位置交换操作的，所以只需要调用swap()方法，交换完成后将parent(k)的索引赋给k即可。

• add()方法

    public void add(E e) {
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }

添加方法只需要向数组末尾添加元素，然后再将最后位置的元素进行上浮操作即可。

• findMax()

    //查看堆中最大元素
    public E findMax(){
        if (data.getSize() == 0){
            throw new IllegalArgumentException("Can not findMax when heap is empty.");
        }
        return data.get(0);
    }

查找堆中的最大元素，首先需要判断堆中是否有元素，如果没有就抛出异常，否则就将最大元素返回。

• siftDown()

    private void siftDown(int k){
        while (leftChild(k) < data.getSize()){
            int j = leftChild(k);
            //k如果有右孩子，并且右孩子的值比左孩子大
            if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0){
                //将右孩子进行存储
                j = rightChild(k);
            //data[j]是k的左右孩子的最大值
            }
            //如果k元素比j元素还要大
            if (data.get(k).compareTo(data.get(j)) >= 0){
                //条件满足
                break;
            }
            //否则将元素位置进行交换
            data.swap(k, j);
            k = j;
        }
    }

该方法需要输入某个元素的索引k，如果k的左孩子存在，就将k的左孩子下标进行保存，这里使用变量j。然后再判断索引k位置是否有右孩子，如果有便将j进行更新，此时j保存的就是索引k位置的最大子节点的索引。再判断索引k的值是否大于等于索引j的值，如果满足就结束循环，否则将k和j进行位置的交换并保存。

• extractMax()方法

    public E extractMax(){
        E ret = findMax();
        //将第一个元素和最后一个元素交换位置
        data.swap(0,data.getSize() - 1);
        data.removeLast();
        siftDown(0);
        return ret;
    }

准备工作都做好了，接下来就可以编写删除最大值的函数了，首先需要将最大值保存起来，并将其返回。在代码的中间需要将最大元素与最小元素进行位置的交换，然后删除最大元素，再将最小元素进行下沉操作即可。

• replace()

    public E replace(E e){
        E ret = findMax();
        data.set(0,e);
        siftDown(0);
        return ret;
    }

这个函数用于取出堆中最大元素，并替换成元素e，首先要将最大元素保存，然后将元素e设置到堆顶的位置，再维护一下堆的合法性，最终将保存的ret返回。