Take the 2-minute tour ×
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.

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|improve this question
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
add comment

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.

1 Answer

up vote 4 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|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
add comment

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.