Member Avatar for chunalt787

I am currently learning about heaps and specifically their relevance to priority queues. I don't seem to understand a couple concepts and was hoping someone could clear these up.

First of all I don't understand the remove function. I get that it replaces the root with the last external node then bubbles down however it appears to me that for each removal it would take O(n) time. This seems a little inefficient when it is assumed that there will be many removals. Is there no better way to do it?

Secondly how would one go about finding a specific element inside the heap or even a specific key for that matter. Once you move beyond looking for the smallest key it seems like you would have to traverse the entire tree until you found the element or key you were looking for. Am I right on that assumption or am I missing something?

On a similar note I have a homework question "Show that the problem of finding the kth smallest element in a heap takes at least Big-Omega(k) time in the worst case." I'm not asking for someone to do my homework but any help on understanding the searching algorithm that would help me answer that question would be great.

Thanks

  • 2 Contributors
  • 1 Reply
  • 85 Views
  • 16 Hours Discussion Span
  • Latest Post Latest Post by shrughes
Member Avatar for shrughes

Bubbling down doesn't take O(n) time, where n is the number of nodes in the heap. Think again.

If you want to find a specific element in the heap, you have to traverse the tree.

For finding the k'th smallest element in O(k) time, I don't know off the top of my head. Finding it in k log n time is easy, finding it in k log k time is slightly less easy.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.