数据结构-堆和PriorityQueue

1.堆（Heap）

1.1堆的概念

堆是一种非常重要的数据结构，通常被实现为一种特殊的完全二叉树

如果有一个关键码的集合K={k0,k1,k2,...,kn-1}，把它所有的元素按照完全二叉树的顺序存储在一个一维数组中，如果满足ki<=k2i+1且ki<=k2i+2(i=0,1,2,3...)，则称这个集合为小堆；如果满足ki>=k2i+1且ki>=k2i+2(i=0,1,2,3...)，则称这个集合为大堆。

简单来说，根节点的值为最大的堆叫做最大堆或大根堆，根节点的值最小的堆叫做最小堆或小根堆

1.2堆的性质

1.完全二叉树的性质：

除了最后一层外，每一层都被填满，最后一层的节点从左往后填充

2.堆序性质：

最大堆（大根堆）：

对于每个节点i，其左子节点2i+1和右子节点2i+2的值都小于或等于i的值

最小堆（小根堆）：

对于每个节点i，其左子节点2i+1和右子节点2i+2的值都大于或等于i的值

1.3堆的存储方式

从堆的概念可知，堆是一颗完全二叉树，因此可以以层序的规则方式来高效存储

注意：对于非完全二叉树来说，不适合使用顺序的方式进行存储，因为为了还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低

1.4堆的创建

给定一个集合{28,16,20,19,29,35,66,50,26,38}，如何将其创建为堆呢？

观察发现：根节点的左右子树都已经满足堆的性质，因此只需要将根节点向下调整即可

1.4.1堆的向下调整

1.用parent表示要调整的节点，child表示parent的左孩子（注意：堆是一颗完全二叉树，如果parent有孩子一定是先有左孩子

2.如果parent的左孩子存在，即child<size，进行如下操作，直到parent的左孩子不存在：

parent的右孩子是否存在，如果存在，则找到左右孩子中最小的元素，让child表示这个元素。

将parent与较小的孩子child进行比较，如果parent小于child，调整结束。

如果parent大于child，将parent和child进行交换，原来parent中较大的元素向下调整可能会导致子树不满足堆的性质，因此要继续向下调整，即parent=child，child=2*parent+1，继续进行步骤2

代码编写：

    public void shiftDown(int[] array,int parent){
        int child=2*parent+1;
        int size=array.length;
        while(child<size){
            //如果右孩子存在，用child标记左右孩子中较小的值
            if(child+1<size&&array[child+1]<array[child]){
                child++;
            }
            if(array[parent]>array[child]){
                swap(array,parent,child);
                //继续向下调整，为了保证子树也满足堆的性质
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }
        }
    }
    private void swap(int[] array,int a,int b){
        int tmp=array[a];
        array[a]=array[b];
        array[b]=tmp;
    }

注意：再调整以parent为根的二叉树时，必须满足parent的左子树和右子树已经时堆了才可以进行向下调整。

1.4.2堆的创建（小根堆）

那么对于普通的序列，即根节点的左右子树不满足堆的性质，又该如何创建呢？

例如对普通序列{2,7,8,5,4,1}进行小根堆的创建

根据上面的堆的向下调整，我们的思路就是要将根的左右子树都满足小根堆的特点，我们可以从下向上，从最后一个非叶子节点出发，将其与他们的左右孩子进行比较，将最小的值与非叶子节点进行交换（堆的向下调整），再继续向上执行上述操作，直到操作的节点为根节点即可

代码编写：

     public void createSmallestHeap(int [] array){
        int root=(array.length-2)>>1;
        for(;root>=0;root--){
            shiftDown(array,root);
        }
    }

1.5堆的插入和删除

1.5.1堆的插入

堆的插入总共需要2步：

1.先将元素放入底层（空间不够时，需要进行扩容）

2.将新插入的元素不断向上调整，直到满足堆的性质

观察可以发现：如果新插入的节点的父节点大于新插入的节点，就进行元素的交换，不断重复该动作

