优先队列(堆)

背景：系统调度 insert any, delete max

堆：纵向有序

查找树：横向有序

性质：

  • 顺序性质：纵向有序，根到叶节点路径递增
    • 定义：A min tree is a tree in which the key value in each node is no larger than the key values in its children (if any). A min heap is a complete binary tree that is also a min tree.
  • 结构性质：完全二叉树，id_fa = id_chl / 2
    • 定义：A binary tree with n nodes and height h is complete iff its nodes correspond to the nodes numbered from 1 to n in the perfect binary tree of height h
    • 性质：高度为h的完全二叉树节点数介于\(2^h\)和\(2^{h+1}-1\)
    • 表示：数组BT[1:n+1] (BT[0]不使用)
      • 引理：
\[ \text{parent}(i)=\left\{ \begin{array}{ll} \lfloor i/2\rfloor&,i\not=1\\ \text{None}&,i=1 \end{array} \right. \]
\[ \text{left\_child}(i)=\left\{ \begin{array}{ll} 2i&,2i\leqslant n\\ \text{None}&,2i>n \end{array} \right. \]
\[ \text{right\_child}(i)=\left\{ \begin{array}{ll} 2i+1&,2i+1\leqslant n\\ \text{None}&,2i+1>n \end{array} \right. \]

定义：A finite ordered list with zero or more elements

操作：

  • PriorityQueue Initialize (int MaxElements);
  • void Insert (ElementType X, PriorityQueue H);
  • ElementType DeleteMin (PriorityQueue H);
  • ElementType FindMin(PriorityQueue H);

初始化时，利用Elements[0]作岗哨，防止插入时落在堆外（否则每次循环需2个条件，效率低）

简单实现：

  • 数组
  • 链表
  • 有序数组（从大到小排）
  • 有序链表 问题：部分操作耗时多，部分操作耗时少

实现：

  • Initialize： 

    PriorityQueue  Initialize( int  MaxElements ) 
{ 
     PriorityQueue  H; 
     if ( MaxElements < MinPQSize ) 
    return  Error( "Priority queue size is too small" ); 
     H = malloc( sizeof ( struct HeapStruct ) ); 
     if ( H == NULL ) 
    return  FatalError( "Out of space!!!" ); 
     /* Allocate the array plus one extra for sentinel */ 
     H->Elements = malloc(( MaxElements + 1 ) * sizeof( ElementType )); 
     if ( H->Elements == NULL ) 
    return  FatalError( "Out of space!!!" ); 
     H->Capacity = MaxElements; 
     H->Size = 0; 
     H->Elements[ 0 ] = MinData;  /* set the sentinel */
     return  H; 
}

    设置岗哨Elements[0]

  • insertion：将父节点不断往下挪 \(T(N)=O(\log N)\) 

    /* 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; 
}

    (1)Elements[0]为岗哨，最后一定会停下来 (2)赋值速度比swap快

  • deletemin：先删除根，找最小儿子，判断能否放入最后一个节点，否则儿子向上提 

    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(P,\(\Delta\),H) / increaseKey(P,\(\Delta\),H)：向上 / 向下调整

  • delet(P,H) （删除任意元素）

    1. decrease(P,\(\infty\),H)调整至根
    2. deleteMin(H)

  • buildHeap(H)：

    • 法一：逐个插入 \(T(N)=O(N\log N)\)
    • 法二：从最后一个有儿子的节点\(\dfrac{n}{2}\)开始，向下一个一个调整 \(T(N)=O(N)\)
      • 子问题：左右儿子都是堆，如何调整根使之成为堆

        法一为深度和，深度越深节点越多；

        法二为高度和，高度越高节点越少

        故高度和 < 深度和，法二更优

  • 应用：找第\(k\)大数 \(O(N+k\log N)\)

    1. 建堆
    2. 删最大数\(k-1\)次

d-堆：每个节点有\(d\)个儿子

  • deleteMin复杂度\(O(d\log_d N)\) 找最小儿子交换时需要\(d\)次比较