#define leftchild(i) ( 2*(i)+1 ) void BuildMaxHeap( ElementType A[], int N ) { int i, j, child; ElementType Tmp; for ( i = (N-1)/2; i >= 0; i-- ) { j = i; for ( Tmp = A[j]; leftchild(j) < N; j = child ) { child = leftchild(j); if ( ) child ++; if ( ) A[j] = A[child]; else break; } ; } }填完这段代码
时间: 2024-03-12 13:50:22 浏览: 114
这段代码是一个建立最大堆的函数,需要填写两个条件的判断语句。
第一个条件判断语句需要比较左右子节点的大小,如果右子节点比左子节点大,需要返回右子节点的下标。
第二个条件判断语句需要比较当前节点和其较大的子节点的大小,如果当前节点比其子节点小,需要将当前节点和其子节点交换位置。
下面是填好代码的函数:
```
#define leftchild(i) ( 2*(i)+1 )
void BuildMaxHeap( ElementType A[], int N ) {
int i, j, child;
ElementType Tmp;
for ( i = (N-1)/2; i >= 0; i-- ) {
j = i;
for ( Tmp = A[j]; leftchild(j) < N; j = child ) {
child = leftchild(j);
if (child+1 < N && A[child+1] > A[child])
child ++;
if ( A[child] > Tmp )
A[j] = A[child];
else
break;
}
A[j] = Tmp;
}
}
```
相关问题
#define leftchild(i) ( 2*(i)+1 ) void BuildMinHeap( ElementType A[], int N ) { int i, j, child; ElementType Tmp; for ( i = (N-1)/2; i >= 0; i-- ) { j = i; for ( Tmp = A[j]; leftchild(j) < N; j = child ) { child = leftchild(j); if ( ) child ++; if ( ) A[j] = A[child]; else break; } ; } }填完这段代码
这段代码是一个建立最小堆的函数,需要填写两个条件的判断语句。
第一个条件判断语句需要比较左右子节点的大小,如果右子节点比左子节点小,需要返回右子节点的下标。
第二个条件判断语句需要比较当前节点和其较小的子节点的大小,如果当前节点比其子节点大,需要将当前节点和其子节点交换位置。
下面是填好代码的函数:
```
#define leftchild(i) ( 2*(i)+1 )
void BuildMinHeap( ElementType A[], int N ) {
int i, j, child;
ElementType Tmp;
for ( i = (N-1)/2; i >= 0; i-- ) {
j = i;
for ( Tmp = A[j]; leftchild(j) < N; j = child ) {
child = leftchild(j);
if (child+1 < N && A[child+1] < A[child])
child ++;
if ( A[child] < Tmp )
A[j] = A[child];
else
break;
}
A[j] = Tmp;
}
}
```
#define leftchild(i) ( 2*(i)+1 ) void PercDown( ElementType A[], int i, int N ) { int child; ElementType Tmp; for ( Tmp = A[i]; leftchild(i) < N; i = child ) { child = leftchild(i); if ( ) child ++; if ( ) A[i] = A[child]; else break; } ; } void Heapsort( ElementType A[ ], int N ) { int i; for ( i = N / 2; i>= 0; i -- ) /* BuildHeap */ PercDown( A, i, N ); for ( i = N-1; i >0; i -- ) { Swap( &A[ 0 ], &A[ i ] ); ; } }
你的代码片段中实现了一个堆排序算法。堆排序是一种基于堆数据结构的排序算法,它的核心思想是首先将待排序的序列构造成一个最大堆(或最小堆),然后将堆顶元素与堆底元素交换,再对剩余的元素重新构造最大堆,重复执行这个过程直到排序完成。
具体来说,你的代码实现了一个最大堆的构造函数`PercDown`和一个堆排序函数`Heapsort`。`PercDown`函数用于将以`A[i]`为根的子树构造成最大堆,`N`为堆的大小。`Heapsort`函数首先利用`PercDown`函数构造出一个最大堆,然后不断将堆顶元素与堆底元素交换,并重新构造最大堆,直到排序完成。
`leftchild(i)`是一个宏定义,用于计算以`i`为根节点的子树的左孩子在数组中的下标。在`PercDown`函数中,首先将`A[i]`保存到`Tmp`中,然后只要`i`的左孩子在堆中,就将`child`赋值为`i`的左孩子。如果`i`还有右孩子,并且右孩子比左孩子大,则将`child`更新为右孩子。如果`Tmp`比`child`的值小,则将`A[i]`赋值为`A[child]`,`i`更新为`child`,继续下一轮循环。如果`Tmp`比`child`的值大,则说明`A[i]`已经处于最大堆中的正确位置,可以跳出循环了。
阅读全文