From: ··········@gmail.com
Subject: How to implement heap as a binary tree in lisp?
Date: 
Message-ID: <1190918064.184973.87480@y42g2000hsy.googlegroups.com>
I am trying to implement heap in CLisp. I have already done it in a
linear data strcuture with no left / right pointers. But now I want to
use a nested list format which contains (el () ()) at the highst
level.
The problem I am facing with is how to define a recursive case for
insertion. Heap requires the tree to be complete.

I approach the issue as follows:

1. I will take a heap and an element
2. I will add the element in the last node keeping it a complete tree
3. I wil swap the child with parent if it is greater than the parent

But I am stuck at the second step i.e. how to add an element without
making the tree incomplete? KIndly help me on this!!!!!!!
From: ············@gmail.com
Subject: Re: How to implement heap as a binary tree in lisp?
Date: 
Message-ID: <1190927357.823666.174740@22g2000hsm.googlegroups.com>
On Sep 27, 1:34 pm, ··········@gmail.com wrote:
> I am trying to implement heap in CLisp. I have already done it in a
> linear data strcuture with no left / right pointers. But now I want to
> use a nested list format which contains (el () ()) at the highst
> level.
> The problem I am facing with is how to define a recursive case for
> insertion. Heap requires the tree to be complete.
>
> I approach the issue as follows:
>
> 1. I will take a heap and an element
> 2. I will add the element in the last node keeping it a complete tree
> 3. I wil swap the child with parent if it is greater than the parent
>
> But I am stuck at the second step i.e. how to add an element without
> making the tree incomplete? KIndly help me on this!!!!!!!

Keep a weight slot in each node.  Then you can calculate which
direction to go based on weight.  For example
(dir 1) -> :left
(dir 2) -> :right
write out (dir 3, 4, 5, 6, 7) and you'll see the pattern.  Then be
sure to update weight on insertion or deletion.

Andrew
From: ··········@gmail.com
Subject: Re: How to implement heap as a binary tree in lisp?
Date: 
Message-ID: <1190939317.663172.67550@n39g2000hsh.googlegroups.com>
On Sep 27, 5:09 pm, ·············@gmail.com" <············@gmail.com>
wrote:

> Keep a weight slot in each node.  Then you can calculate which
> direction to go based on weight.  For example
> (dir 1) -> :left
> (dir 2) -> :right
> write out (dir 3, 4, 5, 6, 7) and you'll see the pattern.  Then be
> sure to update weight on insertion or deletion.
>
> Andrew

By weight do you mean the depth/height of each node? Could you please
elaborate it a bit.
Thanks
From: ············@gmail.com
Subject: Re: How to implement heap as a binary tree in lisp?
Date: 
Message-ID: <1190990864.739776.76170@o80g2000hse.googlegroups.com>
> By weight do you mean the depth/height of each node? Could you please
> elaborate it a bit.
> Thanks

I mean the number elements in the sub-tree rooted at each node.

(defstruct heap-node
  item
  weight
  left
  right)

I'm sorry I'm at work and don't have time to expand.  Check out
http://common-lisp.net/project/funds/
comp.lang.lisp / 2007 / sep