Datastructur?

Question

'It is said by some people that insertion and deletion operations in Heaps make them less preferable than Binary Search Trees', Give your views about it.

Answer 1

Neither one is absolutely better than the other. The two structures are meant for different purposes. A BST is meant to be a searchable collection. A heap is best used as a priority queue.

Searching a heap takes linear time, but you can find the largest node (or smallest node if you built it that way) in constant time. A self-balancing BST will let you seek out a particular node in logarithmic time, but finding the smallest node doesn't get any faster than logarithmic.

Also, inserting a node takes logarithmic time with both structures. Removing a particular node is slower in a heap, because it takes linear time to find it.

Answer 2

A heap makes the promise that the child node is never larger than the parent, which makes maintaining the node hirearchy processing intensive.

A binary search tree's hirearchy is never more that a binary fork; the left node is always smaller than the right. So maintaining the hirearchy never takes more than a single swap of the sibling branch to correct.

Once the structure is maintained, in either case, both should take about the same amount of time to traverse all nodes for a particular valued node. (With exceptions for a linear predictive search on heaps for values that aren't too non-linear.)

I hope that makes sense.