Vector based heap in java

Thread view:

Basanta - 16 Mar 2008 18:53 GMT

Can anyone help me to complete my following program??

import java.util.vector;

class Heap{
Vector data;
void insert(Object obj) {
int loc=data.size();
data.addatLastLoc(obj);

while(loc != 0){
int parent = floor((loc-1)/2);
Object par = data.getIthElement(parent);
if(par.compareTo(obj)<=0) break;

Object temp = par;
data.replaceIthElement(parent,obj);
data.replaceIthElement(loc,temp);
loc = parent;
obj= data.getIthElement(loc);
}

Object removeMin(){
int loc = data.size()-1;
swap(root && loc objects)
int curr =0;
int leftchild=curr*2+1;
int rightchild = curr*2+2;

Reply to this Message

Andrea Francia - 16 Mar 2008 19:38 GMT

> Can anyone help me to complete my following program??

Uhm... what it is supposed to do?

Signature

Andrea Francia
http://www.andreafrancia.it/

Reply to this Message

rossum - 16 Mar 2008 23:01 GMT

>Can anyone help me to complete my following program??
>
>import java.util.vector;

Vector is synchronized, and hence can be slow. If you do not require
synchronization then you might want to try using a ArrayList instead.

>class Heap{
> Vector data;

Better to make your internal data private.

> void insert(Object obj) {

You might want to make this method public so it can be accessed from
outside this class/package.

> int loc=data.size();
> data.addatLastLoc(obj);

In the Java standard, this would be "addAtLast". Better to check that
you have not mistyped something.

> while(loc != 0){

Your indentation is wrong here, this is bad style (or possibly an
artefact of posting on usenet).

> int parent = floor((loc-1)/2);
> Object par = data.getIthElement(parent);
[quoted text clipped - 8 lines]
>
>Object removeMin(){

Again, the method should probably be public and should be indented
correctly.

> int loc = data.size()-1;
> swap(root && loc objects)
> int curr =0;
> int leftchild=curr*2+1;
> int rightchild = curr*2+2;

You need to return some Object here and close your method:
return Xxx;
}

You need to close your Heap class here:
}

rossum

Reply to this Message

Lew - 17 Mar 2008 02:11 GMT

> Can anyone help me to complete my following program??
>
> import java.util.vector;

There is no such class.

> class Heap{
> Vector data;

A better choice is java.util.ArrayList. Or even better,

Also, please narrow your indentation to a maximum of four spaces per level,
for readability on Usenet.

> void insert(Object obj) {
> int loc=data.size();
> data.addatLastLoc(obj);

Wouldn't it be simpler and safer simply to invoke 'data.add( obj )'?

> while(loc != 0){
> int parent = floor((loc-1)/2);

Surely this doesn't compile? Did you even try to compile this?

As it happens, integer arithmetic truncates division anyway, so you don't need
this fantasy 'floor()' method.

> Object par = data.getIthElement(parent);
> if(par.compareTo(obj)<=0) break;
[quoted text clipped - 5 lines]
> obj= data.getIthElement(loc);
> }

> Object removeMin(){
> int loc = data.size()-1;
> swap(root && loc objects)
> int curr =0;
> int leftchild=curr*2+1;
> int rightchild = curr*2+2;

Also, consider using
<http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html>

For the rest of the algorithm I find
<http://en.wikipedia.org/wiki/Heap_%28data_structure%29>
a good starting point.

Signature

Lew

Reply to this Message

Roedy Green - 17 Mar 2008 06:27 GMT

On Sun, 16 Mar 2008 10:53:33 -0700 (PDT), Basanta
<mainhoonanjaane@gmail.com> wrote, quoted or indirectly quoted someone
who said :

>Can anyone help me to complete my following program??

To do that, you would have to divulge what you want it to do.
Hint, comments would help.

Signature

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

Reply to this Message

Vector based heap in java

Free Magazines