数据结构----二叉堆和优先权队列

SuperHeroes

发布于 2018-05-30 18:05:58

4880

发布于 2018-05-30 18:05:58

文章被收录于专栏：云霄雨霁云霄雨霁云霄雨霁

堆有序：当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。根结点是堆有序的二叉树中的最大节点。

二叉堆：二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按层级存储（不使用数组的第一个位置）。

二叉堆可以使用数组或者二叉树实现，在这里使用数组实现。在数组中，根结点放置在下标为1的空间内；下标k的结点的父结点的下标为⌊k⌋，它的两个子结点的下标为2k和2k+1.

堆的实现：

构造堆的过程中，肯定会用到比较方法和交换方法：

//比较方法
private boolean less(int i,int j)
{ return pq.[i].compareTo(pq[j])<0; }
//交换方法
priivate void exch(int i,intj)
{ Key t = pq[i]; pq[i] = pq[j]; pq[j] = t; }

在对堆进行有序化的过程中会遇到两种情况：

当某个节点优先级上升(或在堆底加入了一个新元素)时，我们需要由下至上恢复堆的顺序；
当某个节点优先级下降(例如将根结点替换为一个较小节点)时，我们需要由上至下恢复堆的顺序；

我们把由下至上恢复堆的顺序称为上浮，把由上至下恢复堆的顺序叫下沉。

堆的上浮操作：

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++;    //保证j是k两个子节点中的较小者
        if(!less(k,j)) break;    //如果k大于j，结束
        exch(k,j);
        k = j;
    }
}

通过使用上面的方法，我们就可以构造出一个堆，堆的插入操作和删除最大元素操作都可以在对数级别的时间内完成。

插入元素：我们将新元素插入数组末尾，增加堆的大小并让新元素上浮到正确位置；
删除最大元素：我们从数组顶端删去最大元素并将数组末尾元素置入顶端，下沉它到正确位置。

优先权队列：

优先权队列的功能就是插入元素和删除最大元素，所以我们完全可以基于堆来实现优先权队列。

明白堆和上面的代码，优先权队列很容易实现，直接来看代码：

public class MaxPQ<Key extends Comparable<Key>>{
    private Key[] pq;    //基于堆
    private int N;    //堆的大小

    public MaxPQ(int maxN)
    { pq = (Key[]) new Comparable[maxN+1]; }

    public void insert(Key v){
        pq[++] = v;
        swim(N);    //恢复堆的有序性
    }
    public Key delMax(){
        public Key max = pq[1];
        exch(1,N--);    //和最后一个节点交换
        pq[N-1] = null;    //防止对象游离
        sink(1);    //恢复堆的有序性
        return max;
}
//less()、exch()、swim()、sink()方法见上文
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018.03.04，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构