資料結構›Ch7 搜尋與排序第 2 題／共 76 題
2. Heap、Heapify
#DS-07-002易HeapHeapify
Consider an array . What does the array look like after BUILD-MAX-HEAP (bottom-up heapify) is performed, a process that converts the array into a max-heap by adjusting subtrees starting from the bottom non-leaf nodes and working up to the root?
參考答案與解析
答案 (A)：從最後一個非葉節點（index 2，值1）開始往前 sift-down：[4,5,1,10,2,7]→處理 index2(值1)，與子節點7比較，交換→[4,5,7,10,2,1]；處理 index1(值5)，與子節點10比較，交換→[4,10,7,5,2,1]；處理 index0(值4)，與較大子節點10交換→[10,4,7,5,2,1]，繼續下沉，4與5比較交換→[10,5,7,4,2,1]。最終結果為 [10,5,7,4,2,1]。
📄 台大115
▤完整推導請見《WH 資工筆記 · 資料結構》Ch7 搜尋與排序