Java min heap decrease array size after removing element

Question

I am creating a priority queue (my own in array form) with a minimum heap sort where I am implementing a method which deletes the first element in the priority queue (my array) which is the root. I then call the heapifyNumbers() method on my array again to sort the array in minimum heap again. The problem is just that I cannot decrease from an array, so the last two elements will be duplicate.

This is the delete method I am creating

public void deleteMinimum(int[] array){
    array[0] = array[array.length - 1];
    heapSort(array);
    //here I want to decrease array size by 1 after heap sorting the array
}

Here I just replace the first index with the last index, and then call the heapifyNumbers() method on my array again to sort the array. How do I decrease the array size by 1? I know arrays cannot be decreased, but I see all implementations of this using arrays so there must be some way like creating a new array maybe?

This is my output:

Before Heap Sort :
[1, 10, 16, 19, 3, 5]

After Heap Sort :
[1, 3, 5, 10, 16, 19]

After deleting :

Here there are duplicate 19

[3, 5, 10, 16, 19, 19]

I have done this arr = Arrays.copyOf(array, array.length -1); but I don't know if it still holds the Log N time complexity

This is my full code if you are interested:

import java.util.*;

public class ObligatoriskOpgave2 {
    int[] arr={1,10,16,19,3,5};

    public static void buildheap(int []arr) {

        /*
         * As last non leaf node will be at (arr.length-1)/2
         * so we will start from this location for heapifying the elements
         * */
        for(int i=(arr.length-1)/2; i>=0; i--){
            heapifyNumbers(arr,i,arr.length-1);
        }
    }

    public static void heapifyNumbers(int[] arr, int i, int size) {
        int left = 2*i+1;
        int right = 2*i+2;
        int max;
        if(left <= size && arr[left] > arr[i]){
            max=left;
        } else {
            max=i;
        }

        if(right <= size && arr[right] > arr[max]) {
            max=right;
        }
        // If max is not current node, swapCurrentNodeWithMaximumOfChildren it with max of left and right child
        if(max!=i) {
            swapCurrentNodeWithMaximumOfChildren(arr,i, max);
            heapifyNumbers(arr, max,size);
        }
    }

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

    public static int[] heapSort(int[] arr) {

        buildheap(arr);
        int sizeOfHeap=arr.length-1;
        for(int i=sizeOfHeap; i>0; i--) {
            swapCurrentNodeWithMaximumOfChildren(arr,0, i);
            sizeOfHeap=sizeOfHeap-1;
            heapifyNumbers(arr, 0,sizeOfHeap);
        }
        return arr;
    }

    public void deleteMinimum(int[] array){
        array[0] = array[array.length - 1];
        heapSort(array);
    }

    public static void main(String[] args) {
        ObligatoriskOpgave2 o = new ObligatoriskOpgave2();

        System.out.println("Before Heap Sort : ");
        System.out.println(Arrays.toString(o.arr));
        o.arr=heapSort(o.arr);
        System.out.println("=====================");
        System.out.println("After Heap Sort : ");
        System.out.println(Arrays.toString(o.arr));


        o.deleteMinimum(o.arr);
        System.out.println(Arrays.toString(o.arr));
    }
}

Creating and copying an array are both O(n) operations and pretty expensive. I would avoid doing either even if n is small. — Peter Lawrey

Redoishi Redoishi · Accepted Answer · 2018-11-06T12:57:54

https://docs.oracle.com/javase/tutorial/java/nutsandbolts/arrays.html

An array is a container object that holds a fixed number of values of a single type. The length of an array is established when the array is created. After creation, its length is fixed.

So if you want use array, you must create new array with your new length.
And fill new array with value of old array. (see part Copying Arrays in first link)

Java min heap decrease array size after removing element

2 Answers