《算法之美》---二叉堆及其实现

二叉堆是一棵满足下列性质的完全二叉树：

1）如果某节点有孩子，则根节点的值都小于孩子节点的值。我们称之为小根堆；

2）如果某节点有孩子，则根节点的值都大于孩子节点的值。我们称之为大根堆。

这样，如果我们用一维数组a存储来存储该堆，那么具有n个节点的堆可看成是一棵按层次排列，同一层按自左向右排列的完全二叉树。显然，小根堆的根节点是最小值，大根堆的根节点是最大值，计算过程分下面两步进行：

(1)—建堆，把数组a中各个元素转变成堆；

(2)—对数组a进行排序：

通过相继地输出根节点，产生递增（递减）序列；

保持余下节点的堆性质。

在调整中保持堆性质：

以小根堆为例，假设节点a[s]的左右子树都是小根堆，而添加a[s]后不满足小根堆性质，我们的方法是从根节点出发顺着左右子树的一边逐步进行调整，调整的过程实质上是让a[s]在小根堆中下降，最终满足以s为根的子树成为小根堆。过程如下：

1）找出s节点左右子节点中权值较小者，记其位置为j；

2）比较a[j]和a[s]：若a[s]的权值小于等于a[j]，则调整完毕；否则a[s]<---a[j]，s<---j，继续从s出发向下调整。

调整堆的伪代码如下所示：

//从a[s]出发向下调整建堆：若a[s]的左右孩子均大于a[s]，则调整完毕；

//否则，找出其中较小者，其序号记为j；a[s]和a[j]的值交换，继续由a[j]往下调整

procedure heap(s, n : longint);

Var

i, j, k : longint;

{

j <-- 1; k <-- a[s]; //暂存a[s]，a[s]左右孩子的较小者序号初始化为1

while j <> maxint do

{

i <-- a[s]; j <-- maxint; //找出a[s]的左右孩子的较小者，其序号为j

if s*2<=n //左孩子

then if a[s*2]<i then {i<--a[s*2]; j<--s*2;} //顺着左孩子方向找

if s*2+1<=n //右孩子

then if a[s*2+1]<i then{i<--a[s*2+1]; j<--(s*2+1); } //顺着右孩子方向找

if j<>maxint then {a[s]<--i; s<--j; } //a[s]的值调整为其左右孩子较小者，继续从a[j]往下调整

}

a[s]<--k; //最后位置的值调整为原子根值

}

下面是最小堆的一个类模板及其测试代码：

========================asce.h===========================

#include <iostream>

template<typename T> class MinPQ //抽象类

{

public:

virtual int Insert(const T&)=0; //纯虚函数

virtual int RemoveMin(T&)=0;

};

//最小堆的定义

template<typename T>

class MinHeap : public MinPQ<T>

{

public:

MinHeap(int maxSize);

MinHeap(T arr[], int n);

~MinHeap() {delete[] heap;}

int Insert(const T &x); //入队

int RemoveMin(T &x); //出队

bool IsEmpty() const

{

return currentSize == 0;

}

bool IsFull() const

{

return currentSize == MaxHeapSize;

}

private:

enum{DefaultSize = 10};

T *heap; //存放堆的数组

int currentSize; //当前元素个数，堆尾

int MaxHeapSize;

void FilterDown(int start ,int endOfHeap);

void FilterUp(int start);

};

//构造函数，根据给定大小maxSize，建立堆对象

template<typename T>

MinHeap<T>::MinHeap(int maxSize)

{

//确定堆大小

MaxHeapSize = DefaultSize<maxSize ? maxSize : DefaultSize;

heap = new T[MaxHeapSize]; //创建堆数组空间

currentSize = 0;

}

//构造函数，根据数组建立堆对象

template<typename T>

MinHeap<T>::MinHeap(T arr[], int n)

{

//确定堆大小

MaxHeapSize = DefaultSize<n ? n : DefaultSize;

heap = new T[MaxHeapSize];

heap = arr; //数组传送

currentSize = n; //当前堆大小

int currentPos = (currentSize-1)/2; //最后的非叶子节点

while(currentPos >= 0)

{

//从上到下逐步扩大，形成堆

FilterDown(currentPos, currentSize-1);

//从currentPos开始到currentSize为止，调整

currentPos--;

}

}

//最小堆的向下调整算法

template<typename T>

void MinHeap<T>::FilterDown(int start, int endOfHeap)

{

int i = start;

int j = 2*i + 1; //j是的左孩子

T temp = heap[i];

while(j <= endOfHeap)

{

if(j < endOfHeap && heap[j] > heap[j+1])

j++; //左右两孩子中选择较小者，即heap[j+1]

if(temp <= heap[j])

break; //调整结束

else

{

heap[i] = heap[j];

i = j;

j = 2*j + 1;

}

}

heap[i] = temp;

}

//堆的插入操作

template<typename T>

int MinHeap<T>::Insert(const T &x)

{

//在堆中插入新元素x

if(currentSize == MaxHeapSize) //堆满

{

std::cout<<"堆已满"<<std::endl;

return 0;

}

heap[currentSize] = x; //插在表尾

FilterUp(currentSize); //向上调整堆

currentSize++; //堆元素增1

return 1;

}

//最小堆的向上调整算法（堆已建好，用于插入）

template<typename T>

void MinHeap<T>::FilterUp(int start)

{

//从start开始向上直到0，调整堆

int j = start;

int i = (j-1)/2; //i是j的双亲

T temp = heap[j];

while(j > 0)

{

if(heap[i] <= temp)

break;

else

{

heap[j] = heap[i];

j = i;

i = (i-1)/2;

}

}

heap[j] = temp;

}

//最小堆的删除算法（出堆），输入参数x用于接收出堆的元素

//不断调用RemoveMin函数输出x就相当于升序排序了

template<typename T>

int MinHeap<T>::RemoveMin(T &x)

{

if(currentSize <= 0)

{

std::cout<<"堆已空"<<std::endl;

return 0;

}

x = heap[0]; //最小元素heap[0]出队列

heap[0] = heap[currentSize-1]; //用最后元素填补

currentSize--;

//从0号位置开始自上向下调整为最小堆

FilterDown(0, currentSize-1);

return 1;

}

=====================测试代码TestCase.cpp======================

#include "asce.h"

int main()

{

int arr[] = {1, 4, 34, 6, 43, 10,9};

MinHeap<int> ace(arr, 8);

int show = 0;

for(int i=0; i<7; i++)

{

ace.RemoveMin(show);

std::cout<<show<<std::endl;

}

system("pause");

return 0;

}