// Priority Heap base class implementation.
// By Chuck Liang, for educational purposes only, March 2021

public class PriorityHeap<T extends Comparable<T>> implements PriorityQ<T>
{
    protected static int defaultcapacity = 16;
    protected T[] H; // the array underneath the abstract data type.
    protected int size;
    public int size() { return size; }
    public int capacity() { return H.length; }
    public java.util.Comparator<T> cmp = (x,y)->x.compareTo(y); //for later
    
    // Method to return generic array of size n, expect compiler warning.
    // This method must be @Override if T becomes more specific in subclass.
    @SuppressWarnings("unchecked") /* don't use unless you're REALY sure...*/
    protected T[] makearray(int n) { return (T[]) new Comparable[n]; }

    // constructors
    public PriorityHeap(int initcap)
    {
	if (initcap<1) initcap=defaultcapacity; 
	H = makearray(initcap);
	size = 0;
    } //constructor
    public PriorityHeap() { this(defaultcapacity); } // calls other constructor

    // resize to target capacity, but must leave heap at most 90% full, and
    // with an absolute min value of defaultcapacity.
    public void resize(int target) 
    {
	int minsize = (100*size)/90;
	if (minsize < defaultcapacity) minsize = defaultcapacity;
	if (target<minsize) target=minsize;
	T[] H2 = makearray(target);
	for(int i=0;i<size;i++) H2[i] = H[i];
	H = H2;     // set pointer to new array, size doesn't change
    }
    protected void doublecap() { resize(H.length*2); } // called on-demand
    
    // utility functions used by algorithms:

    protected static int left(int i) { return 2*i+1; } //left child index
    protected static int right(int i) { return 2*i+2; } //right child index
    protected static int parent(int i) { return (i-1)/2; } //parent index
    protected void swap(int i, int k) //swap H[i] with H[k], humor me for now
    {
	if (i<0 || i>=size || k<0 || k>=size) 
	    throw new RuntimeException("invalid swap indices "+i+","+k);
	T tmp = H[i];  H[i] = H[k];  H[k]=tmp;
    }

    // Some other properties of complete binary trees:
    // the number of leaf nodes in the tree is always (size+1)/2, so 
    // the number of non-leaf (interior nodes with children) is 
    // size - (size+1)/2, which is not the same as (size-1)/2 because of
    // integer division throwing away the remainder.
    // If an index is >= (size-1)/2, then we know it's a leaf node:
    protected boolean leafnode(int i)
    {
	return i<size && i >= (size - (size+1)/2);
    }


    protected int swapup(int i) // swap i upwards until less than parent,
    {                           // returns new position of H[i]
	if (i>=size || i<0) throw new RuntimeException("invalid index "+i);
	if (i==0) return 0; // can't swapup root
	int p = parent(i);
	while (i>0 && H[i].compareTo(H[p])>0)
	    {
		swap(i,p);
		i = p;
		p = parent(p);
	    }
	return i;
    }//swapup

    protected int swapdown(int i) //swap down until greater than children
    {
	if (i<0 || i>=size) throw new RuntimeException("invalid index "+i);
	// Many scenarios to take care of:
	// 1.left and right may not exist
	// 2.left may exist by not right (if right exists, left exists)
	// 3. must swap with larger of two children, if both exists.
	// may only assume that left child exists if right child exists
	int candidate = 1; // swap candidate, -1 means can't swap
	while (candidate != -1) 
	    {
		candidate = -1; // must reset to -1 each time
		int li = left(i), ri=right(i); // indices of childre
		if (li<size && H[i].compareTo(H[li])<0) candidate = li;
		if (ri<size && H[li].compareTo(H[ri])<0 && H[i].compareTo(H[ri])<0) candidate = ri;
		if (candidate != -1) { 
		    swap(i,candidate);
		    i = candidate;
		}// swap and move i downwards
		// else candidate stays -1 and loop stops
	    }//swap loop
	return i;
    }//swapdown


    ///////// PriorityQ interface functions

    public boolean add(T x)
    {
	if (x==null) return false; // don't allow insertion of null
	if(size>=H.length) resize(H.length*2); // double capacity
	size++;
	H[size-1] = x; // adds x to end of heap
	if (size>1) swapup(size-1);
	return true;
    }//add

    public T peek() 
    {
	if (size<1) return null;
	else return H[0]; // root is always at index 0
    }

    public T poll() // delete and return root, highest priority value
    {
	if (size<1) return null;
	T answer = H[0];
	H[0] = H[size-1]; // moves last value to root
	size--; // new size of tree
	if (size>1) swapdown(0);
	return answer;
    }

    public boolean contains(T x) // search using .equals, O(n)
    {
	for(int i=0;i<size;i++) if (H[i].equals(x)) return true;
	return false;
    }

    public boolean remove(T x) { return delete(x)!=null; }
    public T delete(T x)
    {
	if (x==null) return null;
	int xi = -1; // position of x
	for(int i=0;i<size && xi<0;i++) 
	    if (H[i].equals(x)) xi = i;
	if (xi <0) return null;
	T answer = H[xi];
	H[xi] = H[size-1]; // move last value into position
	int newxi = swapup(xi);
	if (newxi==xi) swapdown(newxi);
	return answer;
    }// remove


    /////// non-interface functions

    public boolean isheap() // checks if heap is indeed a heap
    {
	for(int i=size-1;i>0;i--)
	    if (H[i].compareTo(H[parent(i)])>0) return false;
	return true;
    }
    // needed by heapdisplay program:
    public T[] toArray() { return H; }

