2.4优先队列

2.4优先队列

应用程序有时候需要处理有序元素,但不必全部排序,如:为应用程序分配优先级,这时一个合适的数据结构应该支持删除最大元素和插入元素,这种数据结构即为优先队列

2.4.2初级实现

2.4.2.1数组实现(无序)

基于数组下压栈实现,insert()和下压栈的push()一样,实现删除最大元素可以通过内循环将最大元素移动至栈顶后pop()

2.4.2.2数组实现(有序)

在insert()中添加代码使得较大元素右移,删除最大元素只需pop()

2.4.2.3链表实现

以基于链表的下压栈为基础,修改pop()弹出最大元素或修改push()逆序插入后pop()

使用无序序列是解决问题的惰性方法,仅在必要时采取行动,使用有序序列是积极方法,使后续操作更高效

优先队列不同实现运行时间增长数量级

2.4.3堆的定义

定义:二叉堆是一组能够用堆有序的完全二叉树排序的元素,并在数组中按照层级储存(不使用数组第一个位置)

堆有序:当一棵二叉树的每个节点都大于等于它的两个子结点时,称为堆有序

一棵大小为N的完全二叉树的高度为<=lgN,且当N为2次幂,高度加1

2.4.4堆的算法

使用长度N+1的数组pg[]来表示一个大小为N的堆,不使用pq[0],堆元素放在pq[1]和pq[N]中.

1. 堆的操作会首先进行一些简单改动,打破堆的状态,在遍历堆按要求恢复顺序,此过程为堆的有序化

有序化过程中会有两种情况:

1. 当某个结点优先级上升(或是在堆底加入一个新的元素),需要右下至上恢复堆的顺序(上浮swim)

private void swim(int k){
    while(k > 1 && less(k/2, k)){
        exch(k/2, k);
        k = k/2;
    }
}

1. 当某个结点优先级下降(如根结点被替换为较小结点),需要由上至下恢复堆的顺序(下沉sink)

private void sink(int k){
    while(2*k <= N){
        int j = 2*k;
        if(j < N && less(j, j+1)) j++;//找出两个子结点中较大者
        if(!less(k, j)) break;
        exch(k, j);
        k = j;
    }
}

2. 插入元素:将新元素加到数组末尾,增加堆的大小并让元素上浮到合适位置

3. 删除最大元素:从数组顶端删除删去最大元素并让数组最后一个元素放到顶端,减小堆的大小并让元素下沉到合适位置

基于堆的优先队列:见算法2.6

2.4.4.7索引优先队列:见Ex2_4_33

2.4.5堆排序(实现见算法2.7)

答疑:

1. 优先队列的应用?为什么不把元素排好序后在插入数组?
   答:因为有时数据量太大,无法排序,甚至无法装进内存,如果从10亿个元素中选出最大10个,使用优先队列,只需要一个可存储十个元素的优先队列,实时的向后读取数据即可.
2. 为什么不直接extends Comparable接口,而要使用泛型?

答:这样delMax()的用例需要将返回值强行转换为某具体类型,应避免在用例中强转;

1. 为什么堆排序采用从下至上构造堆,而不是直接向堆添加元素?

答:这样可以提高效率,且代码更少(从下往上构造不用swim()函数),理解算法的难度不一定与它的简洁性或效率有关