Re: Sorted heap trees

On Mar 27, 8:32 pm, Gene <gene.ress...@xxxxxxxxx> wrote:
On Mar 27, 6:32 pm, c...@xxxxxxxx (Richard Harter) wrote:



This is a repost to comp.programming only.

I'm looking at a data structure that I have (re)invented that I
am calling a sorted heap tree. I dare say there is an official
name but I haven't a clue as to what it might be. What I am
looking for are references, preferably on-line, and anything
useful I can snarf up.
[snip]


This sounds like a cool data structure for discrete event simulation
where you usually want to remove the smallest element but now and then
need to inspect all events up to a certain epoch. This is pretty
common. If you decide to publish code, please let us know. Can you
maintain the heap property of this beast and keep it balanced in log n
per operation?

It seems pretty straightforward. When the deleting the root we just
push the right links down until we hit a node with an empty right
link.
These trees have the convenient property that if there is only one
child
link it can be either a left or right link. The amortized cost of
inserts is log n. You can force balancing by checking the depth
required
for an insert. If it is excessive you can move the upper part of the
subtree from one side to another.

This suggests that appropriate balancing algorithms are probably less
like
those used in BST's than I would have supposed.



It looks like this may be related I do not have access to the text:

http://www.springerlink.com/content/x6076732011t7641/

Gene


.