最小-最大堆的实现(二)
}
/*
* 下滤：节点值从小变大的过程叫做下滤
* 下滤的过程包括从根开始向下的所有偶数层，转换到奇数层后
* 再从底部向上经历所有的奇数层
* 插入：在树的底端进行，要么经过上滤到偶数层上，要么
* 下滤到奇数层上
* 删除最小值：从堆的1位置求出最小值，把对最后一个
* 数据放到1位置上，然后经过一个完整的下滤过程
* IncreaseKey：增大关键字的值，是将关键字位置增加后，对
* 其经历一个完整的下滤过程
*/
static Position
PercolateDown(Position i, MinMaxHeap H)
{
int j = i;
ElementType X;
H->Elements[0] = MaxElement;
X = H->Elements[i];
while(j>1) j = j >> 2;
/* 偶数层,先下滤,再上滤,奇数层直接上滤 */
if(j==1)
{
/* 下滤到一个偶数层上 */
for( ; i*4 < H->Size; i = j)
{
int k;
j = k = 4*i;
if(H->Size>=k+1 && H->Elements[j] > H->Elements[k+1]) j = k+1;
if(H->Size>=k+2 && H->Elements[j] > H->Elements[k+2]) j = k+2;
if(H->Size>=k+3 && H->Elements[j] > H->Elements[k+3]) j = k+3;
if(H->Elements[j] < X)
H->Elements[i] = H->Elements[j];
else
break;
}
H->Elements[i] = X;
/* 进行奇偶层互换,把奇数层上的一个最小值替换到偶数层上 */
j = i*2;
if(j < H->Size) //j的值最大可以是H->Size-1为偶数,H->Size是奇数值
{
if(H->Elements[j] > H->Elements[j+1]) j++;
}
else if(j > H->Size) j = i/2;
if(H->Elements[j] < X)
{
H->Elements[i] = H->Elements[j];
i = j;
}
else
return i;
}
/* 上滤 */
for( ; H->Elements[i/4] < X ; i /= 4)
H->Elements[i] = H->Elements[i/4];
H->Elements[i] = X;
return i;
}
/*
* 插入：
* 在堆的最后的位置插入关键字，要么经历上滤过程
* 要么经历下滤过程
*/
static void
Insert(ElementType X, MinMaxHeap H)
{
Position i;
if(IsFull(H)) return ;
i = ++H->Size;
H->Elements[i] = X;
i=PercolateUp(i, H);
if(i==H->Size)
PercolateDown(i, H);
}
/*
* 删除最小值：
* 将1号位置的值取下来，把最后一个元素放到此处
* 然后经历一个完整的下滤过程
*/
static ElementType
DeleteMin(MinMaxHeap H)
{
ElementType Min;
if(IsEmpty(H)) return MinElement;
Min = H->Elements[1];
H->Elements[1] = H->Elements[H->Size--];
PercolateDown(1, H);
return Min;
}
/*
* 查找最小值
*/
static ElementType
FindMin(MinMaxHeap H)
{
return H->Elements[1];
}
/*
* 删除最大值：
* 对2和3号位置比较大小后，把最后一个元素放到此处
* 然后经历一个完整的上滤过程
*/
static ElementType
DeleteMax(MinMaxHeap H)
{
int i;
ElementType Max;
if(IsEmpty(H)) return MaxElement;
if(H->Elements[2] < H->Elements[3])
{
Max = H->Elements[3];
i = 3;
}
else
{
Max = H->Elements[2];
i = 2;
}
H->Elements[i] = H->Elements[H->Size--];
PercolateUp(i, H);
return Max;
}
/*
* 查找最大值
*/
static ElementType
FindMax(MinMaxHeap H)
{
return H->Elements[2] < H->Elements[3]
H->Elements[3] : H->Elements[2];
}
/*
* 减小关键字的值
* 对i位置的值减小后执行上滤过程
*/
static void
DecreaseKey(Position i, ElementType Delta, MinMaxHeap H)
{
if(i <= H->Size)
{
H->Elements[i] -= Delta;
PercolateUp(i, H);
}
}
/*
* 增加关键字的值
* 对i位置的值增加后执行下滤过程
*/
static void
IncreaseKey(Position i, ElementType Delta,