二叉堆详解实现优先级队列

二叉堆(Binary Heap)的主要擦走就两个，sink(下沉)和swim(上浮)，用以维护二叉堆的性质，其主要的应用有两个，首先是一种排序方法堆排序，第二种是实现优先级队列

1. 二叉堆概览

首先二叉堆在逻辑上其实是一种特殊的二叉树，只不过存储在数组里。一般的链表二叉树，我们操作节点的指针，而在数组里，我们将数组索引作为指针

//父节点的索引
int parent(int root){
    return root/2;
}
//左孩子的索引
int left(int root){
    return root*2;
}
//右孩子的索引
int right(int root){
    return left(root)+1;//root*2+1
}

其具体结构如图

这是一个字符数组，数组的第一个索引0是空着不用的，其结构是完全二叉树，所以如果把arr[1]作为整棵树的根的话，每个节点的父节点和左右孩子的索引都可以通过简单的运算来得到。

二叉堆还会分为最大堆和最小堆。最大堆的性质是:每个节点都大于等于它的两个子节点。类似的，最小堆的性质是:每个节点都小于等于它的两个子节点

对于一个最大堆，根据其性质，显然堆顶，也就是arr[1]一定会是所有元素中最大的元素

2. 优先级队列概览

优先级队列在你进行插入和删除操作的时候，元素将会自动排序，这底层的原理就是二叉堆的操作

对于优先级队列而言，有两个api，主要是insert插入一个元素和delMax删除最大元素，如果底层是最小堆，那么就是delMin

一个基本的优先级队列定义如下

package dataStruct;

public class MaxPQ <Key extends Comparable<Key>>{//Key可以是任何一种可比较大小的数据类型,比如Integer等
    //存储元素的数组
    private Key[] pq;
    //当前PQ中的元素个数
    private int size = 0;

    public MaxPQ(int cap){
        //索引0是为了来应对根节点寻找父节点的情况的,所以多分配一个内存空间,key extends<key>,属于一个向上转型
        pq = (Key[]) new Comparable[cap+1];
    }

    /*返回当前队列中的最大元素*/
    public Key max(){
        return pq[1];
    }

    /*插入元素e*/
    public void insert(Key e){

    }

    //删除并返回当前队列元素中的最大元素
    public Key deleteMax(){
        return null;
    }

    //上浮第x个元素,以维护最大堆的性质
    private void swim(int x){

    }

    //下沉第x个元素,以维护最大堆的性质
    private void sink(int x){

    }

    //交换数组的两个元素
    private void swap(int i ,int j){
        Key temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    //pq[i]是否比pq[j]要小
    private boolean less(int i,int j){
        return pq[i].compareTo(pq[j]) < 0 ;//如果pq[i] - pq[j] <0那么返回true
    }

    //父节点的索引
    private int parent(int root){
        return root/2;
    }
    //左孩子的索引
    private int left(int root){
        return root*2;
    }
    //右孩子的索引
    private int right(int root){
        return root*2+1;//root*2+1
    }
}

3. 实现swim和sink

在插入和删除元素的时候，难免会破坏堆的性质，这时候就需要通过这两个操作来恢复堆的性质了

对于最大堆，会破坏堆性质的有两种情况

• 如果某个节点A比它的的子节点(中的一个都要)小，那么A就不配做父节点，应该下去，下面那个更大的节点应该上来做父节点，这就是对A进行下沉
• 如果某个节点A比它的父节点要大，那么A就不应该做子节点，应该把父节点换下来，自己去做父节点，这就是对A进行上浮

一般在进行堆的调整的时候，我们的操作一般会在堆底和堆顶进行，显然对于堆顶的错位元素，我们需要进行下沉，对于堆底的错位元素，我们需要进行上浮

//下沉第x个元素,以维护最大堆的性质
private void sink(int x){
    //如果沉到堆底,那么就沉不下去了
    while (left(x) <= size){
        //先假设左边节点比较大
        int max = left(x);
        //如果右边节点存在,比一下大小
        if(right(x) <= size && less(max,right(x))){
            max = right(x);
        }
        //节点x比两孩子都大,就不必下沉了
        if(less(max,x)){
            break;
        }
        //否则不符合最大堆的结构,下沉x节点
        swap(x,max);
        x = max;
    }
}

//上浮第x个元素,以维护最大堆的性质
private void swim(int x){
    //如果浮到堆顶,就不能再上浮了
    while (x>1 && less(parent(x),x)){
        // 如果第x个元素比上层
        //那么就将x换上去
        swap(parent(x),x);
        x=parent(x);
    }
}

4. 实现delMax和insert

这两个方法就是建立在swim和sink上的

insert方法先把要插入的元素添加到堆底最后，然后让其上浮到正确位置

/*插入元素e*/
public void insert(Key e){
    this.size++;
    //先把新元素加到最后
    pq[this.size] = e;
    //然后让它上浮到正确的位置
    this.swim(size);
}

delMax方法先把堆顶元素A和堆底的最后的元素B对调,然后删除A，最后让B下沉到正确的位置

//删除并返回当前队列元素中的最大元素
public Key deleteMax(){
    // 最大堆的堆顶就是最大元素
    Key max = pq[1];
    // 把这最大元素换到最后,删除之
    this.swap(1,size);
    pq[size] = null;
    this.size--;
    //让 pq[1]下沉到正确的位置
    sink(1);
    return max;
}

设K为当前二叉堆(优先级队列)中的元素总数，则插入和删除元素的时间复杂度为O(logK)，因为我们时间复杂度主要花费在了sink或者swim上，无论是上浮还是下沉，最多也就是树堆的高度，时间复杂度是一个log的级别

5. 实现最小堆

package dataStruct;

public class MinPQ <Key extends Comparable<Key>>{
    private int size;
    private Key[] pq;

    public MinPQ(int cap){
        pq = (Key[]) new Comparable[cap+1];
    }
    //将key插入到小顶堆中
    public void insert(){

    }
    //取当前队列中的最小值
    public Key min(){
        return pq[1];
    }
    //删除堆顶并且返回
    public Key deleteMin(){
        return null;
    }
    /*先处理上浮和下沉的逻辑*/
    //上浮
    private void swim(int x){
        //当上浮到1的时候,就代表着最上层没法再上浮了,如果这个数比它的父节点还要小,那就继续浮
        while (x>1 && isBigger(parent(x),x)){
            swap(parent(x),x);
            x = parent(x);
        }
    }
    //下沉
    private void sink(int x){
        while (left(x) <= size){
            //假设左边节点比较小
            int min = left(x);
            //如果右边节点存在,那么比一下
            if(right(x) <= size && isBigger(min,right(x))){
                min = right(x);
            }
            //如果节点比两个孩子都小
            if(isBigger(min,x)) {
                break;
            }
            swap(x,min);
            x = min;
        }
    }

    private boolean isBigger(int x,int y){
        return pq[x].compareTo(pq[y])>0;
    }

    private void swap(int i,int j){
        Key temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    private int parent(int root){
        return root/2;
    }
    private int left(int root){
        return root*2;
    }
    private int right(int root){
        return root*2+1;
    }

}