我需要實現一個支持插入刪除的數據結構和 O（日誌（n））的搜索的O提取的特殊對象（1）。 我的數據結構需要保存按其ID排序的車輛，並且每輛車都有一個表示直到下一次維修的時間的字段。 我需要在O（1）中提取需要服務的車輛。 歡迎您提出任何建議。如何創建與運行時間限制的數據結構
予理解的是，我需要兩個單獨的數據結構和I想到具有1組和1個優先級隊列都由其他參數排序但保持相同的指針的副本。我遇到的問題是，當我試圖從「set」結構中刪除時，我在其他數據結構（優先級隊列）上留下垃圾。
哈希表將支持插入，刪除，和更好的搜索比O（日誌（N））。這是假設你在增長表格時從不需要重新散列所有內容。困難的部分是在O（1）時間定位「下一個」車輛。
根據具體實施情況，min heap會在O（1）和O（log（n））（攤銷）之間插入，並且找到最小項目爲O（1）。從堆中刪除項是O（log（n））操作，但找到堆中的任意項大於O（log（n））。
是我實現這一點，我會使用兩個單獨的數據結構：哈希表和最小堆。理由是哈希表提供非常快的插入，刪除和查找，並且堆提供基於服務時間的排序。唯一不符合您的起始要求的地方是刪除車輛，因爲這需要在堆中搜索任意物品。
事實上，雖然可能很麻煩，但將兩個數據結構合併在一起，以便您的哈希表存儲堆節點對象（對實際數據有引用）而非實際數據對象。只要堆節點知道它在堆中的位置（即具有父指針以及左和右子指針），那麼可以使用散列表來查找節點並從堆中移除該節點。
首先感謝您的回答 我瞭解，我需要兩個不同的數據結構，我想大約有1套和1個優先級隊列都被其他參數進行排序，但持有相同指針的副本。我遇到的問題是，當我試圖從「set」結構中刪除我留在其他數據結構（優先級隊列）上的垃圾時 – 2010-09-13 18:43:31
如果我要實現組合數據結構，我會創建優先級隊列實現並確保我可以刪除任意節點。然後，添加存儲節點的散列表功能，按鍵索引。無論何時您想通過鍵刪除某些內容，請在散列表中查找它，獲取節點指針，然後將其從優先級隊列中刪除，然後將其從哈希表中刪除。 – 2010-09-13 18:57:15
你將如何實現它，這樣你就可以在優先級隊列中刪除O（log（n）），同時指向需要刪除的數據 – 2010-09-13 19:27:25
是否有這個作業相關的任何機會？ – 2010-09-13 18:15:19
家庭作業看起來很可能 – 2010-09-13 18:16:07
你如何確定下一輛車是否需要照顧？ – 2010-09-13 18:22:56