堆

二叉堆：特殊的树结构

• 完全二叉树(把元素顺序排列成树的形状，且缺失节点的部分一定在整棵树的右下侧)
• 堆中的某个节点的值总是不大于其父亲节点的值(最大堆)
• 根节点的元素是最大的元素，大于其左右子树所有节点的值。

用数组存储二叉堆

堆的基本操作

代码示例

public class MaxHeap <E extends Comparable<E>> {

    private Array<E> data;

    public MaxHeap(int capacity) {
        data = new Array<>(capacity);
    }

    public MaxHeap(){
        data = new Array<>();
    }

    //Heapify 将数组转成Heap 使从0开到到最后一个非叶子节点的index(最后一个元素的父亲节点) 实现下沉
    public MaxHeap(E[] arr){
        data = new Array<>(arr);
        if (arr.length != 1)
            for (int i = parent(arr.length - 1); i >= 0; i--)
                siftDown(i);
    }


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

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

    // 返回完全二叉树的数组表示中，一个索引所表示的父亲节点的索引
    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;
    }

    //取出堆中最大元素
    public E findMax(){
        if (data.getSize() == 0)
            throw new IllegalArgumentException("Heap is empty");
        return data.get(0);
    }
}

添加元素到二叉堆中

    //向堆中添元素
    public void add(E e){
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }

    private void siftUp(int k){
        //判断当前节点与其父节点的大小
        while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
            data.swap(parent(k), k);
            k = parent(k);
        }
    }

添加元素
添加元素

取出最大元素 只取出堆顶 只能取出堆顶

    //向堆中取出元素
    public E extractMax(){
        E ret = findMax();
        //交换最后一个元素与最大元素
        data.swap(0, data.getSize() - 1);
        //删掉最后一个元素
        data.removeLast();
        siftDown(0);
        return ret;
    }

    private void siftDown(int k){
        //数组没有越界
        while (leftChild(k) < data.getSize()){
            //左孩子一定存在
            int j = leftChild(k);
            //是否有右孩子 并判断右孩子与左孩子的大小
            if(j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0)
                //右孩子比左孩子大 j存右孩子
                j = rightChild(k);
            //data[j] 是左右孩子的最大值
            if (data.get(k).compareTo(data.get(j)) >= 0)
                break;

            data.swap(k, j);
            k = j;
        }
    }

取出堆顶元素
将最后一个元素顶到堆顶
删除最后一个元素
堆顶元素实现下沉以保证二叉堆的性质
下沉最后结果

取出最大元素并替换一个新元素

• 先取出最大元素，在添加元素，执行2次O(logn)操作
• 直接将堆顶元素替换以后sift down，只执行一次O(logn)的操作

    // 取出堆中的最大元素 并替换成e
    public  E replace(E e){
        E ret = findMax();
        data.set(0, e);
        siftDown(0);
        return ret;
    }

堆排序

    public static <E extends Comparable<E>> void sort(E[] data){
        MaxHeap<E> maxHeap = new MaxHeap<>();
        for (E e: data)
            maxHeap.add(e);

        for (int i = data.length - 1; i>= 0; i --)
            //拿出堆中最大的元素 放入数组的最后
            data[i] = maxHeap.extractMax();
    }
//时间复杂度 O(nlogn)

Heapify

将任意数组整理成堆的形状(找到当前数组中最后一个非叶子节点，向前实行sift down)，最有一个节点的父亲节点即为最后一个非叶子节点。

    //Heapify 将数组转成Heap 使从0开到到最后一个非叶子节点的index(最后一个元素的父亲节点) 实现下沉
    public MaxHeap(E[] arr){
        data = new Array<>(arr);
        if (arr.length != 1)
            for (int i = parent(arr.length - 1); i >= 0; i--)
                siftDown(i);
    }
时间复杂度：O(n)

依次对索引为4 3 2 1 的节点进行下沉
下沉结束

优化后的堆排序

    //优化后的堆排序
    public static <E extends Comparable<E>> void sort2(E[] data){
        if (data.length <= 1) return;
        //heapify 过程
        for (int i = (data.length - 2)/2; i >= 0; i--)
            siftDown(data, i, data.length);


        for (int i = data.length - 1; i >= 0 ; i--) {
            //交换堆中最大的元素放到数组最后位置
            //每次都将堆中的最大元素放到数组的最后一个，然后将剩余的堆进行siftdown
            swap(data,0, i);
            siftDown(data, 0, i);
        }
    }

    //对data[0, n) 所形成的最大堆中，索引为k的元素，执行 siftDown
    private static <E extends Comparable<E>> void siftDown(E[] data,int k, int n){
        //数组没有越界
        while (2 * k + 1 < n){
            //左孩子一定存在
            int j = 2 * k + 1;
            //是否有右孩子 并判断右孩子与左孩子的大小
            if(j + 1 < n && data[j + 1].compareTo(data[j]) > 0)
                //右孩子比左孩子大 j存右孩子
                j ++;
            //data[j] 是左右孩子的最大值
            if (data[k].compareTo(data[j]) >= 0)
                break;

            swap(data, k, j);
            k = j;
        }
    }

    private static <E> void swap(E[] arr, int i, int j){
        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }