軟件設計師案例分析當天每日一練試題地址：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4

往期軟件設計師每日一練試題匯總：m.xiexiliangjiufa.com/class/27/e4_1.html

軟件設計師案例分析每日一練試題（2022/2/23）在線測試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2022/2/23

點擊查看：更多軟件設計師習題與指導

軟件設計師案例分析每日一練試題內(nèi)容（2022/2/23）

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

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

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