读书人

堆删除算法中将根元素沿着树向下移动

发布时间: 2012-02-14 19:19:19 作者: rapoo

堆删除算法中,将根元素沿着树向下移动算法 中的问题
堆删除算法中,将根元素沿着树向下移动算法
代码如下:

C/C++ code
template <class T>void moveDown(T data[], int first, int last){    int largest = 2 * first + 1;    while (largest <= last)    {        if (largest < last && data[largest] < data[largest + 1])            largest++;        if (data[first] < data[largest])        {            swap(data[first], data[largest]);            first = largest;            largest = 2 * first + 1;        }        else            largest = last + 1;    }}


形参表中last参数是表示的什么呢?知道的前辈请帮一下忙

[解决办法]
我不敢确定你的代码的正确性,删除操作的这个操作是为了保持堆结构,看你的代码应该是我猜你应该想是这样实现,
首先,将根和他的两个孩子比较,如果大于两个孩子就已经保持堆结构,退出函数,如果根元素小于两个孩子就将它与较大的那个孩子交换,再把他变成这个孩子,对以他为根的子树重复以上过程。下面是我写的一个:
void MAX_HEAPIFY(int a[MAX],long i) //保持堆结构 a数组即是堆数组,i是根元素
{
long l=2*i; //左孩子
long r=2*i+1; //右孩子
long largest,t; //用largest表示根,左孩子,右孩子中的最大值
if(l<=len&&a[l]>a[i]) largest=l; //len是堆中元素个数即数组长度,也是你说的last,用last控制防止数组越界
else largest=i; //这判断根与左孩子的大小
if(r<=len&&a[r]>a[largest]) largest=r; //这里得到了三者的最大值
if(largest!=i) //如果largst!=i 说明根元素不是最大的,要交换根元素与他的那个较大的孩子
{
t=a[i];
a[i]=a[largest];
a[largest]=t;
MAX_HEAPIFY(a,largest); //将根元素赋成那个孩子,向下递归调用
}
}

读书人网 >C++

热点推荐