when building maxHeap/minHeap using top-down or bottom-up approach ,will the values in the array be-CodePudding

I created an Max Heap using Top down approach with o(nlogn) time complexity.All the result of all the array values are following max heap norms and if i do the max heap with bottom up approach with o(n) time,the result is also following max heap norms ,but the array results of both top down approach and bottom up approach are not same.is it correct if both approach results are not same but still satisfy max heap rules?

is it correct if both approach results are not same but still satisfy max heap rules?

CodePudding user response：

Yes, they might look different, and this is not a problem at all.

The heap job is to give you the min/max element fast (in O(log(n))).

Although the trees of bottom-up and top-down constructions might look different, the root will always be the same.

When you ask the heap to give you the max/min element, it always gives you the first one (and that's why it is also called priority queue) and then the tree is reorganized by taking the last element of the heap and placing it in the spot of the root and then moving it down following the priority rule by comparing it with the current left and right children.

The key point is to notice that even if the trees look different, the result of N consecutive removals will always be the same.

CodePudding user response：

Yes, there are multiple possible arrangements of items to create a valid binary heap. Consider these two min heaps, each with three items:

  1           1
2   3       3   2

In both cases, the smallest item is at the root. The heap rules don't specify the order of children, just that the each child must be greater than or equal to the root. So both are valid heaps.

When building a binary heap using Floyd's algorithm (the "bottom up" approach), the heap that results depends largely on the initial order of the input array. When building a heap by repeated insertion (the "top down" approach), the resulting heap depends very much on insertion order.

The actual order of the final heap also depends on some implementation details.

CodePudding user response：

Yes, it is normal situation. Same elements might be organized in distinct heaps, preserving heap property

For example, you can use the only top-down approach, but put the same elements set in different order - results might differ.