6
\$\begingroup\$

I'd like this to be reviewed:

public class MaxHeap<E extends Comparable<E>> {
    private E[] heap;
    private int capacity; // maximum size of heap
    private int numberOfNodes; // number of nodes in current heap

    /**
     * Create a new MaxHeap object.
     *
     * @param heap
     * @param capacity
     * @param numberOfNodes
     */
    public MaxHeap(E[] heap, int capacity, int numberOfNodes) {
    this.heap = heap;
    this.capacity = capacity;
    this.numberOfNodes = numberOfNodes;

    this.buildHeap();
    }

    /**
     * Put all nodes within the max heap in the correct position.
     */
    void buildHeap() {
    for (int i = (this.numberOfNodes / 2 - 1); i >= 0; i--) {
        this.correctNodeIndexByShifting(i);
    }
    }

    /**
     * Insert a new node at the current position within the max-heap.
     *
     * @param nodeValue
     *            The node to be inserted.
     */
    public void insert(E nodeValue) {
    if (this.capacity <= this.numberOfNodes) {
        throw new IllegalArgumentException("In method insert of class "
            + "MaxHeap the element: " + nodeValue
            + " could not be inserted because the max-heap is full");
    }

    int currentNodePosition = this.numberOfNodes++;
    this.heap[currentNodePosition] = nodeValue;

    // start at the end of most bottom right leaf node and shift up
    // until the nodeValue has a parent with a greater or equal value
    while ((currentNodePosition != 0)
        && (this.heap[currentNodePosition].compareTo(this.heap[this
            .getParentIndex(currentNodePosition)]) > 0)) {
        this.swap(currentNodePosition,
            this.getParentIndex(currentNodePosition));
        currentNodePosition = this.getParentIndex(currentNodePosition);
    }
    }

    /**
     * Remove the node at arrayIndex within the MaxHeap and return the node
     * value that the removed node is replaced with.
     *
     * @param arrayIndex
     *            Index of the node within the array based max-heap to be
     *            removed.
     * @return The element that was removed.
     */
    public E remove(int arrayIndex) {
    int changingArrayIndex = arrayIndex;
    if ((changingArrayIndex < 0)
        || (changingArrayIndex >= this.numberOfNodes)) {
        throw new IllegalArgumentException("In method remove of class "
            + "MaxHeap the input node postion to be removed is invalid");
    }

    // if the most bottom right node is being removed there is no work to be
    // done
    if (changingArrayIndex == (this.numberOfNodes - 1)) {
        this.numberOfNodes--;
    } else {
        // swap node to be removed with most bottom right node
        this.swap(changingArrayIndex, --this.numberOfNodes);

        // if swapped node is large, shift it up the tree
        while ((changingArrayIndex > 0)
            && (this.heap[changingArrayIndex].compareTo(this.heap[this
                .getParentIndex(changingArrayIndex)]) > 0)) {
        this.swap(changingArrayIndex,
            this.getParentIndex(changingArrayIndex));
        changingArrayIndex = this.getParentIndex(changingArrayIndex);
        }
        if (this.numberOfNodes != 0) {
        // if swapped node is small, shift it down the tree
        this.correctNodeIndexByShifting(changingArrayIndex);
        }
    }
    return this.heap[changingArrayIndex];
    }

    /**
     * @return maximum node value in max-heap.
     */
    public E removeMaximumValue() {
    if (this.numberOfNodes <= 0) {
        throw new IllegalStateException(
            "In method removeMaximumValue of class "
                + "MaxHeap the value you cannot remove a value from an "
                + "empty max-heap");
    }
    // swap maximum with last value
    this.swap(0, --this.numberOfNodes);

    if (this.numberOfNodes != 0) {
        // if not the last element
        this.correctNodeIndexByShifting(0);
    }
    return this.heap[this.numberOfNodes];
    }

    /**
     * Place given node position in the correct position within the complete
     * binary tree.
     *
     * @param arrayIndex
     *            Index of node to be correctly shifted to the correct position.
     */
    void correctNodeIndexByShifting(int arrayIndex) {
    int changingArrayIndex = arrayIndex;
    if ((changingArrayIndex < 0)
        || (changingArrayIndex >= this.numberOfNodes)) {
        throw new IllegalArgumentException(
            "In method shiftDown of class "
                + "MaxHeap the value: "
                + changingArrayIndex
                + " represents a node that does not exist in the current heap");
    }
    while (!this.isLeafNode(changingArrayIndex)) {
        int childIndex = this.getLeftChildIndex(changingArrayIndex);
        if ((childIndex < (this.numberOfNodes - 1))
            && (this.heap[childIndex]
                .compareTo(this.heap[childIndex + 1]) < 0)) {
        childIndex++; // childIndex is not at index of child with
                  // greater node value
        }
        if (this.heap[changingArrayIndex].compareTo(this.heap[childIndex]) >= 0) {
        return;
        }
        this.swap(changingArrayIndex, childIndex);
        changingArrayIndex = childIndex; // node shifted down
    }
    }

