CODEWITHSUNDEEP
data-structuresheapbinary-search-tree
user3297557
user3297557

Reputation: 107

Datastructure for fast and efficient search

I have to store the sorted data in a data structure. The data structure I want to use is heap or binary search tree. But I am confused which one would better serve the requirement i.e. fast and efficient searching.

----MORE DETAILS---

I am designing an application that receive data from a source(say a data grid) and then store it into a data structure. The data that comes from data GRID station is in the form of sorted digits. The sorted data can be in ascending or descending order.

now I have to search the data. and the process should be efficient and fast.

Upvotes: 2

Views: 32439

Answers (4)

Less-Owl-4025
Less-Owl-4025

Reputation: 43

I would go with hash table with separate chaining with an AVLTree (I assume collision occurs). It will work better than O(logn) where n is number of items. After getting the index with hash function, m items will be in this index where m is less than or equal to n. (It is usually much smaller, but never more). O(1) for hashing and O(logm) for searching in AVLTree. This is faster than binary search for sorted data.

Upvotes: 1

Bernhard Barker
Bernhard Barker

Reputation: 55649

For efficient searching, one would definitely prefer a binary search tree.

To search for a value in a heap may require that you search the entire tree - you can't guarantee that some value may not appear on either the left or right subtree (unless one of the children is already greater than the target value, but this isn't guaranteed to happen).

So searching in a heap takes O(n), where-as it takes O(log n) in a (self-balancing) binary search tree.

A heap is only really preferred if you're primarily interested in finding and/or removing the minimum / maximum, along with insertions.

Either can be constructed in O(n) if you're given already-sorted data.

You mentioned a sorted data structure, but in the "more details" in your question I don't really see that a sorted data structure is required (it doesn't matter too much that that's the form in which your data is already in), but it really depends on exactly what type of queries you will do.

If you're only going to search for exact values, you don't really need a sorted data structure, and can use a hash table instead, which supports expected O(1) lookups.

Upvotes: 3

Michał
Michał

Reputation: 2282

Let me make a list of potential data structures and we'll elaborate:

  • Binary search tree - it contains sorted data so adding new elements is costly (O(log n) I think). When you search through it you can use the binary search which is O(log n). IT is memory efficient and it doesn't need much additional memory.
  • Hash table (http://en.wikipedia.org/wiki/Hash_table) - every element is stored with a Hash. You can get element by providing the hash. Your elements don't need to be sortable, they only need to provide hashing method. Accessing elements is O(1) which I suppose is pretty decent one :)

I myself usually use hashtables but it depends on what exactly you need to store and how often you add or delete elements.

Check this also: Advantages of Binary Search Trees over Hash Tables

So in my opinion out of heap and binary search list, use Hash table.

Upvotes: 2

Raman Shah
Raman Shah

Reputation: 497

A heap will only let you search quickly for the minimum element (find it in O(1) time, remove it in O(log n) time). If you design it the other way, it will let you find the maximum, but you don't get both. To search for arbitrary elements quickly (in O(log n) time), you'll want the binary search tree.

Upvotes: 7

Related Questions