Member Avatar for md_salman

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
  • 152 Views
  • 3 Days Discussion Span
  • Latest Post Latest Post by ITgeneration

Recommended Answers

All 2 Replies

Member Avatar for Rashakil Fol

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.

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.