代码编写：

    //child表示新插入元素的索引
    public void shiftUp(int child){
        //找到新插入节点的父节点
        int parent=(child-1)/2;
        while(child>0){
            if(array[parent]>array[child]){
                swap(array,parent,child);
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
    }

1.5.2堆的删除

堆在删除过程中需要注意删除的元素一定是堆顶元素

1.将堆顶元素和堆中的左后一个元素交换位置

2.将堆中有效个数减少一个

3.对堆顶元素进行向下调整

代码编写：

     public void shiftDown(int[] array,int parent){
        int child=2*parent+1;
        int size=array.length;
        while(child<size){
            //如果右孩子存在，用child标记左右孩子中较小的值
            if(child+1<size&&array[child+1]<array[child]){
                child++;
            }
            if(array[parent]>array[child]){
                swap(array,parent,child);
                //继续向下调整，为了保证子树也满足堆的性质
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }
        }
    }
    public void delete(int[] array){
        swap(array,0,size-1);
        //size表示有效元素的个数
        size--;
        shiftDown(array,0);
    }

1.6堆的应用

1.堆排序（Heap Sort）

利用堆的性质对数组进行排序，时间复杂度为O(nlogn)

2.优先级队列（PriorityQueue）

堆是实现优先级队列的高校数据结构，支持快速的插入和删除操作

3.Dijkstra算法

在最短路径算法中，堆用于高效地选择当前距离最小的节点

4.Kth Largest Element

也叫topK问题，使用堆可以高效地找到数组中的第k大元素

2.PriorityQueue

2.1什么是优先级队列

通过之前的介绍，队列是一种先进先出(FIFO)的数据结构，但是优先情况下，操作的数据可能带有优先级，并不希望按照队列原始的顺序进行出栈，可能优先级高的元素想先出队列

在生活中有一个很常见的例子：当你在用听歌的时候，突然接到电话，音乐会自动停止，而执行通话的操作

优先级队列（PriorityQueue）是一种特殊的队列，其中的每个元素都有一个优先级，队列会根据优先级来决定元素的出队顺序，优先级高的元素先出队，优先级低的元素后出队，如果两个元素的优先级相同，则按照它们入队列的顺序出队

优先级队列通常基于堆这种数据结构实现，因为堆可以高效地进行插入和删除操作，同时保持元素的优先级顺序

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，我们主要进行讲解PriorityQueue

2.2PriorityQueue常见操作

PriorityQueue的常见方法：

方法	解释
PriorityQueue()	创建一个空的优先级队列，默认容量是11
PriorityQueue(int initialCapacity)	创建一个初始容量为initialCapacity的优先级队列，注意：initialCapacity不能小于1，否则会抛出IllegalArgumentException异常
PriorityQueue(Collection<? extends E> c)	用一个集合来创建优先级队列
boolean offer(E e)	插入元素e，插入成功返回true，如果e对象为空，则会抛出NullPointerException异常，空间不够的时候会进行扩容
E peek()	获取优先级最高的元素，如果优先级队列为空，返回null
E poll()	移除优先级最高的元素，如果优先级队列为空，返回null
int size()	获取有效元素的个数
void clear()	清空队列
boolean isEmpty()	检测优先级队列是否为空，如果为空返回true

我们以一个复杂的类型来演示：

public class Student implements Comparable<Student>{
    private String name;
    private int age;

    public Student() {
    }

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public int compareTo(Student o) {
        return this.age-o.age;
    }
}

public class Test {
    public static void main(String[] args) {
        PriorityQueue<Student> queue=new PriorityQueue<>();
        Student s1=new Student("hajimi",21);
        Student s2=new Student("king",18);
        queue.offer(s1);
        queue.offer(s2);
        System.out.println(queue.size());
        for(Student s:queue){
            System.out.println(s);
        }
        queue.clear();
        System.out.println(queue.size());
    }
}

2.3优先级队列的特性

因为优先级队列是基于堆实现的，所以优先级队列的操作的时间复杂度其实就是堆在操作过程中的时间复杂度

1.插入：

将一个新元素插入到队列中，并根据优先级调整队列的顺序，时间复杂度为O(logn)

2.删除：

删除优先级最高的元素，时间复杂度为O(logn)

3.获取优先级最高的元素：

返回优先级最高的元素，但不删除它，时间复杂度为O(1)

4.更新优先级：

更新队列中某个元素的优先级，并调整队列的顺序，时间复杂度为O(logn)

5.Priority中放置的元素必须是能够比较大小的，不能插入无法比较大小的对象，否则会抛出ClassCastException异常

6.不能插入null，否则会抛出NullPointerException

7.PriorityQueue默认情况下是小堆

8.PriorityQueue其内部可以自动扩容

2.4PriorityQueue底层的扩容原理

PriorityQueue的默认无参构造方法创建的数组长度为11

如果容量小于64时，是按照oldCapacity的2倍方式扩容的

如果容量大于64时，是按照oldCapacity的1.5倍方式扩容的

如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容

2.5实现一个优先级队列

package datastructure;

import java.util.Arrays;

public class PriorityQueue {
    private int elem[];
    //队列中有效元素的个数
    private int usedSize;
    private final static int DEFAULT_INIT_SIZE=11;

    public PriorityQueue(){
        elem=new int[DEFAULT_INIT_SIZE];
    }
    public PriorityQueue(int[] elem){
        this.elem=elem;
        this.usedSize=elem.length;
        int root=((elem.length-2)>>1);
        for(;root>=0;root--){
            shiftDown(root,elem.length);
        }
    }
    private void shiftDown(int parent,int len){
        int child=parent*2+1;
        while (child<len){
            if(child+1<len&&elem[child+1]<elem[child]){
                child++;
            }
            if(elem[parent]>elem[child]){
                swap(elem,parent,child);
            }else {
                break;
            }
        }
    }
    public boolean offer(int value){
        if(usedSize==elem.length){
            Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize]=value;
        usedSize++;
        shiftUp(usedSize-1);
        return true;
    }
    private void swap(int[] elem,int a,int b){
        int tmp=elem[a];
        elem[a]=elem[b];
        elem[b]=tmp;
    }
    private void shiftUp(int child){
        int parent=(child-1)/2;
        while (child>0){
            if(elem[child]<elem[parent]){
                swap(elem,parent,child);
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
    }
    public int size(){
        return usedSize;
    }
    public int peek(){
        if(usedSize==0){
            System.out.println("优先级队列中没有元素，无法获取元素");
            return -1;
        }
        return elem[0];
    }
    public boolean isEmpty(){
        return usedSize==0;
    }
    public int poll(){
        if(usedSize==0){
            System.out.println("优先级队列中没有元素，无法删除元素");
            return -1;
        }
        int value=elem[0];
        swap(elem,0,usedSize-1);
        usedSize--;
        shiftDown(0,usedSize-1);
        return value;
    }
}

对编写的代码进行运行测试：

public class Test {
    public static void main(String[] args) {
        PriorityQueue queue=new PriorityQueue();
        queue.offer(2);
        queue.offer(4);
        queue.offer(3);
        queue.offer(8);
        queue.offer(7);
        queue.offer(5);
        queue.offer(1);
        System.out.println(queue.peek());
        int a= queue.poll();
        System.out.println(a);
        System.out.println(queue.peek());
        System.out.println(queue.size());

    }
}