0

although this question is basically related to a data structure, still I think that a good progrmmer should be able to answer it. My question is that "is it possible to determine the order in which some ( numbers or characters etc ) are arrived for insertion into a min or max heap ( if we are given that heap )." I think that its answer is yes as there can be so many combinations that we can describe in this regard, but my tutor says that it is not possible, I will be very thank ful for any serious reply.

3
Contributors
2
Replies
3
Views
11 Years
Discussion Span
Last Post by ITgeneration
0

although this question is basically related to a data structure, still I think that a good progrmmer should be able to answer it. My question is that "is it possible to determine the order in which some ( numbers or characters etc ) are arrived for insertion into a min or max heap ( if we are given that heap )." I think that its answer is yes as there can be so many combinations that we can describe in this regard, but my tutor says that it is not possible, I will be very thank ful for any serious reply.

If only insertion has happened, you are correct in that there are a non-zero number of combinations in this regard.

For example, suppose your min-heap has three elements, looking like

X
 / \
Y   Z

where X < Y < Z. Suppose your insertion algorithm fills the bottom row from left-to-right. It's either that or right-to-left. First I'll assume that you made only three insertions with no deletions.

There are six possible orders of input: X Y Z, X Z Y, Y X Z, Y Z X, Z Y X, Z X Y. Whenever Z comes before Y, the following heap results.

X
 / \
Z   Y

Therefore, if you have the heap

X
 / \
Y   Z

and X < Y < Z, then you know that Y was inserted before Z was. Generally speaking, I think you can only derive the order of insertion when comparing two leaf nodes (and probably only with two adjacent leaf nodes), but I do not know for sure.

If the heap has undergone insertion along with removal of the minimum element, then you cannot know anything about the ordering in which two particular elements were inserted.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.