ヒープソートの問題について
分からない問題があります。
どなたかお教え下さい。よろしくお願いします。
Max-Heapify (A,i)
1. L <- 2i
2. R <- 2i+1
3. if L<= heap-size[A] かつ A[L] > A[i]
4. then largest <- L
5. else largest <- i
6. if R<= heap-size[A] かつA[R] > A[largest])
7. then largest <-R
8. if largest !=i
9. then 値の交換A[i] <-> A[largest]
10. Max-Heapify (A,largest)
Build-Max-Heap (A)
1. heap-size[A] <- length[A]
2. for i<- ⌊length[A] /2⌋ downto 1
3 do Max-Heapify (A,i)
Heap-Sort (A)
1. Build-Max-Heap (A)
2. for i<- length[A] downto 2
3 do 値の交換 A[1]<->A[i]
4 heap-size[A] = heap-size [A] – 1
5 Build-Max-Heap (A)
上に示す疑似コードを参考に、以下の問いに答えなさい。ただし、length[A]、heap-size[A]は配列Aの要素数、配列Aに格納されているヒープの要素をそれぞれ示す。
a. ヒープに格納される要素数をnとし、要素の添字の範囲を求めなさい。
b. 配列A=<3,9,8,15,4,2,5,1,7,10>からBuild-Max-Heapによりmax-ヒープを生成したときの結果を示しなさい。
c. 上のHeapsortは、配列を正しくソートするか？しないなら、正しくソートするようにするにはどのように修正すればよいか？理由と共に答えなさい。
d. マージソートと比較してヒープソートの良い点を述べなさい。
お礼
ありがとうございました。 やっぱりロジックで作るんですね^^;