优先级队列(堆)

堆的概念:

1. 逻辑上是一颗完全二叉树
2. 堆物理上是保存在数组中
3. 满足任意节点的值都大于其中子树中的值叫做大堆/大根堆/最大堆
4. 满足任意节点的值都小于其中子树中的值叫做小堆/小跟堆/最小堆
5. 堆的基本作用是快速找出集合中的最值

堆的操作:1.向下调整

代码实现(以大堆为例):

//时间复杂度O(log(n))
public class Heap {
    public int[] elem;
    public int usedSize;

    public Heap(){
        this.elem = new int[20];
        this.usedSize = 0;
    }
    //一次调整,每次调整这棵树的根节点下标向下调整
    public void adjustDown(int root, int len){
        int parent = root;
        int child = 2*parent+1;
        while(child<len){
            //判断是否有右孩子,如果有,谁大?
            if(child+1 < len && elem[child+1] > elem[child]){
                child = child+1;
            }
            if(elem[child]>elem[parent]){
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                parent = child;
                child = 2*parent+1;
            }
            else break;
        }
    }
 }

2.建堆

代码实现(以大堆为例):

//建堆
//时间复杂度O(nlog(n))
public void createHeap(int[] array){
    for(int i = 0;i < array.length;i++){
        this.elem[i] = array[i];
        this.usedSize++;
    }
    for(int i = (this.usedSize-1-1)/2;i >= 0;i--){
        adjustDown(i,this.usedSize);
    }
}

堆的应用:Priority Queue

Priority Queue 是一个基于优先级堆的*队列,它的元素是按照自然顺序排序的,在创建的时候,我们可以给他提供一个负责给元素排序的比较器,Priority Queue 不允许null值,因为他们没有自然排序,或者说他们没有任何的相关联的比器.Priority Queue 不是线程安全的,入队和出队的时间复杂度是O(log(n)).

原理

以Priority Queue 通过用数组表示的小顶堆实现为例:

1.添加元素add()和offer()
原理: 添加元素位于末尾,同时队列长度加1,然后这个元素与它的父节点进行比较,如果比父节点小那么就与父节点进行交换,然后再与交换后的位置的父节点进行比较,重复这个过程,直到该元素的值大于父节点结束这个过程
区别: add(E e) 和offer(E e)的语义相同,都是向优先队列中插入元素,只是Queue接口规定二者对插入失败时的处理不同,前者在插入失败时抛出异常,后者则会返回false.对于Priority Queue这两个方法没什么差别

2.寻找队列的头部元素element()和peek()头部元素 时间复杂度为1
element() 和 peek()的语义完全相同,都是获取但不删除队首元素,区别是当方法失败时前者抛出异常,后者返回null,根据小顶堆的性质,堆顶那个元素就是全局最小的那个,由于堆用数组表示,根据下标关系,0下标处的那个元素即是堆顶元素,所以返回数组0下标处的那个元素即可.

3.删除元素 remove()和poll()
原理: 该方法的作用是从k指定的位置开始,将x逐层向下与当前点的左右孩子中较小的那个交换,直到x小于或等于左右孩子中的任何一个为止
区别: remove() 和poll() 方法的语义也完全相同,都是获取并删除队首元素,区别是当方法失败时,前者抛出异常,后者返回null,由于删除操作会改变队列的结构,为维护小顶堆的性质,需要进行必要的调整.

4.最大堆获取数组中的最小的几个数 最小堆获取数组中的最大的几个数

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class GetLeastNumber_Solution {
    public static ArrayList<Integer> GetLeastNumber_Solution(int[] input,int k){
        ArrayList<Integer> result = new ArrayList<>();
        int length = input.length;
        if(k > length || k == 0){
            return result;
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        for(int i = 0;i<length;i++){
            if(maxHeap.size() != k){
                maxHeap.offer(input[i]);
            }else if(maxHeap.peek() > input[i]){
                Integer tmp = maxHeap.poll();
                tmp = null;
                maxHeap.offer(input[i]);
            }
        }
        for(Integer integer : maxHeap){
            System.out.println(integer);
            result.add(integer);
        }
        return result;
    }
}

我们上面构建了大顶堆,最大堆的栈顶是堆的最大元素,最大的元素比数组中任意一个元素小,说明了最大堆的这些元素是数组中最小的几个元素.

上述代码为何需要重新写比较器compare()?

//offer(E e)
public boolean add(E var1) {
    return this.offer(var1);
}

public boolean offer(E var1) {
    if (var1 == null) {
        throw new NullPointerException();
    } else {
        ++this.modCount;
        int var2 = this.size;
        if (var2 >= this.queue.length) {
            this.grow(var2 + 1);
        }

        this.size = var2 + 1;
        if (var2 == 0) {
            this.queue[0] = var1;
        } else {
            this.siftUp(var2, var1);
        }

        return true;
    }
}
//siftUp()
private void siftUp(int var1, E var2) {
    if (this.comparator != null) {
        this.siftUpUsingComparator(var1, var2);
    } else {
        this.siftUpComparable(var1, var2);
    }

}

以上是Priority Queue的部分源码,添加元素需要比较新的元素和父节点的元素,如果比较器比较结果大于等于0,那么结束添加过程,添加完成,说明在构建最大堆的时候,要想使得元素是对父节点的元素小才结束循环,那么必须重新写比较器方法,调换两者的比较顺序即可.

堆排序

//堆排序
public void heapSort(){
    int end = usedSize- 1;
    while (end > 0){
        int tmp = this.elem[0];
        this.elem[0] = this.elem[end];
        this.elem[end] = tmp;
        //向下调整
        adjustDown(0,end);
        end--;
    }
}