首页 > 代码库 > 通用的最小堆（最大堆）D-ary Heap
通用的最小堆（最大堆）D-ary Heap
听说有一种最小（大）堆，不限于是完全二叉树，而是完全D叉树，名为D-ary Heap（http://en.wikipedia.org/wiki/D-ary_heap）。D可以是1，2，3，4，100，对于优先队列该有的功能都没有问题。
动手写一个D-ary Heap，应该不难。简单起见，不考虑像STL一样通过template传入Comp类，下面的实现要求T类型重载了operator <和operator >。
template<class T>class DaryHeap{ size_t D; size_t size; vector<T> a; ...};
用vector容器存储数据，是因为在优先队列的插入、构建、删除操作需要RandomAccessIterator，而使用deque或其他STL容器都将影响性能。
为了节约点访问vector::size()函数的代价，用size_t size记录堆的大小。这也许没有必要，因为编译器可能对size()的调用做优化，而且访问size()的次数也并不多。
然后写堆的基本操作，即元素的上移下移。完全D叉树的性质和二叉树差不多，甚至可以推广到1叉树（数组）。
void up(size_t i) { while(i) { size_t p = (i-1)/D; if(a[p]>a[i]) { swap(a[p], a[i]); i = p; } else break; } } void down(size_t i) { size_t ii; size_t min = i*D+1; while(min<size) { for(ii=i*D+2; ii<size; ii++) if(a[min] > a[ii]) min = ii; if(a[min]<a[i]) { swap(a[min], a[i]); i = min; min = i*D+1; } else break; } }
写好了这两个函数，堆的插入删除排序构建就都一样了：
DaryHeap(int _D=2):size(0) { if(_D<1) D=1; else D=_D; } size_t getsize(){return size;} void push(T& x) { a.push_back(x); up(size++); } T& top() { if(size) return a[0]; } void pop() { if(size) { a[0] = a[--size]; a.pop_back(); down(0); } }
最后测试：
main(){ DaryHeap<int> h(10); for(int i=10; i>0; i--) { h.push(i); // h.print(); } for(int i=10; i>0; i--) { cout <<h.top()<<ends; h.pop(); }}
D-ary Heap的定义是：
1 逻辑上是一个完全多叉树；
2 每个父节点有最多D个子节点；
3 子节点永远比父节点大（小），前提是节点具有可比性。
性质：
1 父节点=(子节点-1)/D；
2 子节点=父节点*D+i (i=1, 2, ..., D)；
操作：
1 插入时将新插入元素放在最尾端，并与父节点交换位置直到比父节点大，即up操作。
2 从一个数组a构建成一个D-ary Heap，即需要每一个a[i](i>1)做如上的up操作。
3 删除一个节点时，将尾部的节点复制到待删除节点的位置，size-=1，然后将新复制节点从待删除节点开始向下移动，直到所有的子节点都比新复制节点大，down操作。至于怎么求子节点中最小的那个，要么去构建个局部的最小堆，要么就只好遍历咯。
4 排序：每一次将堆的根节点与尾节点a[size-1]交换，同时size-=1，再调整新根节点的位置（就是将堆首删除后拿到数组尾端。）
总的来说，和熟为人知的二叉树除了up和down有一点点不同，其他的一模一样。
通用的最小堆（最大堆）D-ary Heap