二叉堆-白红宇

二叉堆

阅读量：7062 次

发布时间：2019-06-28

本文共 2205 字，大约阅读时间需要 7 分钟。

容易证明：

一棵高为h的完全二叉树有2^h 到 2^(h+1)-1个结点。

这就意味着，完全二叉树的高是[logN]

特点：

任意位置i：

左儿子在位置2i上，右儿子在位置2i+1上，父亲在i/2上

一个堆数据结构将由一个Comparable数组和一个代表当前堆的大小的整数组成：

优先队列的接口:

1 template 
     
       2 class BinaryHeap 3 { 4 public: 5     explicit BinaryHeap ( int capacity = 10 ); 6     explicit BinaryHeap ( const Vector
      
        & items); 7  8     bool isEmpty() const; 9     const Comparable & findMin() const;10 11     void insert(const Comparable & x);12     void deleteMin();13     void deleteMin(Coparable & minItem);14     void makeEmpty();15 private:16     int currentSize;17     vector
       
         array;18     void buildHeap();19     void percolateDown(int hole);20 }

堆序的性质：如果想要找到一个最小点，最好是把最小值移动到堆的最上方，使用方法: 上滤

应用比如插入一个元素到堆中：

1 void insert(const Comparable & x) 2 { 3     if(currentSize == array.size()-1) 4         array.resize(array.size()*2); 5  6     int hole = ++currentSize; 7  8     for( ; hole > 1 && x < array[hole/2];hole /= 2) 9         array[hole] = array[hole/2];10     array[hole] = x;11 }

想要删除一个堆结点，一般都是要把堆结点移动到最顶端，然后通过下滤方法删除：

1 void deletMin() 2 { 3     if(isEmpty()) 4         throw UnderflowException(); 5  6     array[1] = array[currentSize--]; 7     percolateDown(1); 8 } 9 void deleteMin(Comparable & minItem)10 {11     if(isEmpty())12         throw UnderflowException();13     minItem = array[1];14     array[1] = array[currentSize--];15     percolateDown(1);16 }17 void percolateDown(int hole)18 {19     int child;20     Comparable tmp = array[hole];21     for( ; hole*2 <= currentSize;hole = child)22     {23         child = hole*2;24         if(child != currentSize && array[child+1] < array[child])25             child++;26         if(array[child] < tmp)27             array[hole] = array[child];28         else29             break;30     }31     array[hole] = tmp;32 }

堆的其他操作：

decreaseKey（p,@）:把p结点的元素减少到p-@

increaseKey (p,@):把p结点的元素增加到p+@

remove (p)一般都是先用decreaseKey(p,无限大),减少到最小，然后移动至堆顶端，用deleteMin方法删除。

buildHeap：构造堆原始集合

1 explicit BinaryHeap( const vector
     
       & items): array(item.size()+10),currentSize(items.size()) 2 { 3     for(int i=0;i
      
       0;i--)10         percolateDown(i);11 }