堆和优先队列

1.优先队列的概念

优先队列和其实是队列的一种

普通队列：先进先出；后进先出

优先队列：出队顺序和入队顺序无关；和优先级相关

优先队列的接口和普通队列的接口是完全相同的，只是在出队和查看队首的实现方式会不同（优先级最高的在队首）；

优先队列可以使用不同的底层数据结构来实现

 

我们对队列这种抽象的数据结构做一些限制，创造出优先队列这个概念，我们在实现这个概念时可以使用不同的底层实现，这是很重要的一种思想。

 

2.堆

如果算法里面的时间复杂度是O(logn)，那么近乎一定和树这种结构有关。当然我们不一定要显示的构造一棵树，比如像归并排序，快速排序等，它们都是nlogn级别的，它们在排序过程中没用用树这种结构，但是在递归的过程形成一棵隐形的递归树。

堆本身也是一棵树，其实堆也有很多种，我们在这里主要使用二叉树来表示堆，说白了，二叉堆就是满足一些特殊性质的二叉树：

1）二叉堆是一棵完全二叉树

2）堆中某个节点的值总是不大于其父节点的值（所以也叫做最大堆），注意：层次大的元素值不一定小于层次小的元素

注：

满二叉树：满二叉树就是对于整颗树来说，除了叶子节点，所有的节点左右孩子都不为空如下图

完全二叉树：不一定是满二叉树，但它不满的那一部分，也就是缺失节点的那一部分一定是在整颗树的右下侧。对于一个满二叉树来讲，一个树有多少层，节点有多少个其实是固定的（如一层有1个，二层有3个，三层6个），但很多时候我们的元素数量不符合满二叉树的元素数量，所以我们当一层满了后再进入下一层，且从左向右排列元素（即元素一层一层的放）

 

二叉树可以和二叉树一样使用左右节点的方式来实现，但是我们可以看到我们现在是一层一层按顺序排放的，所以我们可以用更巧妙的方式来实现（数组）

 

知道这些概念之后我们下把最大堆的基础架构写出来：完整代码在我github上： 点击

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
    public MaxHeap(E[] arr){
        data = new Array<>(arr);
        for(int i = parent(arr.length - 1) ; i >= 0 ; i --)
            siftDown(i);
    }



    // 返回一个布尔值, 表示堆中是否为空
    public boolean isEmpty(){
        return data.isEmpty();
    }

    // 返回堆中的元素个数
    public int size(){
        return data.getSize();
    }


    // index节点的parent索引
    private int parent(int index){
        if(index == 0)
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        return (index - 1) / 2;
    }
    // index节点的左孩子节点的索引
    private int leftChild(int index){
        return index * 2 + 1;
    }
    // index节点的右孩子节点的索引
    private int rightChild(int index){
        return index * 2 + 2;
    }
}

其中Array是自己定义的动态数组；

接下来我们就要讲解堆中的核心代码了

 

 

2.1 堆中添加元素和Shift Up

现在我们要添加元素52，先添加到索引为10的位置，然而现在不满足二叉堆的性质，所以要调整52的位置，所以让52和自己的父亲节点依次与父亲节点相比较，如52大于父亲节点，就交换52与父亲节点的位置-------Shift up

    // 向堆中添加元素
    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(k, parent(k));
            k = parent(k);
        }
    }

 

 

2.2 堆中取出元素(最大值)和Shift Down

我们先取出最大值62，因为将两颗子树融合成一棵树比较复杂，所以我们可以把最小值16换到根节点，然后在采用shift-down操作，

shift-down：把16与左右两个孩子节点相比较，选择两个孩子中最大的那个元素，如果最大的那个元素比16大，则将16与它交换，很显然52与16做交换

探后继续与41做交换

因为16比15大，所以就完成啦

我们来看下代码:
 

 // 取出堆中最大元素
    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);                                                          // 在此轮循环中,data[k]和data[j]交换位置
            if( j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0 ){
                j ++;                                                                       // data[j] 是 leftChild 和 rightChild 中的最大值
            }
            if(data.get(k).compareTo(data.get(j)) >= 0 ){
                break;
            }
            
            data.swap(k, j);
            k = j;
        }
    }

 

 

2.3 Heapify

从倒数第一个非叶子节点（22）开始shift-Down操作，那么怎么得到最后一个非叶子节点？很简单，找到最后一个节点，然后求出最后一个叶子节点的父节点即可，我们来看代码：

    //构造函数，将传入的数组变成堆  Heapify
    public MaxHeap(E[] arr){
        data = new Array<>(arr);
        for(int i = parent(arr.length - 1) ; i >= 0 ; i --)
            siftDown(i);
    }

 

 

3.优先队列

前面我们可以用堆来构造优先队列，很简单，优先队列里面的优先队列的接口都可以服用堆中的优先队列

public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {

    private MaxHeap<E> maxHeap;

    public PriorityQueue(){
        maxHeap = new MaxHeap<>();
    }

    @Override
    public int getSize(){
        return maxHeap.size();
    }

    @Override
    public boolean isEmpty(){
        return maxHeap.isEmpty();
    }

    @Override
    public E getFront(){
        return maxHeap.findMax();
    }

    @Override
    public void enqueue(E e){
        maxHeap.add(e);
    }

    @Override
    public E dequeue(){
        return maxHeap.extractMax();
    }
}