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?

  • 7
    $\begingroup$ 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. $\endgroup$ – Shaull Feb 24 '13 at 7:39

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.

| cite | improve this answer | |
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Feb 24 '13 at 16:26
  • $\begingroup$ @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. $\endgroup$ – Hendrik Jan Feb 24 '13 at 16:53
  • $\begingroup$ (+1)The implementation is unknown, it can be a linked tree or array. $\endgroup$ – Bit_hcAlgorithm Jan 4 '19 at 7:31
  • $\begingroup$ A heap is not the same thing as a priority queue. A heap is a data structure; which defines how data will be stored. A priority queue defines an abstract datatype - essentially an interface. As such; a heap can be used for many abstract datatypes; and abstract datatypes can use any data structure. Trying to equate one of them to be a heap is a bit like saying "headphones are bose". $\endgroup$ – UKMonkey Apr 13 at 9:59

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.

| cite | improve this answer | |
  • 2
    $\begingroup$ 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.). $\endgroup$ – David Richerby Jan 6 '16 at 10:59
  • 1
    $\begingroup$ Thank you David. Apologies for the choice of language. Will keep it in mind for future posts. $\endgroup$ – markpapadakis Jan 6 '16 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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