是有具有以下屬性的數據結構：

給定的n個元素，該數據結構具有以下運行時的複雜性：是有具有以下屬性的數據結構：

尋找最小元素Θ（1），
刪除最小元素是Θ（LGÑ ）

插入一個元件是Θ（LG n）的

我發研究，我不知道這個快速的數據結構

來源

2013-10-07 ERJAN

最小堆可能？我想到的第一件事。 – Justin

也許樹實現符號表，但不知道 –

這聽起來像一個堆，但我可能失去了一些東西，因爲你會很容易發現它 – harold

從維基百科： http://en.wikipedia.org/wiki/Heap_(data_structure)

Operation  Binary  Binomial Fibonacci 
find-min  Θ(1)  Θ(1)  Θ(1) 
delete-min  Θ(log n) Θ(log n) O(log n)* 
insert   Θ(log n) O(log n) Θ(1) 
decrease-key Θ(log n) Θ(log n) Θ(1)* 
merge   Θ(n)  O(log n)** Θ(1) 
(*) Amortized time 
(**) Where n is the size of the larger heap

來源

2013-10-07 22:26:55 Justin

現在這是明確的，我讀了一篇文章，它只是描述了操作何苦簡單！ – ERJAN

是有具有以下屬性的數據結構：

回答

相關問題