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();
        }
    }
}

Recommended Answers

All 3 Replies

You need to read Knuth's work on Sorting and Searching. Remember the KISS (Keep It Simple Stupid) principle. Read this in Wikipedia: https://en.wikipedia.org/wiki/Heapsort

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

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.