Binary Heap using Tree

> The arrays represent a binary tree. Checkout this

> Wiki page:

> http://en.wikipedia.org/wiki/Binary_heap

my homework project states that it's suppose to be a tree-based implementation not array-based, so I took that to mean that I could not use an array. Or is that the only way to do it?

Nic_C78a at 2007-7-12 22:07:53 >

> I thought the *whole* *point* to a binary heap is

> that its tailor-made to use an array/list. Why reject

> that and use a tree structure? It sounds goofy to me.

> I think you may be misreading your homework.

I thought the same thing, that's why I've been making myself crazy trying to find an example. I can't think of any way to do it WITHOUT an array. But this is what the homework says:

The class should use tree-based implementation (not array-based) and the heap should be ascending (not descending).

Nic_C78a at 2007-7-12 22:07:53 >

> Anyone have any idea on how to do this (if it can be

> done)?

Just keep it as a binary tree then. Create a BinaryHeap class that encapsulates a BinaryTree (which you already have). Here's a small start with a little hint:

public class BinaryHeap<V> {

private BinaryTree<V> tree;

private int numElements;

public BinaryHeap() {

tree = new BinaryTree<V>();

numElements = 0;

}

public void add(V value) {

numElements++;

// Insert new value in your binary tree

// Here's a hint:

System.out.print("\n"+value);

int dummy = numElements;

while(dummy > 1) {

System.out.print(" <- "+(dummy%2==0?"left ":"right "));

dummy /= 2;

}

System.out.print(" <- START");

}

/**

* Max-heap:

*

* 9

*/\

*58

*/ \/ \

*34 75

*/ \

* 2?

*

*/

public static void main(String[] args) {

BinaryHeap<Integer> heap = new BinaryHeap<Integer>();

heap.add(9);

heap.add(5);

heap.add(8);

heap.add(3);

heap.add(4);

heap.add(7);

heap.add(5);

heap.add(2);

// heap.add(?)

}

}

Analise the output and see if you can use it to insert the new values properly (according to the heap). When you've done that, only then worry about how to swap nodes in your tree.

; )

Good luck.

prometheuzza at 2007-7-12 22:07:53 >

> Analise the output and see if you can use it to

> insert the new values properly (according to the

> heap). When you've done that, only then worry about

> how to swap nodes in your tree.

> ; )

>

> Good luck.

One question out of curiosity. Could you just trickle up or down after inserting into the tree as you showed above? My assignment doesn't call for that, but I was just curious if that was possible and how hard is it to do that? Wouldn't that be an easier way to maintain the tree? Insert until all data is inserted and then do one "sort" instead of trickling up or down each time you insert data. But I guess the hard part would be finding the last node in the tree so that you could start the sorting?

Nic_C78a at 2007-7-12 22:07:53 >

> > Wouldn't that be an

> > easier way to maintain the tree? Insert until all

> > data is inserted and then do one "sort" instead of

> > trickling up or down each time you insert data.

> But

> I guess the hard part would be finding the last

> node

> in the tree so that you could start the sorting?

>

> More importantly: you need to be able to find the

> next open "slot" in your tree to put the newly added

> value in (that's what's my hint was about).

oh, i see. So you'd have to convert the numElems to a binary string to find the next open "slot",and then use that binary string to find the last node? That does sound more complicated. =)

Nic_C78a at 2007-7-12 22:07:53 >

> Yes, it is more complicated, that's why a array/list

> structure is used for this normally. With such a

> structure, an index of the "next slot" can be quite

> easily calculated.

> You need to insert it into a "real" tree, which takes

> a bit more effort.

> What you could to is push all dummy%2 outcomes

> onto a stack and then pop them all off to find your

> way through your tree. Of course, you can also build

> a String with the outcome and rad it char by char

> from String.length()-1 to 0 as you

> mentioned.

It's me again. My professor actually changed our assignment to an array-based heap(I guess I wasn't the only one having trouble with it). However, he added an extra credit to do exactly what I was asking you about. Do all your inserts at one time, then do one sort. I'm getting a compiling error when trying to insert into the array(toss method). I was wondering if you might be able to tell me what I'm doing wrong. Here's my code:

class Node

{

private int data;

//--

public Node (int k)

{

data = k;

}

//--

public int getK()

{

return data;

}

//--

public void setK(int d)

{

data = d;

}

}//end Node class

//--

public class Htree

{

private Node[] heapArr;

private int mSize;

private int nElems;

private int index;

//--

public Htree(int ms)

{

mSize = ms;

nElems = 0;

heapArr = new Node[mSize];

}

//--

public void toss(int j)

{

nElems++;

Node newNode = new Node(j);

heapArr[nElems] = newNode;

int d = nElems;

while(d >= 1)

{

heapArr[j++] = d % 2;

d = d / 2;

}

}

//--

public void restoreHeap()

{

int parent = (index - 1) / 2;

Node bottom = heapArr[index];

while(index > 0 && heapArr[parent].getK() < bottom.getK())

{

heapArr[index] = heapArr[parent];

index = parent;

parent = (parent - 1) / 2;

}

heapArr[index] = bottom;

System.out.println();

}

}//end Htree class

//--

class HtreeApp

{

public static void main(String[] args)

{

Htree theHtree = new Htree(31);

theHtree.toss(13);

theHtree.toss(1);

theHtree.toss(29);

theHtree.toss(16);

theHtree.toss(5);

theHtree.toss(73);

theHtree.restoreHeap();

}

}

The error is:

Exception in thread "main" java.lang.Error: Unresolved compilation problem:

Type mismatch: cannot convert from int to Node

at Htree.toss(Htree.java:57)

at HtreeApp.main(Htree.java:88)

Any ideas? Thanks!

Nic_C78a at 2007-7-12 22:07:53 >

> > ...

> > Any ideas? Thanks!

>

> It's because of this line (in your Htree

> class):

> heapArr[j++] = d % 2;

>

> The statement d % 2returns an int, but

> heapArr is an array of Node objects, not

> int's.

Thanks I fixed it. I'm getting a new error in my display. Here's my display code:

public void displayH()

{

System.out.print("heapArr: ");

for(int m=0; m < nElems; m++)

if(heapArr[m] != null)

System.out.print( heapArr[m].getK() + " ");

else

System.out.print("--");

System.out.println();

int nBlanks = 32;

int itemsPerRow = 1;

int column = 0;

int j = 0;

String dots = "................................";

System.out.println(dots+dots);

while(nElems > 0)

{

if(column == 0)

for(int k=0; k<nBlanks; k++)

System.out.print(' ');

System.out.print(heapArr[j].getK());

if(++j == nElems)

break;

if(++column==itemsPerRow)

{

nBlanks /= 2;

itemsPerRow *= 2;

column = 0;

System.out.println();

}

else

for(int k=0; k><nBlanks*2-2; k++)

System.out.println();

}

System.out.println("\n"+dots+dots);

}

The error message is pointing to

System.out.print(heapArr[j].getK());

stating this error:

Exception in thread "main" java.lang.NullPointerException

at Htree.displayH(Htree.java:72)

at HtreeApp.main(Htree.java:144)

I can't find where I messed up. I know I'm probably making you crazy, but this will hopefully be the last time I bug you.>

Nic_C78a at 2007-7-12 22:07:53 >