Skip to content

优先队列(堆)#

ADT 模型#

  • 对象:一个有限的有序集
  • 操作:
    • 初始化
    • 插入
    • 删除最小的元素
    • 寻找最小的元素

简单的实现#

  • 数组:
    • 插入元素到末尾 \(\Theta(1)\)
    • 找到最大/最小元素 \(\Theta(n)\), 删除元素移动数组 \(O(n)\)
  • 链表:
    • 插入元素到链表开头 \(\Theta(1)\)
    • 找到最大/最小元素 \(\Theta(n)\), 删除元素 \(\Theta(1)\)
  • 有序数组:
    • 插入 找到合适的位置 \(O(n)\), 移动数组并插入元素 \(O(n)\)
    • 删除开头/末尾元素 \(\Theta(1)\)
  • 有序链表:
    • 插入 找到合适的位置 \(O(n)\), 插入元素 \(\Theta(1)\)
    • 删除开头/末尾元素 \(\Theta(1)\)

二叉堆#

结构性质#

堆是一棵被完全填满的二叉树,有可能的例外是在底层:底层上的元素从左到右填入。这样的树称为完全二叉树

一棵高 h 的完全二叉树的节点个数介于 \(2^h\)\(2^{h+1}-1\) 之间,即完全二叉树的高度是 \(\lfloor \log N\rfloor\)

对于下标为 \(i\) 的元素,其左儿子位于 \(2i\) 上,右儿子位于 \(2i+1\) 上,他的父亲位于 \(\lfloor i/2 \rfloor\) 上。

堆序性质#

如果一棵树,每个节点的值都不大于其儿子节点的值,那么这是一棵小根树小根堆就是满足小根树性质的完全二叉树。

基本的堆操作#

插入#

对于新的节点,唯一可以放的位置就是下一个空闲位置,否则堆将不再是完全树,但这样可能破坏堆的序,我们一般采用上浮的策略。

/* H->Element[ 0 ] is a sentinel */ 
void  Insert( ElementType  X,  PriorityQueue  H ) 
{ 
     int  i; 

     if ( IsFull( H ) ) { 
    Error( "Priority queue is full" ); 
    return; 
     } 

     for ( i = ++H->Size; H->Elements[ i / 2 ] > X; i /= 2 ) 
    H->Elements[ i ] = H->Elements[ i / 2 ]; 

     H->Elements[ i ] = X; 
}

注意这里代码实现中,我们没有使用交换操作,因为交换操作的时间成本更高。

删除最小元#

我们一般采用下滤的策略。删除最小元后,在根节点产生一个空穴。同时堆少了一个元素,我们必须把堆最后一个元素 X 移动到堆的某个地方。从根节点的空穴开始我们将空穴的两个儿子中的较小者移入空穴,这样就把空穴往下推了一层。重复步骤直到 X 可以放入空穴。

ElementType  DeleteMin( PriorityQueue  H ) 
{ 
    int  i, Child; 
    ElementType  MinElement, LastElement; 
    if ( IsEmpty( H ) ) { 
         Error( "Priority queue is empty" ); 
         return  H->Elements[ 0 ];   } 
    MinElement = H->Elements[ 1 ];  /* save the min element */
    LastElement = H->Elements[ H->Size-- ];  /* take last and reset size */
    for ( i = 1; i * 2 <= H->Size; i = Child ) {  /* Find smaller child */ 
         Child = i * 2; 
         if (Child != H->Size && H->Elements[Child+1] < H->Elements[Child]) 
           Child++;     
         if ( LastElement > H->Elements[ Child ] )   /* Percolate one level */ 
           H->Elements[ i ] = H->Elements[ Child ]; 
         else     break;   /* find the proper position */
    } 
    H->Elements[ i ] = LastElement; 
    return  MinElement; 
}

其他的堆操作#

需要注意的是,对于小根堆,找除了最小元以外的元素都需要线性搜索整个堆。

  • DecreaseKey
    DecreaseKey(P,\(\Delta\),H) 操作降低在位置 P 处的关键字的值。我们需要上滤操作对堆进行调整。
  • IncreaseKey
    IncreaseKey(P,\(\Delta\),H) 操作增加在位置 P 处的关键字的值。我们需要下滤操作对堆进行调整。
  • Delete
    Delete(P,H) 操作删除堆中位置 P 上的节点。这个操作首先执行 DecreaseKey(P,\(\infty\),H) 再执行 DeleteMin 即可。
  • BuildHeap
    BuildHeap(H) 操作把 N 个关键字作为输出并把它们放在空队中,可以使用 N 个相继的 Insert 操作完成。
    也可以将 N 个关键字以任意顺序放入树中构成一棵完全二叉树,从倒数第二层开始依次 percolate down. 可以证明这时只需要线性的时间复杂度就可以完成树的构建。

定理:包含 \(2^{h+1}-1\) 个节点,高度为 \(h\) 的理想二叉树,其节点的高度和为 \(2^{h+1}-1-(h+1)\)
证明:\(S=\sum\limits_{i=0}^h 2^i(h-i)\)
因此 BuildHeap 的操作是线性的

d-Heaps#

d-堆是二叉堆的推广,所有的节点都有 d 个儿子(因此二叉堆是 2-堆) d-堆比二叉堆浅,因此 Insert 操作改进为 \(O(\log_dN)\) 但对于大的 d, DeleteMin 会花费更多时间,因为我们每层都要找出 d 个儿子中的最小者。这样操作的用时就是 \(O(d\log_dN)\)。而且当 d 不是 2 的幂次时,找出儿子和父亲会花费更多的时间。

Info

Priority queue: 优先队列
Binary heap: 二叉堆
堆序: heap order
上浮:percolate up
下滤:percolate down


Last update: 2023年9月27日 10:52:36
Created: 2023年9月27日 10:52:36