lesson10

优先级队列
算法(server algorithm) <--------------------  数据(clients data)
      |                                         |     
      |                                         |
scheduler(调度器)<--priority queue <--------- 重要性指标(important priority)  
接口定义
template <typename T> struct PQ{
  virtual void insert(T) = 0;
  virtual T getMax() = 0;
  virtual T delMax() = 0;
};
只需查找极值元素，不必维护所以元素的全序关系
 
 完全二叉堆
 平衡因子处处非负的AVL   0 / 1
 若bf(v) = 0,则 lc(v)满
 若bf(v) = 1,则 rc(v)满
 完全二叉树
 逻辑节点与物理元素依层次遍历次序彼此对应
 #define Parent(i) ((i-1)>>1)
 #define LChild(i) (1 + (i<<1)) //奇数
 #define RChild(i) ((1 + i) <<1) //偶数
 
 template <typename T> class PQ_ComplHeap:public PQ<T>, public Vector<T>{
   protected : Rank percolateDown( Rank n, Rank i);//下滤
               Rank percolateUp (Rank i ); //上滤
               void heapify( Rank n); //Floyd建模算法
   public    : PQ_ComplHeap( T * A, Rank n)//p批量构造{
                  copyFrom( A, 0, n);
                  heapify(n);
               }
               void insert(T);
               T getMax(){return _elem[0];}
               T delMax(); 
 }      
 数值上，只要 0 < i，必满足H[i] <= H[Parent(i)]
 
 template <typename T> PQ_ComplHeap<T>::getMax(){
   return _elem[0];
 }
 插入及上滤
 template <typename T> PQ_ComplHeap<T>::insert( T e){
   Vector<T>::insert(e);
   percolateUp(_size -1);
 }
 template <typename T> PQ_ComplHeap<T>::percolateUp( Rank i){
   while ( ParentValid(i)){
     Rank j = Parent(i);
     if( lt( _elem[i],_elem[j])) break;
     swap (_elem[i], _elem[j]);
     i = j;
   }
   return i;
 }
 删除和下滤
  template <typename T> PQ_ComplHeap<T>::delMax(){
   T maxElem = _elem[0];
   _elem[0] = _elem[ --_size];
   percolateDown(_size,0);
   return maxElem;
 }
 template <typename T> PQ_ComplHeap<T>::percolateDown( Rank i){
   Rank j;
   while ( i!= ( j = ProperParent ( _elem, n, i))){
     swap (_elem[i], _elem[j]);
     i = j;
   }
   return i;
 }
 批量建堆
 PQ_ComplHeap( T * A, Rank n){
   copyFrom( A, 0, n);
   heapify(n);
 }
 version 1(自上而下的上滤)
 template <typename T> PQ_ComplHeap<T>::heapify( Rank n){
   for ( int i = 1; i < n; i ++)
     percolateUp(i);
 }
 version 2(自下而上的下滤)
template <typename T> PQ_ComplHeap<T>::heapify( Rank n){
   for ( int i = LastInternal(n); i >=0; i --)
     percolateDown(n,i);
 }
 堆排序算法
  1 初始化：heapify(),O(n)，建堆
  2 迭代： delMax(),O(logn),取出堆顶并调整复原
  template <typename T>
  void Vector<T>::heapSort( Rank lo, Rank hi){
    PQ_ComplHeap<T> H( _elem + lo, hi - lo);
    while(! H.empty())
      _elem[--hi] = H.delMax();
  }
左式堆
堆合并
H = merge(A,B):将堆A和B合二为一 //不妨设|A| = n >= m = |B|
方法一： A.insert(B.delMax())
O(m * (logm + log(n + m))) = O(mlog(n+m))
方法二：union(A,B).heapify( n + m)
O( m + n)

单侧倾斜：
  保持堆序性，附加新条件，使得在堆合并过程中，只需调整很少部分的节点O(logn)
  新条件  = 单侧倾斜 ： 节点分布偏向左侧
                       合并操作只涉及右侧
  不是完全二叉树
  先引入所有的外部节点，消除一度节点转为真二叉树
  NPL(空节点长度)
  npl(NULL) = 0
  npl(x) = 1 + min(npl(lc(x)),npl(rc(x)))
  验证：npl(x) = x 到外部节点的最近距离
       npl(x) = 以x为根的最大满子树的高度 
  左倾：对任意内节点x，都有npl(lc(x)) >= npl( rc(x))
  推论：对任何内节点x，都有npl(x) = 1 + npl(rc(x))
  
  右侧链
   rChain(x):从节点x出发，一直沿右分支前进
   rChain(root) 的终点，必为全堆中最浅的外部节点
     npl(r) = |rChain(r)| = d
     存在一颗以r为根、高度为d的满子树
   右侧链长为d的左式堆，至少包含 2^d-1 个内部节点，2^(d+1) - 1 个节点
   反之，在包含n个节点的左式堆中，右侧链的长度 d <= 下取整(log(n+1))-1 = O(logn)
   template< typename T> 
   class PQ_LeftHeap: public PQ<T>, public BinTree<T>{
      public:
        void insert(T);
        T getMax(){ return _root->data;}
        T delMax();
   }
  static BinNodePosi(T) merge( BinNodePosi(T) a, BinNodePosi(T) b){
    if( ! a) return b; //递归基
    if( ! b) return a; //递归基
    if( !lt( a->data, b->data) ) swap( b, a);//确保b不大
    a->rc = merge( a->rc, b);//将a的右子堆与b合并
    a->rc->parent = a;  //更新父子关系
    if ( ! a->lc || a->lc->npl < a->rc->npl)
      swap ( a->lc, a->rc); //确保左子堆
    a->npl = a->rc? a->rc->npl + 1 : 1;
    return a;
  };
  插入删除
  void PQ_LeftHeap<T>::insert( T e){
    BinNodePosi(T) v = new BinNode<T> (e);
    _root = merge( _root,v);
    _root->parent = NULL;
    _size ++;
  }
  void PQ_LeftHeap<T>::delMax(){
   BinNodePosi(T) lHeap = _root->lc;
   BinNodePosi(T) rHeap = _root->rc;
   T e = _root->data;
   delete _root;
   _size--;
   _root = merge(lHeap, rHeap);
   if( _root) _root->parent = NULL;
   return e;
  }