Building MinHeap using insert() method

[JainishP]

This is the class I created to make a MinHeap from data that is being inserted into it:

public class MinHeap
{
    protected int [] a;
    protected int lastindx;

    public MinHeap()
    {
        lastindx = 0;                   // heap starts at a[1]
        a = new int[1];
    }

    // is the heap empty?
    public boolean isEmpty()
    {
        return lastindx < 1;           // heap starts at a[1]
    }

    // how many items in the heap?
    public int size()
    {
        return lastindx;               // heap starts at a[1]
    }


    // remove and return the maximum item, reconnect and restructure
    // throws ItemNotFound if there is no maximum item
    public int deleteMin()  throws ItemNotFound
    {
        if (isEmpty())
            throw new ItemNotFound("Cannot extractmax() on empty max heap");

        int temp = a[1];
        a[1] = a[lastindx];
        lastindx--;
        percDown(a, 1, lastindx);
        return temp;
    }

    // insert the new item x and percolate it up into place
    public void insert(int x)
    {
        lastindx++;
        if (lastindx==a.length)
            expandArray();
        decreaseKey(lastindx,x);
    }

    // dump out the heap in array index order (level order)
    public void dumpHeap()
    {
        for(int i = 1; i < lastindx; i++)
            System.out.print(a[i] + " ");
            System.out.println();
    }

  
    //------------- private support methods ----------------------

    // left child of a[i]
    private int LC(int i)
    {
        return 2*i;
    }

    // right child of a[i]
    private int RC(int i)
    {
        return 2*i+1;
    }

    // parent of a[i]
    private int P(int i)
    {
        return i/2;
    }

    // swap a[i] and a[j]
    private void swap(int i, int j)
    {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    // percolate upward from a[k], n is the size of the heap
    // (i.e., a[n] is the last occupied slot)
    private void percDown(int[] a, int k, int n)
    {
        int smallest = k;
        int temp = 0;

        if(LC(k) <= n && a[LC(k)] > a[k])
            smallest = LC(k);
        if(RC(k) <= n && a[RC(k)] > a[smallest])
            smallest = RC(k);
        if(smallest != k)
        {
            temp = a[k];
            a[k] = a[smallest];
            a[smallest] = temp;
            percDown(a, smallest, n);
        }
    }

    // increase the value of the key at a[i] and percolate it upward, if needed
    private void decreaseKey(int i, int newval)
    {
        a[i] = newval;
        while ((i>1) && (a[P(i)] < a[i]))
        {
            swap(i,P(i));
            i = P(i);
        }
    }

    // double the size of the array a[]
    private void expandArray()
    {
        int[] t = new int [2*a.length];
        for(int i = 0; i < a.length; i++)
        {
            t[i] = a[i];
        }
        a = t;
    }
}

However, I'm having problems with this sorting the data I insert into it. I'm inserting character frequencies(found from a text file) to the heap, but the resulting hep isn't sorted properly for me to go ahead with the rest of the program.

This is what I use to insert data into the MinHeap:

for(int i = 0; i < f.length; i++)
{
      if(f[i] > 0)
      mih.insert(f[i]);
}

Using the dumpHeap(); method I get the following results(example insert):

11 2 7 2

Instead of:

11 7 2 2

Is there something wrong with my MinHeap class? Or is something else wrong with the program?

[georgeh1]

Do you know how data is stored in a MinHeap? Your implementation is very confusing, but your output seems to be correct. Remember that the left and right child must be greater than or equal to the parent. If 2 is the parent, then it's children are 7 and 2. If you want the array to print out in order from least to greatest, you would have to use the deleteMin method until all the elements were removed.

Is there something wrong with my MinHeap class? Or is something else wrong with the program?

So to answer both of your questions: it's very confusing, but somehow it works.