CODEWITHSUNDEEP
javaalgorithmarrays
user466534
user466534

Reputation:

Looking for help with implementation of a heap data structure

I have an operation on a heap, a fixdown operation . This is the code:

public class Heap {

    public static void fixdown (int a[],int k,int n) {
        while (2*k<=n) {
            int j=2*k;
            if (j<n && a[j]<a[j+1]) j++;
            if (!(a[k]<a[j])) break;
            swap(a,k,j);
            k=j; 
        }
    }

    public  static void main (String[]args) {
        int a[]=new int[]{12,15,20,29,23,22,17,40,26,35,19,51};
        fixdown(a,1,a.length);
        for (int i=0;i<a.length;i++) {
            System.out.println(a[i]);
        }
    }

    public static void swap (int a[],int i,int j) {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}

Update: I have changed it and now there is no error.

//result is 

12
29
20
40
23
22
17
15
26
35
19
51

Upvotes: 0

Views: 305

Answers (4)

Maciej Hehl
Maciej Hehl

Reputation: 7995

Those lines:

for (int i=0;i<a.length;i++){
 System.out.println(a[i]);

suggest, that indexes in Your array are 0 based. If so, the indexes of the left and right child of the element at index i should be calculated as

leftchild_index = 2*i+1;
rightchild_index = 2*i+2; // rightchild_index = leftchild_index + 1

left child of a[0] is a[1] and the right one is a[2]

If parameter n is the length of an array containing the heap, You need to fix some conditions

while(2*k<=n){

should be changed to:

while(2*k + 1 < n){

and 

int j=2*k;
    if (j<n && a[j]<a[j+1])   j++;

should be changed to 

int j = 2 * k + 1;
    if (j < n - 1 && a[j] < a[j+1])   j++;

Otherwise You are accessing the array out of bounds.

Upvotes: 0

user168715
user168715

Reputation: 5579

The code is very hard to read in its current state of indentation, but I believe a[j]=k; should be a[j]=t;.

Upvotes: 0

corsiKa
corsiKa

Reputation: 82589

you have a[j]=k;

perhaps it should be a[j]=t;

Upvotes: 1

polygenelubricants
polygenelubricants

Reputation: 384006

a[j]=k;

You probably want:

a[j]=t;

On array declarations

Please, please, do not make a habit of declaring arrays like this:

int x[];

You should instead put the brackets with the type, rather than with the identifier:

int[] x;

Related questions

Upvotes: 1

Related Questions