    /**
     * Switch the node at arrayIndex1 into node at arrayIndex2 and vice versa.
     *
     * @param arrayIndex1
     * @param arrayIndex2
     */
    void swap(int arrayIndex1, int arrayIndex2) {
    if (arrayIndex1 < 0 || arrayIndex1 > this.numberOfNodes) {
        throw new IllegalArgumentException(
            "In method swap of class "
                + "MaxHeap the input arrayIndex1 is not a valid node position");
    } else if (arrayIndex2 < 0 || arrayIndex2 > this.numberOfNodes) {
        throw new IllegalArgumentException(
            "In method swap of class "
                + "MaxHeap the input arrayIndex2 is not a valid node position");
    }
    E tempNodeValue = this.heap[arrayIndex1];
    this.heap[arrayIndex1] = this.heap[arrayIndex2];
    this.heap[arrayIndex2] = tempNodeValue;
    }

    /**
     * @param arrayIndex
     *            Index of child node.
     * @return Index of parent to given index of child.
     *
     */
    public int getParentIndex(int arrayIndex) {
    if (arrayIndex <= 0) {
        throw new IllegalArgumentException(
            "In method getParentPosition of class "
                + "MaxHeap your input node position at "
                + arrayIndex + " must be > 0");
    } else {
        return (arrayIndex - 1) / 2;
    }
    }

    /**
     * @param arrayIndex
     *            Index of parent node.
     * @return Index of right child within array based max-heap to given parent
     *         node.
     */
    public int getRightChildIndex(int arrayIndex) {
    if (arrayIndex >= (this.numberOfNodes / 2)) {
        throw new IllegalArgumentException("In method rightChild of class "
            + "MaxHeap your input node position at " + arrayIndex
            + " does not have a right child.");
    } else {
        return 2 * arrayIndex + 2;
    }
    }

    /**
     * @param arrayIndex
     *            Index of parent node.
     * @return Index of left child within array based max-heap to given parent
     *         node.
     */
    public int getLeftChildIndex(int arrayIndex) {
    if (arrayIndex >= (this.numberOfNodes / 2)) {
        throw new IllegalArgumentException("In method leftChild of class "
            + "MaxHeap your input node position at " + arrayIndex
            + " does not have a left child.");
    } else {
        return 2 * arrayIndex + 1;
    }
    }

    /**
     * @param arrayIndex
     *            Index of node to be checked.
     * @return True if node at given arrayIndex is a leaf node; otherwise return
     *         false.
     */
    public boolean isLeafNode(int arrayIndex) {
    if ((arrayIndex >= (this.numberOfNodes / 2))
        && (arrayIndex < this.numberOfNodes)) {
        return true;
    } else {
        return false;
    }
    }

    /**
     * @return The number of nodes in this max-heap.
     */
    public int getNumberOfNodes() {
    return this.numberOfNodes;
    }

    /**
     * @return The height of the heap.
     */
    public int getHeapHeight() {
    double approximateHeight = Math.log(this.numberOfNodes) / Math.log(2);
    int actualHeight = (int) (Math.floor(approximateHeight) + 1);
    return actualHeight;
    }

    /**
     * @return String representation of elements in the array used to implement
     *         the max-heap.
     */
    public String printMaxHeapArray() {
    StringBuilder maxHeapArray = new StringBuilder();
    for (int i = 0; i < this.heap.length; i++) {
        maxHeapArray.append(this.heap[i] + " ");
    }
    return maxHeapArray.toString();
    }
}
\$\endgroup\$
7
\$\begingroup\$

