public class PartialSolutionHeap {
    
    PartialSolution[] heap;
    int count;
    int size;
    int numInsertions;
    int numExtractions;
    
    public PartialSolutionHeap() {
        heap = new PartialSolution[100];
        count = 0;
        size = 100;
    }
    
    void insert(PartialSolution p) {
        //System.out.println("Inserting a new partial solution into the heap");
        numInsertions++;
        if (count == size) {
            PartialSolution[] temp = new PartialSolution[2*count];
            for (int i = 0; i < count; i++) temp[i] = heap[i];
            size *= 2;
            heap = temp;
        }
        
        heap[count] = p;
        int temp = count;
        int tempParent = (temp - 1) / 2;
        while ((temp > 0) && (heap[temp].getLower() < heap[tempParent].getLower())) {
                    swap(temp, tempParent);
                    temp = tempParent;
                    tempParent = (temp - 1) / 2;
        } // while
        count++;
    }
    
    void swap(int a, int b){
            PartialSolution t = heap[a];
            heap[a] = heap[b];
            heap[b] = t;
    } // swap(int,int)
    
    PartialSolution extractMin() {
        numExtractions++;
        PartialSolution returnPS = heap[0];
        int lostLeaf = promote(0);
        if (lostLeaf != count-1) {
            heap[lostLeaf] = heap[count-1];
            heap[count-1] = null;
            int temp = lostLeaf;
            int tempParent = (temp - 1) / 2;
            while ((temp > 0) && (heap[temp].getLower() < heap[tempParent].getLower())) {
                    swap(temp, tempParent);
                    temp = tempParent;
                    tempParent = (temp - 1) / 2;
            } // while
        }
        count--;
        //System.out.println("Extracted partial solution with cost " + returnPS.getLower());
        //returnPS.printChoices();
        return returnPS;
            
    } // exgtractMin
    
    int promote(int c) {
        // promote INTO location c by choosing the smaller of
        // its children, copying up the contents, and recursing
        // on the chosen one.
        // if c has no children, mark c as empty and return c
        int n = heap.length;
        int returnVal;
        if (2*c + 1 > n - 1) {
            heap[c] = null;
            return c;
        }
        else {
            int leftChildPos = 2*c+1;
            if (heap[leftChildPos] == null) {
                // I think I am right in believing that the right child cannot be filled
                // if the left child is not
                heap[c] = null;
                return c;
            } // if
            else {
                int rightChildPos = 2*c+2;
                if ((rightChildPos >= n) || (heap[rightChildPos] == null)) {
                    // promote the left child
                    heap[c] = heap[leftChildPos];
                    return promote(leftChildPos);
                } // if
                else {
                    int choice;
                    if (heap[rightChildPos].getLower() <= heap[leftChildPos].getLower())
                        choice = rightChildPos;
                    else choice = leftChildPos;
                    heap[c] = heap[choice];
                    return promote(choice);
                } // else
            } // else
        } // else
    } // promote
    
    boolean notEmpty() {return count != 0;}
    
    void report() {
        System.out.println("Number of partial solutions added to heap = " + numInsertions);
        System.out.println("Number of partial solutions extracted from heap = " + numExtractions);
    } // report()
} // class