优先队列学习总结

本文内容是《算法》书中内容的摘抄以及总结

重要概念

什么是优先队列？
——优先队列是一个支持删除最大（最小）元素和插入元素的一种数据结构。这种数据结构可以是用有序或者无序数组实现，或用链表来表示，而最常用的是用堆来实现优先队列。

什么是堆有序？
——当一颗二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。

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

---

使用场景

1. 需要按照时间顺序处理所有事件的模拟系统，键值是事件发生时间。
2. 任务调度，其中键值对应的优先级决定了哪些任务先执行；
3. 不需要全部有序，或是不一定要一次性就将它排序的情况，比如在N个数中找出最大的M个数。

以上场景有一个共同特点，就是可能需要不断删除和插入，删除的元素是整个队列中的最大值或最小值，而新插入的元素将从新排序，以定位自己在优先队列中的位置。比如，对于场景1，根据时间这个键值，先处理最先发生的事件，处理完成后将其从队列中删除，插入新的事件。对于场景2，同场景1类似，不过键值由时间变为了优先级。而场景3，请考虑书中209页第一个答疑中的例子，10亿个数中选出最大的十个，我们只需构造一个大小为10的队列，不断删除队列中的最小元素，并不断插入元素即可。

---

命题证明

命题P：一课大小为N的完全二叉树的高度为⎣lgN⎦.

证明：使用归纳法。
观察树的大小和高度的变化，可有下列变化：

树的大小          高度
1                 0
2                 1
3                 1
4                 2
5                 2
…
8                 3
…
15                3
16                4
…
查找规律可发现，当树的大小为2，4，16，…时，树的高度加1，
即树的大小N为2的幂时，树高度增1，
有2^1——>1, 2^2——>2,2^3—->3,因此有2^h——>h(h为树的高度），
即当N = 2^h时，h = lgN, 那么当2^h <= N < 2^(h+1)时，
树的高度都为h, 由此可得，h = ⎣lgN⎦.

---

优先队列的几种实现

几种实现对比.png

• 有序数组实现优先队列

//这里用动态数组保存一系列int值，假设是有序的;
//且为了简化，这里简单粗暴的使用了int作为内部元素,实际上应该是一切可比较对象；
int *orderArray = new int[CAPACITY];
int n = 0;//元素个数

//时间复杂度为线性O(n)
void insert(int newKey, int *orderArray, int &n)
{
    int i = n- 1;
    while(i >= 0 && newKey < orderArray[i])
    {
        orderArray[i+1] = orderArray[i];
        i--;
    }
    orderArray[i+1] = newKey;
    n++;
}

//时间复杂度为常量O(1)
void delMAX(int *orderArray, int &n){ return orderArray[—-n]; }

• 无序数组实现优先队列

//这里用动态数组保存一系列int值，假设是无序的;
//且为了简化，这里简单粗暴的使用了int作为内部元素,实际上应该是一切可比较对象；
int *unorderArray = new int[CAPACITY];
int n = 0;//元素个数

//时间复杂度为常量O(1)
void insert(int newKey, int *unorderArray, int &n) { unorderArray[n++] = newKey; }


//线性时间复杂度O(n)
void delMAX(int *unorderArray, int &n)
{

    int max = 0;

    for(int i = 1; i < n; i++)
    {
        if(unorderArray[i] > unorderArray[max])
         max = i;
    }
    exch(unorderArray, max, n-1);  //交换unorderArray[max] 与 unorderArray[n-1]
    return unorderArray[—n];
}

• 二叉堆实现优先队列

  • 插入元素
    ——将新元素加到数组末尾，增加堆的大小，并让这个新元素上浮到合适的位置。

  • 删除最大元素
    ——从数组顶端删去最大的元素并将最后一个元素放到顶端，减去堆的大小并让这个元素下沉到合适的位置。

  • 无论是插入还是删除，都经历堆的有序状态的破坏以及重建。在上浮或下沉过程中，遇到比它大的父节点就可以停止上浮了，因为往上的结点必然比它大，子节点都比它小时就可以停止下沉了，子节点下面的结点一定比它小。

  • 位于K的结点，父节点位置为k/2，子结点位置为2k，2k+1

对于上浮 和 下沉，一图胜千言

上浮 .png 下沉.png

class MaxPQ
{
public:
    MaxPQ(int maxN){ pa =  new int[maxN]; }
    bool isEmpty() { return len == 0; }
    int size() { return len; }
    void insert(int v){

        pq[++len] = v;
        swim(len);
    }

    int delMax()
    {
        int maxKey = pq[1];
        exch( 1, len);
        pq[len--] = NULL;
        sink(1);
        return maxKey;
    }

private:
    bool less(int i, int j){ return pa[i] < pq[j]; }
    void exch(int i, int t){int t = pa[i]; pa[i] = pa[j]; pq[j] = t; }

    // 上浮，即与父节点交换，k的父节点的位置是k/2
    //不断向上移动直到遇到了更大的父节点
    void swim(int k)
    {  
        //注意：less()函数也作为循环条件
        while(k > 1 && less(k/2, k)){
            exch(k/2, k)
            k = k/2;
        }

    }

    //下沉，即与两个子节点中较大者交换；子节点位置为2k和2k+1
    //向下移动直到它的子节点都比它更小或者到达了堆的底部
    void sink(int k)
    {
        int j = 2k;
        while(k < len)
        {
            if(less(2k, 2k+1)) j++;//找出较大的子节点
            if(!less(k, j))  break;//确定该子节点是否上浮

            exch(k, j);
            k = j;
        }
    }

    int *pq; //堆有序的完全二叉树
    int len = 0;//存储于pq[1...len]中，pq[0]没有使用

};