Re: How to implement heap as a binary tree in lisp?

On Sep 27, 1:34 pm, riahasa...@xxxxxxxxx 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

.

Relevant Pages

  • Re: iterative binary tree traversal
    ... > If the tree has links to the parent, ... A stack isn't strictly necessary, ... into a heap; the heap lets you backtrack to scan down branches you ...
    (comp.programming)
  • How to implement heap as a binary tree in lisp?
    ... I am trying to implement heap in CLisp. ... linear data strcuture with no left / right pointers. ... Heap requires the tree to be complete. ... I wil swap the child with parent if it is greater than the parent ...
    (comp.lang.lisp)
  • Re: A C implementation of Binary Heap
    ... (Nor can any heap with more than 2 distinct ... less as compared to its parent and root node has the largest value. ... some heaps it's comparing more than. ... that 1-3-2 tree is a Binary Tree. ...
    (comp.lang.c)
  • [SUMMARY] Drawing Trees (#40)
    ... Did you spot the errors in my Heap class? ... It may be interesting to note that this quiz grew out of an actual problem I was ... then initializes a String to hold the result and a root node for the tree. ...
    (comp.lang.ruby)
  • RE: Add Child Node to Treeview
    ... thinking yesterday afternoon that perhaps one way to get a unique strKey is ... into the!Parent section. ... 'Fill Tree ... qryFamTree has my main table joined to a second table by WhoID. ...
    (microsoft.public.access.formscoding)