How is this function being made use of?

Question

Hello all,

I am just studying a few classes given to me by my lecturer and I can't understand how the function heapRebuild is being made used of! It doesn't change any global variables and it doesn't print out anything ad it doesn't return anything - so should this even work? It shouldn't, should it?

If you were told to make use of heapRebuild to make a new function removeMac would you edit heapRebuild?

public class MaxHeap<T extends Comparable<T>> implements Heap<T>{
private T[] heap;
private int lastIndex;

public T removeMax(){
        T rootItem = heap[0];
        heap[0] = heap[lastIndex-1];
        lastIndex--;
        heapRebuild(heap, 0, lastIndex);
        return rootItem;
}

protected void heapRebuild(T[ ] items, int root, int size){

        int child = 2*root+1;
        if( child < size){
            int rightChild = child+1;
            if ((rightChild < size) &&
                    (items[rightChild].compareTo(items[child]) > 0)){
                child = rightChild;
            }
            if (items[root].compareTo(items[child]) < 0){
                T temp = items[root];
                items[root] = items[child];
                items[child] = temp;
                heapRebuild(items, child, size);}
        }
    }

}

Answer 1

Java is a pass-reference-by-value OO language. The methods can change the passed-in mutable values.

Simplified example:

import java.util.Arrays;

public class Test {

    public static void main(String... args) {
        String[] strings = new String[] { "foo", "bar" };
        System.out.println(Arrays.toString(strings)); // [foo, bar]
        changeValue(strings);
        System.out.println(Arrays.toString(strings)); // [foo, foo]
    }

    public static void changeValue(String[] strings) {
        strings[1] = "foo";
    }

}

Answer 2

Who said it is not doing anything. It modifies the value that is passed which is T[] items.

Answer 3

T temp = items[root];
items[root] = items[child];
items[child] = temp;

These lines swap two entries in items, the ones at index root and index child. Each invocation of heapRebuild() works with the same items array, not copies of the array, so these changes are indeed seen by the caller.

Answer 4

It modifies the items array.

When you pass an object to a function in Java, it doesn't make a separate copy of the object.

Therefore, when your heapRebuild function modifies the items array, it modifies the original array that was passed to it.

Note that Java does not pass references to variables, so that if the function wrote items = whatever, the caller's array will still refer to the old array instance.

Answer 5

The method is modifying the passed in array. In java this is passed in by reference. More details here.

Answer 6

The method changes the order of the contents of its T[ ] items parameter. in Java, method parameters of a reference type (including arrays) are passed by copying the value of the reference. The method can make any changes allowed by the objects those references refer to.