快速高效搜索的數據結構

我必須將排序的數據存儲在數據結構中。我想要使用的數據結構是堆或二叉搜索樹。但我很困惑哪一個會更好地滿足要求，即快速和高效的搜索。快速高效搜索的數據結構

----更多細節---

我設計從源接收數據（比如數據網格），然後將其保存到數據結構的應用程序。來自數據GRID站的數據是以排序數字的形式出現的。排序後的數據可以按升序或降序排列。

現在我必須搜索數據。這個過程應該是高效和快速的。

可能幫助：http://stackoverflow.com/questions/6147242/heap-vs-binary-search-tree –

我已經檢查過..它是關於以排序的形式存儲數據。我的要求是有效的搜索。在數據結構中搜索某些特定數據時哪一個更好。 – user3297557

都是很好的選擇，使用哪一個很容易實現。如果你正在執行BST，那麼也要查找AVL樹（BST很容易實現，並且比我根據堆使用） –

堆只會讓你快速搜索最小元素（在O（1）時間內找到它，在O（log n）時間內將其刪除）。如果你以另一種方式設計它，它會讓你找到最大限度，但是你沒有得到兩者。要快速搜索任意元素（在O（log n）時間），您需要二叉搜索樹。

2014-02-11 14:22:11

反正數據被排序，以便他可以遍歷列表，即取決於他的執行 –

好的答案。我會補充它，儘管說你可能想看看一個平衡二叉樹，這取決於你對數據的瞭解。也就是說，如果你的數據是有序的，重新平衡將保持樹的效率。 – wmorrison365

欲瞭解更多信息，請參閱Skienna在http://www.algorist.com/或搜索「skiena算法設計手冊pdf」可下載的第一版。 – wmorrison365

讓我潛在的數據結構的列表，我們將闡述：

二叉搜索樹 - 它包含排序數據，從而增加新的元素是昂貴的（O（log n）的，我認爲）。當你搜索它時，你可以使用O（log n）的二進制搜索。 IT節省內存，並且不需要太多額外的內存。
哈希表（http://en.wikipedia.org/wiki/Hash_table） - 每個元素都存儲在一個哈希表中。您可以通過提供哈希來獲取元素。你的元素不需要排序，他們只需要提供散列方法。訪問元素是O（1），我想這是相當不錯的一個:)

我自己通常使用哈希表，但它取決於你確切需要存儲和多久你添加或刪除元素。

所以，在我看來，出堆和二進制搜索列表，使用哈希表。

2014-02-11 14:28:10

一個BST需要O（n）內存，所以大多數其他結構，包括一個哈希表 - 所以我不知道你的意思是「不需要額外的內存」。在哈希表中查找需要O（1）（不是O（n）），但是哈希表不是O數據結構，因此推測不符合OP的要求。 – Dukeling

@Dukeling你是對的，不知道我是怎麼寫這個的:) –

爲了高效搜索，人們肯定會喜歡二叉搜索樹。

要在堆中搜索值可能需要搜索整個樹 - 您無法保證某些值可能不會出現在左側或右側子樹上（除非其中一個子樹已經大於目標值，但這並不保證會發生）。

因此，在一個堆中搜索需要O（n），因爲它需要O（log n）在（self-balancing）二叉搜索樹中。

如果您主要希望查找和/或刪除最小值/最大值以及插入操作，那麼只有堆確實是首選。

如果給出已排序的數據，則可以在O（n）中構造它們。

你提到一個排序的數據結構，但在你的問題「更多細節」我實在不明白，一個排序的數據結構是必需的（它沒有太大的關係是這是在形式你的數據已經在哪裏），但它確實取決於你要做什麼類型的查詢。

如果您只是要搜索確切值，您並不真的需要排序的數據結構，並且可以使用hash table來代替，它支持預期的O（1）查找。

2014-02-11 14:29:16 Dukeling

你可以從O（n）中的任意數據（不一定排序）構造一個堆。 –

@JimMischel真實（並且有用的說明），由於輸入數據已經被排序，它在編寫時似乎是不必要的細節。 – Dukeling

我會去哈希表單獨與AVLTree鏈接（我假設發生碰撞）。它會比O（logn）更好地工作，其中n是項目的數量。在用散列函數獲得索引之後，m個項目將在此索引中，其中m小於或等於n。（它通常小得多，但從不多）。 O（1）用於哈希和O（logm）用於在AVLTree中搜索。這比二進制搜索排序數據要快。

2017-01-08 12:15:48

回答