To build a max Heap from Array. implementation. How to dynamically manage size of Array. I am supposed to increae arr size when I use Insert method

Question

To build a max Heap from Array. In implementation part. How to dynamically manage size of Array?. I am supposed to increase arr size when I use Insert method. Tried but it does not return desired heap Array.

I am getting output as => [72] Expecting outPut => [99, 61, 72, 18, 27, 55, 58]

I tried Array.copyof which Returns: a copy of the original array, truncated or padded with zeros to obtain the specified length to do so.

and got result as : [72, 0, 0, 0, 0, 0, 0, 0] - truncated or padded with zeros to obtain the specified length

import java.util.Arrays;

public class Heaps { private int[] heap;

public Heaps() {
    this.heap = new int[1];
}

public int[] getGeap() {
    return this.heap;
}

private int leftChild(int index) {
    return index * 2 + 1;
}

private int rightChild(int index) {
    return index * 2 + 2;
}

private int parent(int index) {
    return (index - 1) / 2;
}

private void swap(int index1, int index2) {
    int temp = heap[index1];
    heap[index1] = heap[index2];
    heap[index2] = temp;
}

public void insert(int value) {
    heap[0] = value;
    int current = heap.length - 1;

    while (current > 0 && heap[current] > heap[parent(current)]) {
        swap(current, parent(current));
        current = parent(current);
    }
}

public static void main(String[] args) {
    int[] A = { 99, 61, 58, 18, 27, 55, 72 };
    Heaps hp = new Heaps();

    for (int i = 0; i < A.length; i++) {
        hp.insert(A[i]);
    }

    System.out.println(Arrays.toString(hp.getGeap()));

}

}

Answer 1

There is ArrayList which does that for you. So I would define the heap field as ArrayList<Integer>, and adapt your code accordingly. If you really need a method that returns an array of primitive ints, then write the conversion in getHeap.

Here is how it could be done:

import java.util.*;

class Heaps {
    private List<Integer> heap;

    public Heaps() {
        this.heap = new ArrayList<Integer>(); // Dynamic array
    }

    public int[] getHeap() {
        // Convert to int[]:
        int[] intHeap = new int[heap.size()];
        for (int i = 0; i < intHeap.length; i++) {
            intHeap[i] = this.heap.get(i);
        }
        return intHeap;
    }

    private int leftChild(int index) {
        return index * 2 + 1;
    }

    private int rightChild(int index) {
        return index * 2 + 2;
    }

    private int parent(int index) {
        return (index - 1) / 2;
    }

    private void swap(int index1, int index2) {
        Collections.swap(heap, index1, index2); // Simple...
    }

    public void insert(int value) {
        heap.add(value); // Now it's easy.
        int current = heap.size() - 1;
        while (current > 0 && heap.get(current) > heap.get(parent(current))) {
            swap(current, parent(current));
            current = parent(current);
        }
    }
}