A.length和A.heap-size有什麼區別？

我有一個關於堆排序的問題。它在一個算法書中表示A.heap-size<= A.length 我不明白這兩者之間的區別。如果一個數組表示一個堆，爲什麼有可能A.heap-size小於A.length。我知道A.heap-size代表堆中元素的數量，爲什麼它不完全等於數組中的元素數量？A.length和A.heap-size有什麼區別？

來源

2013-09-27 monkey doodle

聽起來像你的書的堆排序實現使用數組的第一個「節」作爲堆，而數組的第二個「節」用於排序元素。堆由'A.length'元素開始，但是當你移除最大元素時......堆會縮小。 – rliu

堆排序的不變性是n元素數組的前k個元素是k個最小元素上的堆，最後n-k個元素是排序順序中的n-k個最大元素。後面的元素是爲什麼堆不佔據整個陣列。

來源

2013-09-27 20:52:22

你能更具體嗎？我無法理解這種差異 – caesar

只是爲了擴大答案。進一步閱讀那本書。

A.heap_size數組，是放置堆（max_heap或min_heap）結構元素的地方。它在排序或排隊的範圍內是有意義的。你是對的：這是堆內元素的數量，但它等於A.length僅在堆排序的第一次迭代。

在下一迭代中，用A[i] = A[A.length]（數組A內最後一個元素）交換max_heap樹（A[1]）的根之後，A[1]元件將是A的最後元件，並且A.heap_sort值將由1和max_heap降低結構應爲max_heapified：A[Parent(i)] >= A[i]，其中Parent(i)返回堆樹的i/2。

來源

2013-11-24 18:58:09

-1

從Cormen的算法教科書我使用的：（幫我）