使用鏈接列表的二進制堆的複雜性

Question

我想比較使用數組和鏈接列表實現二進制堆。 我認爲數組在各方面都更好，因爲所有的操作都可以比使用鏈表的操作更快或者更快。它也需要更少的內存。

但是，有沒有什麼原因，爲什麼使用鏈接列表比二元堆陣列好？

Answer 1

二進制堆很少表示爲顯式樹。它們比陣列版本使用更多的內存，參考位置較差，（如您在前面的問題中提到的）難以實現。

將二進制堆作爲樹研究的馬林理由是建立數據結構的直覺。僅僅給出二進制堆的屬性和正確性是相當困難的，只要將它們連接回二叉樹表示，就可以更容易地設計和證明二進制堆上的算法的正確性。

希望這會有所幫助！