Rookie's blog

Chapter7 优先级队列

Chapter7 优先级队列

基于线性表的优先级队列

和普通队列差不多（当然多一个变量存储每个节点的优先级），没啥特别的

基于树的优先级队列——二叉堆

二叉堆

堆是一棵完全二叉树，且满足下列关系之一：

  1. ki≤k2i and ki≤k2i+1k_i \leq k_{2i} \, and \, k_i \leq k_{2i+1}

    • 人话：每个节点都小于自己的左节点和右节点
    • 满足这一条件的堆被称为最小堆

  2. ki≥k2i and ki≥k2i+1k_i \geq k_{2i} \, and \, k_i \geq k_{2i+1}

    • 人话：每个节点都大于自己的左节点和右节点
    • 满足这一条件的堆被称为最大堆

二叉堆的特性

  • 结构性：完全二叉树
  • 有序性：满足父结点小于子结点（最小化堆）或父结点大于子结点（最大化堆）

二叉堆的存储

采用顺序存储

  • 如果数值越小，优先级越高，则可以用一个最小化堆存储优先级队列
  • 在最小化堆中，最小元素是根元素，而根结点永远存放在数组的下标为1的元素中。
  • 获取队头元素的操作就是返回下标为1的数组元素值
  • 出队操作就是删除下标为1的数组元素中的值，重新调整堆
  • 入队操作就是在数组的末尾添加一个元素，但添加后要调整元素的位置，以保持堆的有序性

优先级队列类

定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template <class Type>
class priorityQueue:public queue<Type>
{
private:
    int currentSize;  
    Type *array;   
    int maxSize;
    void doubleSpace();
    void buildHeap( );//建堆，被priorityQueue调用
    void percolateDown( int hole );  //向下过滤
public:
    priorityQueue( int capacity = 100 ) 
    { 
        array = new Type[capacity];
        maxSize = capacity;   
        currentSize = 0;
    }
    priorityQueue( const Type data[], int size );
    ~priorityQueue() { delete [] array; }
    bool isEmpty( ) const { return currentSize == 0; }
    void enQueue( const Type & x );
    Type deQueue();
    Type getHead() { return array[1]; }
};

enQueue(x)

  • enQueue操作是在堆中插入一个新元素
  • 堆的插入是在具有最大序号的元素之后插入新的元素或结点，否则将违反堆的结构性。
  • 如果新元素放入后，没有违反堆的有序性，那么操作结束。否则，让该结点向父结点移动，直到满足有序性或到达根结点。
  • 新结点的向上移动称为向上过滤(percolate up)

image-20240611122644214

1
2
3
4
5
6
7
8
9
10
11
template <class Type>
void priorityQueue<Type>::enQueue( const Type & x )
{  
    if( currentSize == maxSize - 1 )  doubleSpace();
  
    // 向上过滤
    int hole = ++currentSize;
    for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 )
        array[ hole ] = array[ hole / 2 ];
    array[ hole ] = x;
}
  • 最差时间复杂度为O(logn)O(log n)（对数）
  • 平均好于最差

deQueue(x)

  • 当最小元素被删除时，在根上出现了一个空结点。堆的大小比以前小1，堆的结构性告诉我们，最后一个结点应该删掉。
  • 如果最后一项可以放在此空结点（根节点）中，就把它放进去。然而，这通常不符合堆的有序性。
  • 需要与插入操作类似的操作：把某些项放入空结点，然后移动空结点。仅有的区别在于：对DeQueue操作，空结点是往下移动，称为向下过滤percolateDown 。
1
2
3
4
5
6
7
8
9
 template <class Type>
Type priorityQueue<Type>::deQueue()
{
    Type minItem;
    minItem = array[1];//输出最小值
    array[1] = array[currentSize--];
    percolateDown(1);
    return minItem;
}

向下过滤：percolateDown(x)

  • 找到空结点的一个较小的子结点，如果该儿子的值小于我们要放入的项，则把该儿子放入空结点，把空结点往下推一层
  • 重复这个动作，直到该项能被放入正确的位置。
image-20240611122939952 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class Type>
void priorityQueue<Type>::percolateDown( int hole )
{  
    int child;
    Type tmp = array[ hole ];
  
    for( ; hole * 2 <= currentSize; hole = child )
    {  
        child = hole * 2;
        if( child != currentSize && array[child + 1] < array[child] )
            child++;//child保留较小的子结点
        if( array[ child ] < tmp )   array[hole] = array[child];
        else break;
    }
   array[hole] = tmp;
}

时间复杂度分析：

  • 因为树有对数的深度，在最坏情况下，deQueue是一个对数时间的操作。
  • 根据堆的有序性，堆中最后一个结点的值一般都是比较大的。因此，向下过滤很少有提前结束的，所以deQueue操作平均也是对数时间。

建堆

一种不实用的方法
  • 看成N次连续插入
  • 时间复杂度为O(nlogn)O(n log n)
  • 输入数据和顺序都相同的情况下，该方法得出的二叉堆是唯一的
  • 事实上，在构造过程中，我们并不关心每个元素加入后堆的状态，我们关心的是N个元素全部加入后的最后状态，最后的状态是要保证堆的有序性。至于中间过程中的有序性是否成立并不重要。
  • 事实上，采用合适方法可以将时间复杂度降到O(n)
更合适的建堆方法
  • 利用堆的递归定义
  • 时间复杂度为O(N)O(N)
  • 具体方法：
    • 函数buildHeap可以将一棵完全二叉树调整为一个堆
    • 先对左子堆和右子堆递归调用buildHeap，保证除了根结点外，其余的地方都建立起了堆的有序性
    • 然后对根结点调用percolateDown，以创建堆的有序性
最好的方法：建堆的非递归实现
  • 以逆向层次的次序对结点调用percolateDown，直到根结点为止。
  • 注意：不需要对叶结点执行percolateDown。因此，我们是从编号最大的非叶结点i2\dfrac{i}{2}开始。
  • 时间复杂度O(N)
最终采用的方法：buildHeap()
1
2
3
4
5
6
template <class Type>
void priorityQueue<Type>::buildHeap( )
{  
    for ( int i = currentSize / 2; i > 0; i-- )
        percolateDown( i );
}
总结：最好的方法是非递归实现
  • 逆向层次次序调整每一个子堆
  • 在调整每个子堆时，除子堆的根以外，所有结点满足堆的定义
  • 根结点的调整和删除时一样，可以通过调用向下过滤percolateDown实现
0%