容易证明：
一棵高为h的完全二叉树有2^h 到 2^(h+1)-1个结点。
这就意味着，完全二叉树的高是[logN]
特点：
任意位置i：
左儿子在位置2i上，右儿子在位置2i+1上，父亲在i/2上
一个堆数据结构将由一个Comparable数组和一个代表当前堆的大小的整数组成：
优先队列的接口:
1 template <typename Comparable> 2 class BinaryHeap 3 { 4 public: 5 explicit BinaryHeap ( int capacity = 10 ); 6 explicit BinaryHeap ( const Vector<Comparable> & 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<Comparable> 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 else 29 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<Comparable> & items): array(item.size()+10),currentSize(items.size()) 2 { 3 for(int i=0;i<items.size();i++) 4 array[i+1] = items[i]; 5 buildHeap(); 6 } 7 void buildHeap() 8 { 9 for( int i = currentSize/2; i>0;i--) 10 percolateDown(i); 11 }
本文转自博客园xingoo的博客，原文链接：二叉堆，如需转载请自行联系原博主。
