trickster0's blog

By trickster0, history, 2 years ago, In English

How tractable is it to implement a min/max heap, such that all the nodes on all levels are sorted say from left to right?

This obviously doesn't need to break the main property of a heap, each parent is the min/max of its children. For instance:

If we make a min heap out of the numbers 1,2,3,4,5

We could get this valid heap: 1 / \ 3 2 / \ / \ 5 6 4

Is it possible to modify the implementation so that we always get something similar to this: 1 / \ 2 3 / \ / \ 4 5 6

And can we keep the complexity of insertion & deletion at O(log n)?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it