Java Max-Stack implementation to return maximum value in the stack

Question

I have written the below program to write a Java stack implementation. I have added a method which returns the maximum value in the stack, e.g, a pop. The implementation for this is based on the Max Heap Sort algorithim. I have little doubt on the time complexity analysis - it's not \$O(\log n)\$ is it?

public class Stack {

    int top = -1;
    int[] stack;

    public Stack(int size) {
        stack = new int[size];
    }

    public void push(int v) {
        if (top == stack.length - 1) {
            System.out.println("Oveflow!!");
            return;
        }
        stack[++top] = v;
    }

    public void pop() {
        if (top < 0) {
            System.out.println("Empty stack");
            return;
        }

        stack[top] = 0;
        top--;

    }

    public int getMax() {

        int[] c = stack.clone();
         // not a complete heap sort, but with below approach, i am trying bubble up.
        // build the heap starting from n/2, as any nodes after n/2 are leaf(s)
        for (int j = stack.length / 2; j >= 0; j--) {
            buildMaxHeap(c, j, c.length - 1);
        }

        return c[0];
    }

    private void buildMaxHeap(int[] clone, int i, int j) {
        int root = i;

        while (root * 2 + 1 <= j) {
            int c = root * 2 + 1;

            if ((c + 1) <= j && clone[c] <= clone[c + 1]) {
                c = c + 1;

            }

            if (clone[root] < clone[c]) {
                int t = clone[root];
                clone[root] = clone[c];
                clone[c] = t;
                root = c;
            } else {
                root++;
            }
        }

    }

    public void display() {
        System.out.println("------------------------");
        for (int i = top; i >= 0; i--) {
            System.out.println(stack[i]);
        }
    }
}

Answer 1

Running time:

The running time is not O(lg(n)) is O(n) since you are building a max heap.

You iterate over elements (no leaf elements). Knowing this we can conclude that is at least O(n). The function called buildMaxHeap is actually O(h), h being the height of the node (which you call i). So because the height of any heap is

and because this summation to the infinity ends up being constant:

we get O(n).

Names:

buildMaxHeap doesn't actually builds the max heap so it name is not appropriate. This function is commonly called maxheapify and is to maintain the heap property. Also I would change the name of parameter named clone for something more generic, because in that context it doesn't matter if its a clone or not.

Pop:

Pop doesn't return the element poped, neither I see a top function so this stack is pointless.

Code

This part:

 if ((c + 1) <= j && clone[c] <= clone[c + 1]) {
     c = c + 1;
 }

Can be change to this

 if ((c + 1) <= j && clone[c] < clone[c + 1]) {
     ++c;
 }

Because if both are equal why bother incrementing c ?

This is not that important though I am just nitpicking.

This part could be improved as well:

 if (clone[root] < clone[c]) {
    int t = clone[root];
    clone[root] = clone[c];
    clone[c] = t;
    root = c;
 } else {
    root++;
 }

For the swapping it would be more readable to implement a method named swap. Also if there is no swapping the algorithm should terminate, because the lower subtrees are already max heaps so its pointless. This is the reason why building a max heap starts at floor(n/2).

so this part would end up like this

 if (clone[root] >= clone[c]) break; 

 swap(clone, root, c);
 root = c;

Conclusion:

Given the hidden constant factor in your function getMax (cloning the array and the hidden constant factor in building a max heap) its better to do it the straightforward way:

    int max = Integer.MIN_VALUE;
    for(int i = 0; i <= top; ++i)
        max = Math.max(max, stack[i]);

or for Java 8:

    OptionalInt i = Arrays.stream(stack,0, top+1).max();    

Additional notes: This also can be improved with Java generics.

Answer 2

Pop doesn't return value

I'm not sure what your stack is used for. Your pop() function doesn't return the value of the top of the stack. So, is the only thing the stack is used for to return the maximum value?

Getting max value in constant time

You can get the maximum value in \$O(1)\$ time if you keep a second stack dedicated to holding the maximum value at each stack level. In fact, if your pop() function isn't going to return a value, you can get rid of your original stack and only keep maxstack. Here is a rewrite of your implementation, which also changes pop() to return a value.

public class Stack {

    int top = -1;
    int[] stack;
    int[] maxstack;

    public Stack(int size) {
        stack = new int[size];
        maxstack = new int[size];
    }

    public void push(int v) {
        if (top == stack.length - 1) {
            System.out.println("Overflow!!");
            return;
        }
        stack[++top] = v;
        if (top == 0 || v >= maxstack[top-1]) {
            maxstack[top] = v;
        } else {
            maxstack[top] = maxstack[top-1];
        }
    }

    public int pop() {
        if (top < 0) {
            System.out.println("Empty stack");
            return 0;
        }
        return stack[top--];
    }

    public int getMax() {
        return maxstack[top];
    }
}