优先队列（堆）

2018-02-01

算法与数据结构

模型
简单实现
二叉堆实现

本文是学习：数据结构与算法分析所做的笔记。

场景：

打印机打印文档，有某个文档比较重要，需要优先打印。
执行某些任务的时候，耗时短的任务应该先执行或者是某些耗时不短，但是比较重要的任务也应该先执行。

普通的队列满足不了上述的需求，需要特殊的队列-优先级队列来满足这种需求。

模型

基本操作：插入操作（insert）和删除最小（deleteMin）或者最大的操作（deleteMax）。

此处输入图片的描述

简单实现

链表

无序链表：O(1)插入，O(n)删除（遍历）
有序链表：O(n)插入，O(1)删除

二叉查找树

二叉堆实现

二叉堆有两个性质：

堆序性

结构性

对堆的任何一次操作都有可能会破坏这两种性质之一，因此堆的操作必须等堆的所有性质都被满足才能停止。

堆的结构性质

堆是一个完全填满的二叉树，唯一的例外在底层，底层上的元素从左到右填入，这样的树是完全二叉树。

此处输入图片的描述

高度为h的完全二叉树的有2的h次方-2的h+1次方个节点，因此完全二叉树的高度为O(logN)。

由于完全二叉树的规律性，完全二叉树完全可以只使用数组来实现。

此处输入图片的描述

数组中位置为i的元素，其左儿子的位置为2i，右儿子的位置为2i+1，他的父亲的位置为i/2(向零取整)。

堆序性质

让堆快速执行的性质就是堆序性质。

最小堆：最小的节点在根上，任意的节点都小于他的后裔。
最大堆：最大的节点在根上，任意的节点都大于他的后裔。

堆序性质（最小堆）：在一个堆上，对于每一个节点X，X的父亲节点的关键字小于或者等于X中的关键字，根节点除外（他没有父亲）。

堆序性质（最大堆）：在一个堆上，对于每一个节点X，X的父亲节点的关键字大于或者等于X中的关键字，根节点除外（他没有父亲）。

根据堆序性质，最小的（或者最大的）元素总可以在根节点找到，所以我们可以以常数的时间执行findMin或者findMax操作。

基本的堆操作

插入操作

为了讲一个元素插入到堆中，我们在下一个可用的位置创建一个空穴，否则堆将不是完全二叉树。如果X可以完全放入空穴并且不破坏堆序，那么插入完成。否则，我们把空穴的父节点上的元素放入空穴，这样空穴就朝着根的方向移动了一步。继续该过程直到元素被放入空穴为止。

此处输入图片的描述

这种策略叫做上滤，新的元素在堆中上滤直到找到正确的位置。

代码实现:

 public void insert(E x) {
        if (currentSize == array.length - 1) {
            enlargeArray(array.length * 2 + 1);
        }
        int hole = ++currentSize;
        for(;hole>1&&x.compareTo(array[hole/2])<0;hole/=2) {
            array[hole] = array[hole / 2];//比使用交换语句，省去了两句语句。
        }
        array[hole] = x;
}

or

public void insert(E x) {
        if (currentSize == array.length - 1) {
            enlargeArray(array.length * 2 + 1);
        }
        int hole = ++currentSize;
        for(;hole>1&&x.compareTo(array[hole/2])<0;hole/=2) {
            array[hole] = array[hole / 2];//比使用交换语句，省去了两句语句。
        }
        array[hole] = x;

}

如果要插入的元素是最小值，那么他将一直被推到顶端。这样某一时刻hole将是1，并且需要程序跳出循环。我们可以用显示的测试做到这一点，或者是把对被插入项的引用放到位置0处使循环终止。

如果要插入的元素是最小元素，那么他将一直上滤到根处，那么这种插入的时间将长达O(logN)。平均来看上滤终止的要早，平均一次插入操作，上移元素1.607层。

删除最小（或者最大）

当删除一个最小元的时候，要在根节点建立一个空穴。由于现在堆少了一个元素，因此堆中的最后一个元素需要移动到某个位置。如果X可以被放到空穴中，那么删除操作完成。不过一般不太可能，因此我们将空穴的两个儿子中的较小者移入空穴，这样就把空穴上下移动了一层，重复该步骤，直到X可以被放入空穴。因此，我们的做法是将X置入沿着从根开始包含最小儿子的一条路径上的一个正确的位置。

