當我們將它稱爲二進制堆樹時，它是什麼意思抽象類型？

我讀了一個術語抽象類型，這意味着你可以使用結構或骨架。我正在談論二進制堆樹。我認爲它是一種抽象類型，但當問題出現時，合併兩個最小堆以創建最大堆的時間複雜度是多少？我得到了一些答案，說複製樹中的元素到數組中，並使用構建堆方法n在O（n）時間創建最大堆！但是如果你不能遍歷樹作爲抽象類型，你將如何在const時間/或O（n）時間複製min堆的元素。剩下的唯一一件事就是逐個刪除所有元素。n將它保存在數組中。這將花費O（nlogn）時間。任何人都可以花些時間讓我明白這個疑問嗎？當我們將它稱爲二進制堆樹時，它是什麼意思抽象類型？

謝謝

來源

2015-09-18 Bishnu

我認爲你是一個抽象數據類型的實現與其接口混淆。

要實現一個堆（或隊列等），你可以做任何你想用它的內部結構。請注意，堆的內部結構可以是任何東西（數組，列表...）;事實上，堆的內部結構對用戶是隱藏的（但同樣：開發人員可以看到它）。

的實施堆將提供其定義他的抽象類型只有它的接口方法。

當人們談論合併兩個堆，他們所談論的也實現了合併功能的堆。在合併函數內（在堆的實現中），可以使用內部實現的所有功能。

來源

2015-09-18 11:13:33

雅...我得到它只會提供其接口。但是通過那個接口你可以遍歷它嗎？採取一種情況：從最小的堆中獲得第二分鐘？我希望你會回答它刪除根，heapify，得到根，這就是你的第二分鐘，對吧？（＆將需要O（logn）時間）爲什麼我會刪除根目錄，如果我可以遍歷樹，即第二分鐘肯定會在根級別旁邊。（這裏我只需要2比較，即左n的根權利，小於O（logn）時間同意??）如果我錯了，請你糾正我嗎？ – Bishnu

「遍歷」不是可用的接口操作。 –

當我們將它稱爲二進制堆樹時，它是什麼意思抽象類型？

回答

相關問題