試題四
閱讀下列說(shuō)明和C代碼，回答問(wèn)題1至問(wèn)題3，將解答寫(xiě)在對(duì)應(yīng)欄內(nèi)。
[說(shuō)明]
堆數(shù)據(jù)結(jié)構(gòu)定義如下：
對(duì)于n個(gè)元素的關(guān)鍵字序列{a1, a2, …, an}，當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)稱其為堆。

在一個(gè)堆中，若堆頂元素為最大元素，則稱為大頂堆；若堆項(xiàng)元素為最小元素，則稱為小頂堆。堆常用完全二叉樹(shù)表示，圖4-1是一個(gè)大頂堆的例子。

堆數(shù)據(jù)結(jié)構(gòu)常用于優(yōu)先隊(duì)列中，以維護(hù)由一組元素構(gòu)成的集合。對(duì)應(yīng)于兩類堆結(jié)構(gòu)，優(yōu)先隊(duì)列也有最大優(yōu)先隊(duì)列和最小優(yōu)先隊(duì)列，其中最大優(yōu)先隊(duì)列采用大頂堆，最小優(yōu)先隊(duì)列采用小頂堆。以下考慮最大優(yōu)先隊(duì)列。
假設(shè)現(xiàn)已建好大頂堆A，且已經(jīng)實(shí)現(xiàn)了調(diào)整堆的函數(shù)heapify(A,n,index)。
下面將C代碼中需要完善的三個(gè)函數(shù)說(shuō)明如下：
(1)heapMaximumA.：返回大頂堆A中的最大元素。
(2)heapExtractMaxA.：去掉并返回大頂堆A的最大元素，將最后一個(gè)元素“提前”到堆頂位置，并將剩余元素調(diào)整成大頂堆。
(3)maxHeapInsert(A,key)：把元素key插入到大頂堆A的最后位置，再將A調(diào)整成大頂堆。
優(yōu)先隊(duì)列采用順序存儲(chǔ)方式，其存儲(chǔ)結(jié)構(gòu)定義如下：
#define PARENT(i)  i/2
typedef struct array{
int *int_array;  //優(yōu)先隊(duì)列的存儲(chǔ)空間首地址
int array_size;  //優(yōu)先隊(duì)列的長(zhǎng)度
int capacity;    //優(yōu)先隊(duì)列存儲(chǔ)空間的容量
} ARRAY;
[C代碼]
函數(shù)heapMaximum
int heapMaximum(ARRAY *A. { return   (1)  ;  }
函數(shù)heapExtractMax
int heapExtractMax(ARRAY *A. {
int max;
max=A-＞int_array[0];
(2)  ;
A-＞array_size --;
heapify(A,A-＞array_size,0);  //將剩余元素調(diào)整成大項(xiàng)堆
return max;
}
函數(shù)maxHeapInsert
int maxHeapInsert(ARRAY *A, int key){
int i, *p;
if (A-＞array_size==A-＞capacity)  {  //存儲(chǔ)空間的容量不夠時(shí)擴(kuò)充空間
P=(int*)realloc(A-＞int_array, A-＞capacity *2 * sizeof(int));
if (!p) return -1;
A-＞int_array=p;
A-＞capacity=2 * A-＞capacity;
}
A-＞array_size ++;
i =   (3)  ;
while (i＞0 ＆＆   (4)  ) {
A-＞int_array[i]=A-＞int_array[PARENT(i)];
i=PARENT(i);
}
(5)  ;
return 0;
}
根據(jù)以上說(shuō)明和C代碼，填充C代碼中的空。
根據(jù)以上C代碼，函數(shù)heapMaximum、heapExtractMax和maxHeapInsert的時(shí)間復(fù)雜度的緊致上界分別為（6）  、（7）  和 （8）(用O符號(hào)表示)。
（9）若將元素10插入到堆A=(15,13,9,5,12,8,7,4,0,6,2,1)中，調(diào)用maxHeapInsert函數(shù)進(jìn)行操作，則新插入的元素在堆A中第      個(gè)位置(從1開(kāi)始)。