第14章 堆

1,二叉树是否是一个堆,由两个性质决定:
(1)顺序:任何结点的值都小于或等于其子节点的值;
(2)形状:最多两层上具有叶子结点,其中最底层的叶子节点尽可能的靠左分布.树中不存在空闲的位置,即所有结点到根结点的距离都不超过log2n.

2,树中常见的函数定义如下:根结点位于x[1]
root=1
value(i)=x[i]
leftchild(i)=2*i
rightchild(i)=2*i+1
parent(i)=i/2
null(i)=(i<1)or(i>n)
如下图:




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 = n
	loop
		if i == 1
			break;
		p = i / 2;
		if x[p] <= x[i]
			break;
		swap(p, i)
		i = p

运行时间和logn成正比.

4,关键函数:sitfdown
策略:将x[1]向下筛选,和较小的子结点交换,直到没有子结点小于它的子结点.
heap(1, n),如果给x[1]分配一个新值,得到heap(2, n).
代码:

void siftdown(n)
		pre heap(2, n) && n>=0
		post heap(1, n)
	i = 1
	loop
		c = 2*i
		if c > n
			break;
		if c+1 <= n
			if x[c+1] < x[c]
					c++ //取较小的子结点
		if x[i] <= x[c]
			break;
		swap(c, i);
		i = c;

运行时间和logn成正比.

5,堆排序
第一阶段:
建立heap(1,n)
for i = [2, n]
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 >= maxsize
		report error;
		break;
	n++;
	x[n] = t;
	siftup(n);

T extractmin()
	if n < 1
		report error;
		break;
	t = x[1];
	x[1] = x[n--];
	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[maxsize+1]) {}

    void insert(T t)
    {
        x[++n] = t;
        for(int i = n, p; i > 1 && x[p = i/2] > x[i]; i = p)
            swap(p, i);
    }

    T extractmin()
    {
        T t = x[1];
        x[1] = x[n--];
        for (int i = 1, c; (c = 2*i) <= n; i = c)
        {
            if ( c+1 <= n && x[c+1] < x[c])
                c++;
            if ( x[i] <= x[c])
                break;
            swap(i, c);
        }
        return t;
    }

private:
    void swap(int i, int j)
    {
        T t = x[i];
        x[i] = x[j];
        x[j] = 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;
}