数据结构：优先队列和堆

优先队列的概念

普通队列：先进先出；后进后出
优先队列：出队顺序和入队顺序没有关系；和优先级相关
队列中的元素是不断变化的，需要根据队列中元素的不断变化动态的调节队列的优先级

优先队列底层为什么选择堆实现？

堆的基础表示

1、二叉堆是一棵完全二叉树，不会退化成链表。
3、堆中某个节点的值总是不大于其父节点的值（最大堆）
4、堆中某个节点的值总是不小于其父节点的值（最小堆）

用数组存储二叉堆
索引从1开始：

索引从0开始：

二叉堆的代码结构

使用到之前自己定义的动态数组类，具体内容请参照本人所写的另外一篇博客:数据结构 ： Java实现动态数组

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

    private Array<E> data;

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

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

    // 返回堆中的元素个数
    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;
    }
}

⭐向堆中添加元素，Sift up方法的实现

向堆中添加元素52，即向数组中索引为10的位置添加元素，但是添加完后，不满足堆的性质：堆中某个节点的值总是不大于其父节点的值
所以元素需要移动，即Sift up,也称为上浮


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;
    }

add方法与sift 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);
        }
    }

⭐向堆中取出元素，Sift Down方法的实现

首先，将最后一个元素放在堆顶。

开始下沉：16和它的两个孩子中最大的孩子进行比较，如果最大的孩子比它大，则进行交换

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

    // 取出堆中最大元素
    public E extractMax(){

        E ret = findMax();

        data.swap(0, data.getSize() - 1);
        data.removeLast();
        siftDown(0);

        return ret;
    }

    private void siftDown(int k){

        //当k所在的节点没有左孩子，跳出循环
        while(leftChild(k) < data.getSize()){
            int j = leftChild(k); // 在此轮循环中,data[k]和data[j]交换位置

            //如果有右孩子，并且右孩子的值大于左孩子，j就指向k的右孩子
            if( j + 1 < data.getSize() &&
                    data.get(j + 1).compareTo(data.get(j)) > 0 )
                j ++;
            // data[j] 是 leftChild 和 rightChild 中的最大值
            //k和最大的孩子进行比较
            if(data.get(k).compareTo(data.get(j)) >= 0 )
                break;
            //交换
            data.swap(k, j);
            k = j;
        }
    }

Heapify和Replace

Replace:
replace:取出最大元素后，放入一个新元素
实现：可以直接将堆顶元素替换后Sift Down,一次O(log n)的操作

// 取出堆中的最大元素，并且替换成元素e
    public E replace(E e){

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

Heapify：
将任意数组整理成堆的形状
实现一：将数组中的所有元素依次插入到堆中 (O(nlogn))
实现二：Heapify法：将这个数组看做是一个完全二叉树，然后从倒数第一个非叶子节点开始依次进行下沉操作： (O(n))
22下沉→13下沉→17下沉…

//将heapify设计为构造方法
public MaxHeap(E[] arr){
        data = new Array<>(arr);
        for(int i = parent(arr.length - 1) ; i >= 0 ; i --)
            siftDown(i);
    }

基于堆的优先队列

队列接口

public interface Queue<E> {

    int getSize();
    boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    E getFront();
}

优先队列

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();
    }
}