2017-10-13

二叉堆与优先队列

一、优先队列

1.简单介绍

优先队列是一种抽象的数据结构，它与我们生活中的许多场景息息相关。比如我们的电脑或者手机，很多时候我们后台会运行多个程序，当程序过多导致内存急剧减少时，如果没有相关权限的设置，处理器会优先关闭挂在后台比较久的，然后继续往后台加入程序。和基本的数据结构队列和栈类似，不过优先队列对元素的操作是有优先级的，和上面描述的一样，它的核心是删除最大元素和插入元素。

2.基本实现

优先队列的实现有很多方式，常见的初级实现有基于有序数组和无序数组的，以及基于链表的，都能达到优先队列的核心操作。但这些实现平均效率不高。这里就重点描述下基于堆的优先队列的实现。

二、二叉堆

1.简单介绍

二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按层级储存（不使用数组的第一个元素）。且根结点是堆有序的二叉树中最大的节点。在一个二叉堆中，如果一个节点的位置为k，则它的父结点的位置为k/2，左右子节点的位置分别为2k、2k+1。

2.基本实现

①比较和交换
这个比较简单，这里就不多说了，直接上代码

// 比较两个元素大小
private boolean less(int i,int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }
// 交换两个元素
private void exch(int i,int j) {
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }

②插入和删除最大元素
插入元素就直接将元素增加到堆的末尾，然后进行上浮操作，使二叉堆有序。

删除最大元素就直接从二叉堆顶端删除，然后进行下沉操作。

所以接下来2个将堆有序化的操作是比较重要的，因为不管是删除最大元素还是插入元素后，都要继续保持二叉堆的有序性。

③由下至上的堆的有序化
这个也称上浮。如果二叉堆的有序化因为某个结点变得比它的父结点更加大而打破，就需要进行不断的上浮操作,也就是把当前结点与父结点交换位置直到二叉堆有序为止。看看下面的代码

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

这里循环的条件判断了只有当父结点比子结点更加小时交换才会继续进行。

④由上至下的堆有序化
这个也称下沉。与上浮类似，如果二叉堆的有序化因为某个结点变得比它的某个子结点更加小而打破，就需要进行不断的下沉操作，把当前结点与其子结点中较大的部分进行交换（注意：二叉堆的左右结点是不需要按大小来排序的，但都比父结点小）。下面来看看代码

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

这里注意一下第一个判断，如果当前结点的左结点比右结点小，就进行++操作,这样j就变成了右结点。继续往下，如果当前结点比j结点大，就结束循环。否则就以j结点为当前结点继续进行下一轮循环。

最后附上基于堆的优先队列的全部代码

/*
 * 基于堆的优先队列
 */
public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;   //基于堆的完全二叉树
    private int N = 0;  // 在数组中储存的范围是[1...N] 不包括pq[0]
    public MaxPQ(int MaxN) {
        pq = (Key[]) new Comparable[MaxN+1];
    }
    // 判断数组是否为空
    public boolean isEmpty() {
        return N == 0;
    }
    // 数组大小
    public int size() {
        return N;
    }
    // 插入元素
    public void insert(Key v) {
        pq[++N] = v;
        swim(N);
    }
    // 删除最大元素
    public Key delMax() {
        Key max = pq[1];
        exch(1,N--);
        pq[N+1] = null; //防止对象游离
        sink(1);
        return max;
    }
    // 上浮操作
    private void swim(int k) {
        while (k > 1&&less(k/2,k)) {
            exch(k/2,k);
            k = k/2;
        }
    }
    // 下沉操作
    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;
        }
    }
    // 比较两个元素大小
    private boolean less(int i,int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }
    // 交换两个元素
    private void exch(int i,int j) {
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
}