此处输入图片的描述

这种一般的策略叫做下滤。
这种操作的最坏情形的运行时间是O(logN)。平均而言，被放到根处的元素几乎下滤到堆的底层，因此平均运行时间为O(logN)。

代码实现：

 public E deleteMin() {
     if (isEmpty()) {
         throw new IllegalStateException("isEmpty()");
     }
     E minItem = findMin();
     array[1] = array[currentSize--];
     percolateDown(1);
     return minItem;
 }

 private void percolateDown(int hole) {
     int child;
     E tmp = array[hole];
     for(;hole*2<=currentSize;hole=child) {
         child = hole * 2;
         if (child != currentSize && array[child + 1].compareTo(array[child]) < 0) {
             child++;//上面的条件，解决了当堆中元素的个数为偶数的时候，有一个节点只有一个子节点的情况，这种方式，假设了右子节点总是存在的。
         }
         if (array[child].compareTo(tmp) < 0) {
             array[hole] = array[child];
         }else
             break;
     }
     array[hole] = tmp;
}

最后需要注意的，虽然删除最小值（或者最大值的）操作可以在常数时间内完成，但是按照求最小元（或者最大元）设计的堆，对于查找最大元（或者最小元）却无任何帮助。

构建堆

有时候二插堆是由一些项饿初始集合构造而成。这种构造方法以N项作为输入，并且把他们放入到一个堆中。

一般的算法是使将N项以任意的顺序放入到树中，保持结构性。然后用下面程序创建一个堆序的树。

public BinaryHeap(E[] items) {
        currentSize = items.length;
        array = (E[]) new Comparable[(currentSize + 2) * 11 / 10];

        int i = 1;
        for (E item : items) {
            array[i++] = item;
        }
        buildHeap();
}
private void buildHeap() {
        for(int i=currentSize/2;i>0;i--) {
            percolateDown(i);
        }
}

此处输入图片的描述

每条虚线对应两次比较：一次是找出较小的儿子节点，另一次是较小的儿子节点与该节点比较。

完整的源码实现：

public class BinaryHeap<E extends Comparable<? super E>> {

   
    private static int DEFAULT_CAPACITY = 10;
    private int currentSize;
    private E[] array;

    public BinaryHeap() {
        this(DEFAULT_CAPACITY);
    }
    public BinaryHeap(int capacity) {
        currentSize = 0;
        array = (E[]) new Comparable[capacity + 1];
    }
    public BinaryHeap(E[] items) {
        currentSize = items.length;
        array = (E[]) new Comparable[(currentSize + 2) * 11 / 10];

        int i = 1;
        for (E item : items) {
            array[i++] = item;
        }
        buildHeap();
    }
    public void insert(E x) {
        if (currentSize == array.length - 1) {
            enlargeArray(array.length * 2 + 1);
        }
        int hole = ++currentSize;
        for(;hole>1&&x.compareTo(array[hole/2])<0;hole/=2) {
            array[hole] = array[hole / 2];
        }
        array[hole] = x;
    }
    private void enlargeArray(int newSize) {
        E[] old = array;
        array = (E[]) new Comparable[newSize];
        for (int i = 0; i < old.length; i++) {
            array[i] = old[i];
        }
    }
    public E findMin() {
        if (isEmpty()) {
            throw new IllegalStateException("isEmpty()");
        }
        return array[1];
    }
    public E deleteMin() {
        if (isEmpty()) {
            throw new IllegalStateException("isEmpty()");
        }
        E minItem = findMin();
        array[1] = array[currentSize--];
        percolateDown(1);
        return minItem;
    }
    private void buildHeap() {
        for(int i=currentSize/2;i>0;i--) {
            percolateDown(i);
        }
    }
    private boolean isEmpty() {
        return currentSize == 0;
    }
    public void makeEmpty() {
        currentSize = 0;
    }
    private void percolateDown(int hole) {
        int child;
        E tmp = array[hole];
        for(;hole*2<=currentSize;hole=child) {
            child = hole * 2;
            if (child != currentSize && array[child + 1].compareTo(array[child]) < 0) {
                child++;
            }
            if (array[child].compareTo(tmp) < 0) {
                array[hole] = array[child];
            }else
                break;
        }
        array[hole] = tmp;
    }
}

上一篇：二叉搜索树

下一篇：散列