二叉堆是一棵满足下列性质的完全二叉树：
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;
}
微信
支付宝
