0

I am attempting a heap sort that sorts from lowest to highest. My code runs and displays, but I have some issues. The output I get is:
The values in the heap array are: 8 9 2 3 4 1 5 6 7 Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 9, Size: 9

    at java.util.ArrayList.rangeCheck(Unknown Source)


at java.util.ArrayList.get(Unknown Source)
at MinHeap.print(MinHeap.java:77)
at ProblemThree.main(ProblemThree.java:13)

The values in the heap, sorted from smallest value to largest, are:
Parent branch: 1, Left Child Branch: 3, right child branch: 2.

Parent branch: 1, Left Child Branch: 6, right child branch: 4.

Parent branch: 1, Left Child Branch: 8, right child branch: 5.

Parent branch: 3, Left Child Branch: 9, right child branch: 7.

I've tried many times to rewrite the code, but I can't get it to display the error message. Also, I'm not 100% certain if the output in terms of parent and child branches is correct(it seems like the second output should have 2 as the parent branch, and the third line of the output should have 3 as the parent branch). Please help.

public class ProblemThree {
    public static void main(String[] args) {
        Integer[] heapNumbers = {8, 9, 2, 3, 4, 1, 5, 6, 7};

        System.out.print("The values in the heap array are: ");
        for (int i = 0; i < heapNumbers.length; i++) {
            System.out.print(heapNumbers[i] + " ");
        }

        MinHeap<Integer> minHeap = new MinHeap<Integer>(heapNumbers);
        System.out.println("\nThe values in the heap, sorted from smallest value to largest, are: ");
        for (int i = 0; i < minHeap.getSize(); i++) {
            minHeap.print();
        }
    }
}
import java.util.*;
public class MinHeap<E extends Comparable<? super E>> {
    private ArrayList<E> heapList = new ArrayList<E>();

    public MinHeap() {

    }

    public MinHeap(E[] heapItems) {
        for (int i = 0; i < heapItems.length; i++)
            add(heapItems[i]);
    }

    public void add(E newItem) {
        heapList.add(newItem);
        int childIndex = heapList.size()-1;

        while (childIndex > 0) {
            int fatherIndex = (childIndex-1)/2;
            if (heapList.get(childIndex).compareTo(heapList.get(fatherIndex)) < 0) {
                E temporary = heapList.get(childIndex);
                heapList.set(childIndex, heapList.get(fatherIndex));
                heapList.set(fatherIndex, temporary);
            }

            else
                break;

            childIndex = fatherIndex;
        }
    }

    public E branchAt(int branch) {
        return heapList.get(branch);
    }

    public E remove() {
        if (heapList.size() == 0)
            return null;

        E removedBranch = heapList.get(0);
        heapList.set(0, heapList.get(heapList.size() -1));
        heapList.remove(heapList.size() - 1);

        int currentBranch = 0;
        while (currentBranch < heapList.size()) {
            int leftChildBranch = 2 * currentBranch + 1;
            int rightChildBranch = 2 * currentBranch + 2;

            if (leftChildBranch >= heapList.size())
                break;
            int maxBranch = leftChildBranch;
            if (rightChildBranch < heapList.size()) {
                if (heapList.get(maxBranch).compareTo(heapList.get(rightChildBranch)) < 0) {
                    maxBranch = rightChildBranch;
                }
            }

            if (heapList.get(currentBranch).compareTo(heapList.get(maxBranch)) < 0) {
                E temporary = heapList.get(maxBranch);
                heapList.set(maxBranch, temporary);
                currentBranch = maxBranch;
            }
            else
                break;
        }

        return removedBranch;
    }

    public int getSize() {
        return heapList.size();
    }

    public void print() {
        for (int i = 0; i < heapList.size(); i++) {
            System.out.println("Parent branch: " + heapList.get((i-1)/2) + ", Left Child Branch: " + heapList.get(2*i + 1) + ", right child branch: " + heapList.get(2*i+2) + ".");
            System.out.println();
        }
    }
}
4
Contributors
3
Replies
14
Views
1 Year
Discussion Span
Last Post by Taywin
Featured Replies
  • Looking at the print method, where the error is generated, I see 2*i+1 etc in a loop where I goes up to the list size, so the out of bounds is inevitable Read More

1

Looking at the print method, where the error is generated, I see 2*i+1 etc in a loop where I goes up to the list size, so the out of bounds is inevitable

0

In part with JamesCherril answer, in your print() method, you are looping through the NUMBER of nodes (n) instead of the HEIGHT of your heap. You should rewrite the method definition into something similar to a tree iteration instead of direct iteration in a for-loop.

Edited by Taywin

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.