Heap

In this section, we will implement naive simple Min Heap here which utilised java default array but using tree structure (so the if the index is halved then it is the parent).

We first define the array, initialisation and size function.

class SSEHeap{
    private int[] arr = null;

    public int size(){
        return arr.length;
    }

    public SSEHeap(){
        arr = new int[0]; //create array with 0 size
    }
}

Next we define the add function, every time we add - we add at the end of the array then sift up. Sift up will compare its value with parent value if it is lower then swap with its parent.

     public void add(int toBeAdded){
        int[] tempArr = arr.clone();
        arr = new int[this.size()+1];

        //copy actually is 0(n) operation
        System.arraycopy(tempArr, 0, arr, 0, tempArr.length);

        arr[this.size()-1] = toBeAdded;
        siftUp(this.size()-1);
    }

    private void siftUp(int idx){
        int checkIdx = idx/2;
        while(checkIdx >= 0){
            if (checkIdx == idx)
                break;

            //System.out.println("idx = " + idx + " checkIDx = " + checkIdx + " arr[idx]= " + arr[idx]);
            if (arr[idx] < arr[checkIdx]){
                int temp = arr[idx];
                arr[idx] = arr[checkIdx];
                arr[checkIdx] = temp;
            }else{
                break;
            }

            if (checkIdx == 0)
                break;
            idx = checkIdx;
            checkIdx = checkIdx/2;

        }
    }

Next we define the remove function, every time we remove - we remove the index 0 and move last element to index 0 then sift down. Sift down will compare its value with children value if it is lower then swap.

      private void siftDown(){
        int checkIdx = 1;
        int idx = 0;

        if (size() == 2 && arr[idx] > arr[checkIdx]){
            int temp = arr[idx];
            arr[idx] = arr[checkIdx];
            arr[checkIdx] = temp;
        }

        while (checkIdx < size()-1){
            if (arr[idx] > arr[checkIdx] || arr[idx] > arr[checkIdx+1]){
                if (arr[checkIdx] < arr[checkIdx+1]){
                    int temp = arr[idx];
                    arr[idx] = arr[checkIdx];
                    arr[checkIdx] = temp;
                }else{
                    checkIdx = checkIdx+1;
                    int temp = arr[idx];
                    arr[idx] = arr[checkIdx];
                    arr[checkIdx] = temp;
                }
                idx = checkIdx;
                checkIdx = checkIdx * 2;
            }else{
                break;
            }
        }

    }
    public int remove(){
        int[] tempArr = arr.clone();
        int tobeReturned = tempArr[0];
        tempArr[0] = tempArr[size()-1];

        arr = new int[this.size()-1];

        //copy actually is 0(n) operation
        System.arraycopy(tempArr, 0, arr, 0, tempArr.length-1);

        siftDown();
        return tobeReturned;
    }

Next we define the print function, it will just print the array.

     public void print(){
        for (int i=0; i<arr.length; i++){
            System.out.print(arr[i] + ",");
        }
        System.out.println("");
    }

Heap is useful because it is O(log(n)), everytime you insert or remove it only need log(n) time.

Note: This implementation is naive and simple, haven't been thoroughly tested, please do not use in production, it is meant for simple explanation only. And also there can be better implementation.

You can try to run the code here:

Run on jdoodle