[問題] 關於max heap的調整
各位好，不好意思，我是剛接觸C和一些基本演算法數月的新手
來這問些很基本的問題，希望沒違反本板宗旨…
是關於 max heap的調整，我翻了許多本書，將一個由array表示的heap tree 調整為最
大堆積的代碼如下
餵入的資料(Input)：
int data[] ={0,12,17,36,55,63,12,65,89,54};
預期的正確結果(Expected Output)：*[m
data[] : {0,89,63,65,55,17,12,24,36,54};
錯誤結果(Wrong Output)：
data[] : {0,65,17,36,55,63,12,24,89,54};
程式碼(Code)：(請善用置底文網頁, 記得排版)
http://ideone.com/aQmwB
void adjusttoheap(int a[],int root,int n)
{
int temp,parent,child;
temp = a[root];
parent = root;
child = 2*root;
while(child <=n)
{
if(child<n && a[child+1] > a[child])
child++ ;
if(temp > a[child])
break;
else
{
a[parent] = a[child];
parent = child;
child = child*2;
}//else
}//while(child <=n)
a[parent] = temp;
}//adjusttoheap(int a[],int root,int n)
補充說明(Supplement)：
我翻了好幾本書大致都是這樣寫的，但是我還是調不出來…
非常的不懂
1.為何只要樹根的值大於兩個兒子就跳出while呢，那底下的怎麼辦？
2.child = child*2這個動作，不是只會調到左子樹或右子樹嗎，那它的兄弟節點的子樹
不就未被調整？
3.交換後若破壞了前面的平衡為何沒有調整？還是這段code只適用已調整好的heap tree
的刪除動作？那完全尚未調整的二元樹呢？
希望有好心大大能為我解惑，感謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 112.105.149.55
※ 編輯: yakijahn 來自: 112.105.149.55 (01/05 01:39)
→
01/05 01:38, , 1F
01/05 01:38, 1F
→
01/05 01:40, , 2F
01/05 01:40, 2F
→
01/05 01:41, , 3F
01/05 01:41, 3F