How can I build a max heap java class for an object?

Question

I am trying to build a max heap java class for item objects, so I can solve the knapsack problem and implement greedy algorithms to do so. Item class includes weight, value, Id(to distinguish items), and most importantly a priority factor:

public class Items {
    double weight;
    double value;
    double priorityFactor; 
    int ID; 
    
    //constructor for items class
     public Items(int weight, int value, int id, int priorityFactor)  
        {
            this.weight=weight;
            this.value=value;
            this.ID=id;
            this.priorityFactor = priorityFactor;
        } //end constructor 

Now the issue that I'm facing is in the max heap class, which is supposed to build me a max heap tree based on the priority factor. Means that I should have an array of item objects: private Items[] array

What I'm finding difficult to implement is how can I insert those items in the array based on the priority factor. If I do this, I think I will be able to implement the greedy algorithms. How to handle this?

Answer 1

This is the basic code for a min/max heap (depending on the T:compareTo() method). This only handles insertion, but I think it's what you're after.

package jc.lib.container.collection.set;

import jc.lib.lang.string.JcStringBuilder;



public class JcHeap<T extends Comparable<T>> {
    
    
    
    private T[] mItems;
    private int mItemCount  = 0;
    
    
    
    @SuppressWarnings("unchecked") public JcHeap(final int pStartCapacity) {
        mItems = (T[]) new Comparable[pStartCapacity];
    }
    
    
    
    private void checkResize() {
        if (mItems.length <= mItemCount) {
            final int newSize = (mItems.length) * 2;
            @SuppressWarnings("unchecked") final T[] tmp = (T[]) new Comparable[newSize];
            if (mItems != null) System.arraycopy(mItems, 0, tmp, 0, mItemCount);
            mItems = tmp;
        }
    }
    
    static private int getParentIndex(final int pCurrentIndex) {
        return (pCurrentIndex - 1) / 2;
    }
    @SuppressWarnings("unused") static private int getLeftChildIndex(final int pCurrentIndex) {
        return 2 * pCurrentIndex + 1;
    }
    @SuppressWarnings("unused") static private int getRightChildIndex(final int pCurrentIndex) {
        return 2 * pCurrentIndex + 2;
    }
    
    
    
    public void addItem(final T pItem) {
        checkResize();
        
        // insert
        System.out.println("\nInserting " + pItem);
        T current = pItem;
        int currentIndex = mItemCount;
        mItems[currentIndex] = current;
        ++mItemCount;
        
        // sort
        while (true) { // swap up
            if (currentIndex <= 0) break;
            final int parentIndex = getParentIndex(currentIndex);
            final T parent = mItems[parentIndex];
            System.out.print("Checking cur:" + current + " vs par:" + parent + " => " + current.compareTo(parent) + "/");
            if (current.compareTo(parent) >= 0) {
                System.out.println("break");
                break;
            }
            System.out.println("swap");

            System.out.println("Swapping with parent: " + parent);
            final T tmp = mItems[parentIndex];
            mItems[parentIndex] = mItems[currentIndex];
            mItems[currentIndex] = tmp;
            currentIndex = parentIndex;
            current = mItems[currentIndex];
        }
    }
    
    //  public boolean contains(final T pItem) {
    //      final int index = findIndex(pItem);
    //      return 0 <= index && index < mItemCount;
    //  }
    //
    //  public int findIndex(final T pItem) {
    //      int index = 0;
    //      int width = mItemCount;
    //
    //      while (true) {
    //          System.out.println("Comparing with index " + index);
    //          final int cmp = pItem.compareTo(mItems[index]);
    //          if (cmp == 0) return index;
    //          else if (cmp > 0) return -1;
    //
    //          index += mItemCount;
    //          width /= 2;
    //          if (width == 0) return -1;
    //      }
    //  }
    
    
    
    @Override public String toString() {
        final StringBuilder sb = new StringBuilder();
        sb.append("\nTree View:\n");
        int height = (int) (Math.log(mItemCount) / Math.log(2));
        sb.append("count=" + mItemCount + " height=" + height);
        int next = 1;
        sb.append("\n[");
        sb.append(JcStringBuilder.buildFromArray(", ", (Object[]) mItems));
        //      for (int c = 0; c < mItemCount; c++) {
        //          sb.append("\n" + mItems);
        //      }
        sb.append("]");

        for (int c = 0; c < mItemCount; c++) {
            if (c + 2 > next) {
                sb.append("\n");
                for (int d = 0; d < height; d++) {
                    sb.append("\t");
                }
                height -= 1;
                next *= 2;
                //              System.out.println("Next is " + next);
            }
            
            sb.append("<" + mItems[c] + ">\t");
        }
        
        return sb.toString() + "\n";
    }
    
}