第14章 堆
1,二叉树是否是一个堆,由两个性质决定:(1)顺序:任何结点的值都小于或等于其子节点的值;
(2)形状:最多两层上具有叶子结点,其中最底层的叶子节点尽可能的靠左分布.树中不存在空闲的位置,即所有结点到根结点的距离都不超过log2n.
2,树中常见的函数定义如下:根结点位于x
root=1
value(i)=x
leftchild(i)=2*i
rightchild(i)=2*i+1
parent(i)=i/2
null(i)=(i<1)or(i>n)
如下图:
http://dl.iteye.com/upload/attachment/267242/b01cbb69-70ae-3fef-b256-7a2594899500.jpg
3,关键函数:siftup
策略:尽可能地将元素向上筛选,直到元素大于其父结点或位于树根.
结果:如果heap(1,n-1)为真,经过siftup,heap(1,n)为真.
代码:
void sitfup(n)pre n > 0 && heap(1, n-1)post heap(1, n)i = nloopif i == 1break;p = i / 2;if x <= xbreak;swap(p, i)i = p
运行时间和logn成正比.
4,关键函数:sitfdown
策略:将x向下筛选,和较小的子结点交换,直到没有子结点小于它的子结点.
heap(1, n),如果给x分配一个新值,得到heap(2, n).
代码:
void siftdown(n)pre heap(2, n) && n>=0post heap(1, n)i = 1loopc = 2*iif c > nbreak;if c+1 <= nif x < xc++ //取较小的子结点if x <= xbreak;swap(c, i);i = c;
运行时间和logn成正比.
5,堆排序
第一阶段:
建立heap(1,n)
for i =
sifup(i);
第二阶段:
建立有序序列
for (i = n; i >= 2; i--)
swap(1, i);
siftdown(i-1);
6,优先级队列:
template<class T>class priqueue{public:priqueue(int maxsize); //初始化集合为空void insert(T t);T extracmin();}void insert(t)if n >= maxsizereport error;break;n++;x = t;siftup(n);T extractmin()if n < 1report error;break;t = x;x = x;siftdown(n);return t;
7,实例代码:
#include <iostream>#include <ctime>using namespace std;template<class T>class priqueue{public: priqueue(int m) : n(0), maxsize(m), x(new T) {} void insert(T t) { x[++n] = t; for(int i = n, p; i > 1 && x > x; i = p) swap(p, i); } T extractmin() { T t = x; x = x; for (int i = 1, c; (c = 2*i) <= n; i = c) { if ( c+1 <= n && x < x) c++; if ( x <= x) break; swap(i, c); } return t; }private: void swap(int i, int j) { T t = x; x = x; x = t; }private: int n, maxsize; T* x;};int main(){ srand(time(0)); int m = 100; priqueue<int> pq(100); for (int i=0; i < m; i++) pq.insert( rand()%500 ); for (int i=0; i < m; i++) { cout << pq.extractmin() << " "; if ( (i + 1) % 10 == 0 ) cout << endl; }return 0;}
页:
[1]