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)?
If there was a heap which keeps the sorted order and still be $$$O(\log n)$$$, its operation and functionality would be quite identical to that of a BBST. So while I do not explicitly mean that this is impossible, I see no reason to choose this path over using a BBST.