ＪAVA数据结构和算法（第十二章）学习笔记

DATE：2013－8－4
-------------------------------
一.堆的特点：
Ａ）它是完全二叉树
Ｂ）一般情况下，用数组实现
Ｃ）堆中的每一节点都满足堆的条件（每一节点的关键字都大小或等于子节点的关键字）
Ｄ）相对于二叉搜索树，它是弱序的
Ｅ）节点索引下标：
》父节点下标：(index-1)/2
》左子节点：2*index + 1
》右子节点：2*index + 2

二、用堆实现的优先队列
１、前提
２、关键算法：
Ａ）向上筛选（插入）

　int parent = (index-1) / 2;
      Node bottom = heapArray[index];
      while( index > 0 && //向上寻找合适的位置
             heapArray[parent].getKey() < bottom.getKey() )
         {
         heapArray[index] = heapArray[parent];  // move it down
         index = parent;
         parent = (parent-1) / 2;
         }  // end while
      heapArray[index] = bottom;//找到了合适的插入位置
     
     
    Ｂ）向下筛选（移除、排序） 
   
    　int largerChild;
      Node top = heapArray[index];       // save root
      while(index < currentSize/2)       // while node has at
         {                               //    least one child,
         int leftChild = 2*index+1;
         int rightChild = leftChild+1;
                                         // find larger child
         if(rightChild < currentSize &&  // (rightChild exists?)
                             heapArray[leftChild].getKey() <
                             heapArray[rightChild].getKey())
            largerChild = rightChild;
         else
            largerChild = leftChild;
                                         // top >= largerChild?
         if( top.getKey() >= heapArray[largerChild].getKey() )
            break;
                                         // shift child up
         heapArray[index] = heapArray[largerChild];
         index = largerChild;            // go down
         }  // end while
      heapArray[index] = top; 
     
     
   ３、优缺点：相对于快速排序，略慢；但它对初始数据的分布不敏感
   ４、效率：Ｏ（Ｎ*logN）