Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

According to the Wikipedia page, search is "not an operation" on binary heaps (see complexity box at top-right).

Why not? Binary heaps may not be sorted, but they are ordered, and a full graph traversal can find any object in $O(n)$ time, no?

Is the page wrong or am I?

share|cite|improve this question

migrated from cstheory.stackexchange.com Feb 24 '13 at 8:52

This question came from our site for theoretical computer scientists and researchers in related fields.

6  
Pretty sure they just mean that the operation is not supported in any way that utilizes the structure of the heap. You can search it as an array, but that's something you can do on almost every data structure. – Shaull Feb 24 '13 at 7:39
up vote 7 down vote accepted

Actually it depends on your point of view, or level of detail.

The heap, or better priority queue, as abstract data structure usually supports operations like is-empty, add-element, delete-min. And usually not find-element. This is the data structure seen as a specification, fixing the set of operations and their behaviour. The implementation is unknown, it can be a linked tree or array.

The wikipedia page however is concerned with the implementation. That is even clear from the title binary heap. (You understand the binary heap by looking as if it is a tree, you implement it using an array). In this implementation it is easily seen how to program your operation find-element. Technically, that is another abstract data structure (as it has an additional operation aprt from standard heap operations).

In practice heaps (priority queues) are often used for graph algorithms like Dijkstra. There it is important that the priorities stored in the heap can be changed (if we find a shorter route). That is only possible if we are able to find the element in the heap so we can adjust its priority (and reposition the element in the heap). Usually that is done by building another structure on top of the heap so we can efficiently find the positions where elements are stored.

share|cite|improve this answer
1  
1) "you implement it using an array" -- may be a bad idea if the number of stored elements changes a lot. 2) For efficient search, you can use treaps. – Raphael Feb 24 '13 at 16:26
    
@Raphael. Thanks. 1) The nice thing about binary heaps is that their form is 'complete' which makes the waste of space not too bad as with arbirtary trees. But, yes, you usually assume some upperbound in number of nodes. 2) Treaps are nice, but randomized as search tree. When applying heaps with Dijkstra we usually have an array of nodes (in the graphs) and can add to that array the info of where it is in the heap-array. Swapping nodes in the heap-array means also swapping that position as stored in the graph node-array. That means no searching needed. – Hendrik Jan Feb 24 '13 at 16:53

In a binary heap, values are indeed ordered, and a search operation degenerates to a scan of the array if the value/key is >= last value in the array. If however the value you are searching is close to the first (i.e index close to 0), then you will be able to stop early and not scan the array looking for a value that is not there.

For example(C++), an implementation such as this for a Vector that holds the binary heap:

template <class Compare>
uint32_t SearchHeapImpl(const uint32_t idx, const T V, const Compare &cmp) const
{       
    if (slots[idx] == V)
        return idx;
     else if (cmp(slots[idx], V))
         return UINT32_MAX;

     const auto leftChild = 2 * idx + 1;

     if (leftChild >= nElements)
         return UINT32_MAX;

     const auto i = SearchHeapImpl(leftChild, V, cmp);

     if (i != UINT32_MAX)
         return i;

     const auto rightChild = leftChild + 1;

     return rightChild >= nElements ? UINT32_MAX : SearchHeapImpl(rightChild, V, cmp);
}

template<class Compare = std::greater<T>>
uint32_t SearchHeap(const T V, const Compare cmp = Compare()) const
{
    return nElements ? SearchHeapImpl(0, V, cmp) : UINT32_MAX;
}

will abort search early if cmp(slots[idx], V) == true

As others have mentioned, such data structures are suited for O(1) peek, and O(log n) insert and delete operations. A skip list or a self balancing binary tree(e.g red black trees) are usually a better alternative, if you need O(log n) search (you trade O(1) for peek, for O(log n) for search). Of course, they usually more complex, require more memory, and random access patterns may impact performance due to cache hit misses, etc. Win some, lose some.

share|cite|improve this answer
    
Welcome! What you say seems to be correct but the big block of code doesn't add much for our purposes here. If you can, it would be better to express those ideas using pseudocode so that they're accessible to people who don't speak C++. A lot of your code seems to be devoted to error handling and there are lots of little parts that are presumably good practice in C++ but don't help the reader understand the algorithmic concepts you're trying to present (e.g., all those "const auto"s, use of templates, passing a comparison function as an argument, etc.). – David Richerby Jan 6 at 10:59
1  
Thank you David. Apologies for the choice of language. Will keep it in mind for future posts. – markpapadakis Jan 6 at 11:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.