Java Max-Stack implementation to return maximum value in the stack 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 &lt; 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 &gt;= 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 &lt;= j) {
            int c = root * 2 + 1;

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

            }

            if (clone[root] &lt; 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 &gt;= 0; i--) {
            System.out.println(stack[i]);
        }
    }
}
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) &lt;= j &amp;&amp; clone[c] &lt;= clone[c + 1]) {
     c = c + 1;
 }


Can be change to this 

 if ((c + 1) &lt;= j &amp;&amp; clone[c] &lt; 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] &lt; 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] &gt;= 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 &lt;= 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.