構建具有特定需求的數據結構

我需要構建一個僅使用O（n）位存儲的數據結構。插入，刪除和最大時間的最差時間需要爲O（log n），但對於包含而言它需要爲O（1）。我一直試圖使用只有1和0的二進制堆（以滿足存儲的O（n）位），但我似乎無法獲得最大值和包含函數（關於它們的最壞時間複雜度看起來如何）。任何人都可以給我一個關於我要去哪裏的線索嗎？謝謝。構建具有特定需求的數據結構

來源

2016-01-27 Daniel Cook

二元堆你不能實現'O（1）'查找時間 – user8

如何使用只有1和0的數組？ –

如果他們堆在一起，是的。令top爲max（1），如果left爲0（在A [1]處），則它包含1,0。類似於最小。一般來說，你只需要'A [0] == A [1]'來檢查。但對我來說，僅僅分類1和0就沒什麼意義了。 – user8

有兩個工作串聯的數據結構：平衡BST（如AVL樹）和哈希表。插入一個元素需要O（log（n））時間用於BST，O（1）時間用於散列表，所以O（log（n））時間的總和。刪除需要O（log（n））時間BST，O（1）時間散列表。最大值爲BST的O（log（n））時間，並且一旦知道哪個元素是最大值，則需要O（1）時間來計算哈希表。包含需要O（1）時間的散列表（之後，由於它們包含相同的元素，因此不需要檢查BST）。實際上實現它會很困難，因爲你需要在BST元素和哈希表中保留指針，但是這種結構可以達到所需的規範。

來源

2016-01-29 21:12:29 ghui

構建具有特定需求的數據結構

回答

相關問題