问答题
阅读下列说明和C代码，回答下面问题。
[说明]
堆数据结构定义如下。
对于n个元素的关键字序列{a 1 ，a 2 ，…，a n }，当且仅当满足下列关系时称其为堆。
在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若堆顶元素为最小元素，则称为小顶堆。堆常用完全二叉树表示，下图是一个大顶堆的例子。
[说明]
堆数据结构定义如下。
对于n个元素的关键字序列{a 1 ，a 2 ，…，a n }，当且仅当满足下列关系时称其为堆。
在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若堆顶元素为最小元素，则称为小顶堆。堆常用完全二叉树表示，下图是一个大顶堆的例子。
问答题
根据以上说明和C代码，填充C代码中的空白处。
【正确答案】
【答案解析】A-＞int_array[0]
A-＞int_array[0]=A-＞int_array[A-＞array_size-1]
A-＞array_size-1
A-＞int_array[PARENT(i)]＜key
A-＞int_array[i]=key 本题考查排序算法中的堆排序相关内容。
题目告诉我们函数heapMaximum(A)的功能是返回大顶堆A中的最大元素；函数heapExtractMax(A)的功能是去掉并返回大顶堆A的最大元素，将最后一个元素“提前”到堆顶位置，并将剩余元素调整成大顶堆；而函数maxHeaplnsen(A，key)的功能是把元素key插入到大顶堆A的最后位置，再将A调整成大顶堆。
第1空在函数heapMaximum(A)中，而且从程序中可以看出，是返回的结果，那么应该是大顶堆中最大的元素，即A-＞int_array[0]。
第2空在函数heapExtractMax(A)中，根据该函数的功能描述，并结合程序可以看出，第2空是在将最大元素移出后，那么接下来应该处理将最后一个元素“提前”到堆顶位置，那么就应该是A-＞int_array[0]=A-＞int_arrrdy[A-＞array_size-1]。
第3、4、5空都在函数maxHeaplnsert(A，key)中。从程序和函数的功能我们可以知道，从程序第3空到最后，作用是找到元素key的插入位置并插入该元素。第3空是给变量i赋值，从后面的程序中我们可以看出i是作为数组下标的；而查找元素插入的位置应该按从后往前的顺序，因此i的初值应该为A-＞array size-1，从循环中也可以看出i的值在逐渐变小。
第4空是循环的一个条件，而循环的作用是找到合适的插入位置，由于大项堆的特点是根节点的值大于左右子树节点上的值，那么找到比待插入元素大的父节点时，应该就找到了它插入的合适位置，而每次操作后i的值被赋值为PARENT(i)，很显然这是找到其父节点的存储位置，因此循环结束的一个条件就是找到一个比key值大的父节点，那么循环继续的条件就是父节点的值小于key的值，所以本空的答案为A-＞int_array[PARENT(i)]＜key。
第5空就是插入元素，所以应该填A-＞int_array[i]=key。
A-＞int_array[0]=A-＞int_array[A-＞array_size-1]
A-＞array_size-1
A-＞int_array[PARENT(i)]＜key
A-＞int_array[i]=key 本题考查排序算法中的堆排序相关内容。
题目告诉我们函数heapMaximum(A)的功能是返回大顶堆A中的最大元素；函数heapExtractMax(A)的功能是去掉并返回大顶堆A的最大元素，将最后一个元素“提前”到堆顶位置，并将剩余元素调整成大顶堆；而函数maxHeaplnsen(A，key)的功能是把元素key插入到大顶堆A的最后位置，再将A调整成大顶堆。
第1空在函数heapMaximum(A)中，而且从程序中可以看出，是返回的结果，那么应该是大顶堆中最大的元素，即A-＞int_array[0]。
第2空在函数heapExtractMax(A)中，根据该函数的功能描述，并结合程序可以看出，第2空是在将最大元素移出后，那么接下来应该处理将最后一个元素“提前”到堆顶位置，那么就应该是A-＞int_array[0]=A-＞int_arrrdy[A-＞array_size-1]。
第3、4、5空都在函数maxHeaplnsert(A，key)中。从程序和函数的功能我们可以知道，从程序第3空到最后，作用是找到元素key的插入位置并插入该元素。第3空是给变量i赋值，从后面的程序中我们可以看出i是作为数组下标的；而查找元素插入的位置应该按从后往前的顺序，因此i的初值应该为A-＞array size-1，从循环中也可以看出i的值在逐渐变小。
第4空是循环的一个条件，而循环的作用是找到合适的插入位置，由于大项堆的特点是根节点的值大于左右子树节点上的值，那么找到比待插入元素大的父节点时，应该就找到了它插入的合适位置，而每次操作后i的值被赋值为PARENT(i)，很显然这是找到其父节点的存储位置，因此循环结束的一个条件就是找到一个比key值大的父节点，那么循环继续的条件就是父节点的值小于key的值，所以本空的答案为A-＞int_array[PARENT(i)]＜key。
第5空就是插入元素，所以应该填A-＞int_array[i]=key。
问答题
根据以上C代码，函数heapMaximum，heapExtractMax和maxHeaplnsert的时间复杂度的紧致上界分别为______、______和______(用O符号表示)。
【正确答案】
【答案解析】O(1) O(lgn) O(lgn)
根据题目描述，heapMaximum用来返回大顶堆A中的最大元素，而且大顶堆已经建成，只需要通过一步操作就能取到。因此时间复杂度是O(1)。
而对于heapExtractMax是用来去掉大顶堆A的根，然后重新建堆，当输出堆顶节点并将堆中最后一个节点设置为根节点之后，根节点将有可能不再满足堆的性质，所幸的是整个序列也只有根节点一处的堆结构可能被破坏，其余节点仍然满足堆性质，故可利用性质进行堆调整，算法的基本思想为：将新堆顶沿着其关键字较大的子节点向下移动，直到叶子节点或者满足堆性质为止。因此相对于有n个元素的堆，只需要lgn次比较即可完成，因此时间复杂度是O(lgn)，这与书本说堆排序的算法时间复杂度是：O(nlgn)不冲突，因为书本上是对堆中所有元素进行操作，而这里其实相当于只将一个元素入堆，因此少了一个n。同样的道理可以得到maxHeaplnsert的时间复杂度O(lgn)。
而对于heapExtractMax是用来去掉大顶堆A的根，然后重新建堆，当输出堆顶节点并将堆中最后一个节点设置为根节点之后，根节点将有可能不再满足堆的性质，所幸的是整个序列也只有根节点一处的堆结构可能被破坏，其余节点仍然满足堆性质，故可利用性质进行堆调整，算法的基本思想为：将新堆顶沿着其关键字较大的子节点向下移动，直到叶子节点或者满足堆性质为止。因此相对于有n个元素的堆，只需要lgn次比较即可完成，因此时间复杂度是O(lgn)，这与书本说堆排序的算法时间复杂度是：O(nlgn)不冲突，因为书本上是对堆中所有元素进行操作，而这里其实相当于只将一个元素入堆，因此少了一个n。同样的道理可以得到maxHeaplnsert的时间复杂度O(lgn)。
问答题
若将元素10插入到堆A=(15，13，9，5，12，8，7，4，0，6，2，1)中，调用maxHeaplnsert函数进行操作，则新插入的元素在堆A中第______个位置(从1开始)。
【正确答案】
【答案解析】3这个我们可以结合题目给出的那个大顶堆的图来看，首先将key插入在最后，应该是8这个节点的右子树，由于10比8大，所以应该互换，再与节点9比较，由于10仍然大于9，所以也应该互换，这个时候再与其父节点15比较，由于小于15，所以不需要再调整，那么调整后的结果就是10这个元素应该作为根节点15的右子树。那么很显然10应该是在堆A中第3个位置。