    //    /*  main for testing
    public static void main(String[] av)
    {
	PriorityHeap<Integer> PQ = new PriorityHeap<Integer>();
	int n = 100;
	if (av.length>0) n = Integer.parseInt(av[0]);
	for(int i=0;i<n;i++) PQ.add((int)(Math.random()*1000));
	System.out.println("is heap after adds: "+PQ.isheap());
	for(int i=0;i<n/10;i++) System.out.println(PQ.poll());
	// should print out in decreasing order
	System.out.println("is heap after polls: "+PQ.isheap());
	System.out.println("size: "+PQ.size());
	System.out.println("capacity: "+PQ.capacity());

	// need HeapDisplay.java in same folder:
	HeapDisplay window = new HeapDisplay(1000,680);
	window.drawtree(PQ.toArray(), PQ.size());
    }//main
    //    */
}//PriorityHeap


/*
Mathematical Properties of Complete Binary Trees and Heaps:

1. The number of leaf nodes (nodes with no children) is (size+1)/2 without
   the remainder.

   PROOF.

      First, call a complete binary tree "perfect" if all nodes on the 
      last level of the tree has zero children.  Every complete binary 
      tree has a perfect subtree with n perfect levels.  For example:

        8
      /   \
     4     7
    / \   / \
   2   3 5   3
  / \
 1   0

 This tree has n=3 perfect levels and 4 total levels.  The total
 number of nodes in the perfect subtree is (2**n)-1 (using python
 syntax for exponent).  The number of nodes on the last level of the
 perfect subtree is 2**(n-1).  The number of nodes on the very last
 level of the entire tree is either 2*m (even) or 2*m+1 (odd) for some m.
 In the above example, m==1 and there are 2*m==2 nodes on the last level.

 In the general case, the number of leaf nodes on the tree is always
 2**(n-1) + m.  This is because if a node on the last perfect level has
 only one child, then no extra child is added (one-one tradeoff - picture
 the 2 without the right child).  If a node on the last perfect level has
 two children, then one extra child is added.  We have two cases:

 a. if size == (2**n)-1 + 2*m, then (size+1)/2 == (2**n + 2*m)/2 ==
    2**(n-1) + m, which is the expected number of leafs.

 b. if size == (2**n)-1 + 2*m+1 == 2**n+2*m, then (size+1)/2 ==
    (2**n+2*m+1)/2.  This is an odd number dividing an even number
    (for n>0) and throwing away the remainder, we also get 2**(n-1)+m.


2. The worst and average case time complexity of peek() and size() is O(1);
2b.The worst and average case complexity of .contains and .remove is O(n)   

3.  The worst case time complexity of .add is O(log n) without resize and 
     O(n) with resize. However, for n .add operations the total cost of 
     resizing stays within O(n).  This is similar to the Circular Queue.
3b. The average and worst case complexity of .poll() is O(log n);

4.  The average case time complexity of .add is O(1).  This is the
most interesting property.  Notice that half of all nodes are leaf
nodes, (size+1)/2 to be exact but we'll just call it n/2. Thus there
is a 50% or 1/2 chance that whatever number you insert will end up as
a leaf, requiring no further swaps upwards.  Call this a 1-step
operation.  (To be technically correct, there is a 50% chance as n
approches infinity, thus it is valid to ignore the +1 in size+1).

Each level of the tree has twice the number of nodes as the previous
level.  Thus there is a 25% or 1/4 chance that the node inserted will
be just above a leaf node, requiring one additional swapup operation.
Call this 2 steps.  Similarly, there is 1/8 chance that the inserted node
will require 3 steps, 1/16 chance that it will require 4 steps, and so
on...  In general, there will be a 1/2**m chance that .add will require
m steps.

We can write down the average number of steps to insert a value as a
weighted average of these cases.  For example (1/4)a + (3/4)b is a
weighted average of a and b where b has three times the weight of a.
The sum of the weights (probabilities) must add up to one.  But since
we don't know how large the tree is, we will have to write down the
weighted average as an infinite series (grab your calculus textbook).

Let inf = infinity.  The weighted average of the number of steps to insert
a value into an arbitrary binary heap is 

 inf  
Sigma  n/2**n   =  1*1/2 + 2*1/4 + 3*1/8 + 4*1/16 + 5*1/32 ...
 n=1 

Using established theorems concerning the convergence of series, we
observe that the ratio between successive values in the series is

      (n+1)
     --------
     2**(n+1)
  ---------------
        n
     --------
       2**n

This cancels out to be   (n+1) / 2*n. And 

limit     (n+1)/(2*n)   ==  1/2 
n->inf  

Since the limit of this ratio is less than one, we know that the
series converges to some number S.  This is enough to conclude that
.add is O(1) on average, but we want to know what S actually is.

Notice that the probabilities of each possible outcome form the series

 inf 
Sigma  1/2 * (1/2)**n  = 1/2 + 1/4 + 1/8 + 1/16 ...
 n=0

This is a *geometric* series and it converges to 1: the body of the sum
can be written in the form a*r**n with a=1/2 and r=1/2.  Such series
converges to a/(1-r), which in this case is (1/2)/(1/2) == 1.

Thus all the probabilities added together is indeed 1.  Furthermore, let
ONE be the geometric series above, we can observe the following equality

  S - ONE = S / 2

Because S - ONE is 0 + 1/4 + 2/8 + 3/16 + 4/32 ...

But S/2 gives us the same series.  Thus S-1==S/2 and therefore we have

      S == 2

This tells us that it takes on average 2 steps (one swap) to insert a
value into a binary heap.
*/