Re: Sorted heap trees

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.

A sorted heap tree is a heap tree with the further requirement
that left and right subtrees are partitions.  That is, all of the

elements of the left subtree are less than the elements of the
right subtree.  For example, here is a sorted heap tree in
outline form.

T: 1
  L: 2
    L: 3
      L: 4
      R: 5
    R: 6
      L: 7
      R: 8
  R: 9
    L: 10
      L: 11
      R: 12
    R: 13
      L: 14
      R: 15

This is a sorted tree, albeit not a BST.  The recursive traversal

routine is

        procedure traverse node
                print node.data
                traverse node.left
                traverse node.right

There are four types of sorted heap trees, because we can
exchange left and right, and the direction of ordering.

Searches are necessarily asymetric.  That is, in this tree we
first compare with the right child and then with the left.

Sorted heap trees are analogous with binary search trees - for
every type of BST, e.g., splay trees, AVL trees, etc, there are
corresponding sorted heap trees.

It turns out that there are some special situations where a
sorted heap tree is better than an ordinary BST.  I am wondering
if anyone knows the proper name for these type of trees and of
any references, e.g., properties, uses, adaptations of standard
algorithms for them.

I am also really wondering what the right newsgroup for this kind

of query might be.  There doesn't seem to a newsgroup devoted to
algorithms and data structures as such.

Richard Harter, c...@xxxxxxxxxxxx://home.tiac.net/~cri,http://www.varinoma..com
Save the Earth now!!
It's the only planet with chocolate.

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 looks like this may be related I do not have access to the text:

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


Gene

.

Relevant Pages

  • Sorted heap trees
    ... I'm looking at a data structure that I have invented that I ... A sorted heap tree is a heap tree with the further requirement ... albeit not a BST. ... procedure traverse node ...
    (comp.programming)
  • Sorted heap trees
    ... I'm looking at a data structure that I have invented that I ... A sorted heap tree is a heap tree with the further requirement ... albeit not a BST. ... procedure traverse node ...
    (sci.math.research)