Member Avatar for dolfan55aj

I'm trying to do an analysis of buildHeap vs. inserting an array of n values one at a time into a heap. I have a random case, best, and worst case. I was wondering if anyone knows what would actually be in an array to make the best and worst of a min heap?

For example, with n values, what would be in my array to give the slowest possible time to both buildheap and the insert function when creating a heap?

I understand the analysis but I just can't figure out what would give that worst case scenario.

Thanks in advance.

  • 2 Contributors
  • 1 Reply
  • 376 Views
  • 13 Hours Discussion Span
  • Latest Post Latest Post by raptr_dflo
Member Avatar for raptr_dflo

A worst-case situation for buildHeap (having your array pre-filled with values and having to shuffle those values to create a minHeap) is one in which the first value is greater than at least one of the next two, so that a swap is needed there, and then after that, the same holds true for each of the sub-heaps rooted at those children. Plus, once you've (recursively) fixed each child heap, its root now again needs to be exchanged with its parent. My bet is that an array sorted into reverse order (largest element first) is going to represent a huge amount of work to turn into a minHeap.

As far as insertion into a valid minHeap, a new value is presumably added to the end of the array, and then the heap is "re-heap-ified". Again, a worst case scenario is if you keep adding smaller values to your heap, since they will need to be percolated all the way up to the root each time. Is it always the case that once a new value is inserted and percolated part way up the tree-structure, it will never need to move down a different branch? Why? What does this tell us about my argument thus far?

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.