I haven't checked the details of the algorithm, just some general feedback on the code, API, etc:

  1. It's usually a good practice to make a copy of mutable input parameters. (E[] heap in this case.) It prohibits malicious clients to modify the heap's internal structure or it could save you from a few hours of debugging. (Effective Java, 2nd Edition, Item 39: Make defensive copies when needed)

    Copying the input array would make the capacity field redundant. You could use heap.length instead of it.

  2. The constructor should validate its input parameters. Currently it's too easy to call it with a wrong size array:

    String[] heap = {"aa", "ac", "bb"};
    int capacity = 4;
    int numberOfNodes = 4;
    MaxHeap<String> maxHeap =
        new MaxHeap<String>(heap, capacity, numberOfNodes);
    

    If you call a maxHeap.insert("ab") after that you get a mysterious ArrayIndexOutOfBoundsException. (Effective Java, Second Edition, Item 38: Check parameters for validity) (Copying the input array to a properly sized array could solve this issue too.)

  3. It's easy to misunderstood the parameter of remove(). Currently it's an index. A client easily think that the following code removes 20 from the heap:

    final Integer[] initialData = {10, 30, 20, 40};
    int capacity = 4;
    int numberOfNodes = 3;
    MaxHeap<Integer> heap =
        new MaxHeap<Integer>(initialData, capacity, numberOfNodes);
    heap.remove(20);
    

    Actually it throws an exception, since there aren't 20 items in the heap.

    Note that there isn't any other method which returns an index so how could a client figure out a valid parameter of the remove method? A remove(E item) method would be better.

  4. Implementation of printMaxHeapArray could be replaced with return Arrays.toString(heap); if output format is not bound. (Output of Arrays.toString() is a slightly different: [cc, bb, aa, ab]). Otherwise, I'd use a more compact foreach loop:

    for (final E item: heap) {
        maxHeapArray.append(item + " ");
    }
    

    Checking it again I guess i < this.heap.length should be i < this.numberOfNodes. I think you don't want to print the removed items.

  5. Java already has a toString() method. If you use printMaxHeapArray only for debugging or logging purposes and clients don't rely on its exact output you should implement (override) toString() instead. toString() is more convenient for most developers. (Effective Java, 2nd Edition, Item 10: Always override toString)

  6. Comments like this are unnecessary:

    /**
     * Create a new MaxHeap object.
     * 
     * @param heap
     * @param capacity
     * @param numberOfNodes
     */
    

    They say nothing more than the code already does, it's rather noise. (Clean Code by Robert C. Martin: Chapter 4: Comments, Noise Comments)

  7. Instead of comments like this:

     * @param arrayIndex
     *            Index of parent node.
    

    rename the parameter to parentIndex or parentNodeIndex. It would help readers, make the code readable and you could get rid of the comment. The same is true for getParentIndex(final int arrayIndex) (childIndex).

  8. boolean isLeafNode(final int arrayIndex) returns false when the given index is higher than the size of the array. I guess calling the method with a definitely invalid index is a bug in the client code. Crash early, throw an IllegalArgumentException (as the getLeftChildIndex() method does). See: The Pragmatic Programmer: From Journeyman to Master by Andrew Hunt and David Thomas: Dead Programs Tell No Lies.

  9. The else keyword is unnecessary here:

    if (arrayIndex1 < 0 || arrayIndex1 > this.numberOfNodes) {
        throw new IllegalArgumentException("In method swap of class "
                + "MaxHeap the input arrayIndex1 is not a valid node position");
    } else if (arrayIndex2 < 0 || arrayIndex2 > this.numberOfNodes) {
        throw new IllegalArgumentException("In method swap of class "
                + "MaxHeap the input arrayIndex2 is not a valid node position");
    }
    

    It could be simply

    if (arrayIndex1 < 0 || arrayIndex1 > this.numberOfNodes) {
        throw new ...
    }
    if (arrayIndex2 < 0 || arrayIndex2 > this.numberOfNodes) {
        throw new ...
    }
    
  10. Furthermore, you could extract out the checking logic (since it's duplicated, used twice for the two parameters and the same logic is in other methods too) to a validator method:

    void swap(final int arrayIndex1, final int arrayIndex2) {
        checkValidIndex(arrayIndex1,
                "In method swap of class MaxHeap the input arrayIndex1 is not a valid node position: " + arrayIndex1);
        checkValidIndex(arrayIndex2,
                "In method swap of class MaxHeap the input arrayIndex2 is not a valid node position: " + arrayIndex2);
        ...
    }
    
    private void checkValidIndex(final int arrayIndex, final String message) {
        if (arrayIndex < 0 || arrayIndex > this.numberOfNodes) {
            throw new IllegalArgumentException(message);
        }
    }
    

    Google Guava has similar checkArgument method which supports handy template strings (%s) too. (See also: Effective Java, 2nd edition, Item 47: Know and use the libraries The author mentions only the JDK's built-in libraries but I think the reasoning could be true for other libraries too.)

  11. I'd use a little bit shorter exception messages, like "invalid arrayIndex: " + arrayIndex1. The stacktrace will show the place of the error. It helps debugging if you put the invalid value to the message.

  12. I think that the tempNodeValue could have a better name. Currently it does not express the developer's intent and the purpose of the variable. (Every local variable is temporary.) I'd call it oldValue instead since it stores the old value of index1.

  13. The this.heap[changingArrayIndex].compareTo(this.heap[this.getParentIndex(changingArrayIndex)]) > 0 condition is duplicated. It could be extracted out to a helper method:

    private boolean compareWithParent(final int arrayIndex) {
        final int parentIndex = this.getParentIndex(arrayIndex);
        return heap[arrayIndex].compareTo(heap[parentIndex]) > 0;
    }
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.