java - 测试我的堆

Question

1.) 我在测试堆类时遇到困难。当我尝试打印堆时，它给我的是代码而不是数组。我尝试使用 toString() 和 DeeptoString() 但都不起作用。

2.) 在我的 updateValue 方法中。我意识到，一旦到达没有子节点的节点，它就不知道该怎么办。它使我的索引超出范围。我认为检查这一点的一个简单方法是查看左右子索引是否大于或等于大小。如果是的话...我想我希望它什么也不做。

代码如下:

import java.util.NoSuchElementException;

public class MaxHeap {

    public int[] heap;
    private int size;

    public static void main(String args[]){
        MaxHeap testHeap = new MaxHeap(5);
        testHeap.add(5);
        testHeap.add(4);
        testHeap.add(3);
        testHeap.add(2);
        testHeap.add(1);
        System.out.println((testHeap));
        testHeap.maxHeapify(0);
        System.out.println(testHeap);
        testHeap.extractMax();
        System.out.println(testHeap);
        testHeap.updateValue(1, 6);
        System.out.println(testHeap);

    }
    /**
     * _Part 0: Implement this constructor._
     * 
     * Creates a new Heap instance initially capable of storing the specified
     * number of elements.
     * 
     * @param initialsize the initial size of the heap array
     */
    public MaxHeap(int initialsize) {
        // TODO: implement this
        heap = new int [initialsize]; 

    }

    /**
     * Provides read-only access to the heap's size. Size here is the number
     * of *valid* items in the heap
     * 
     * @return the number of items in the heap
     */
    public int size() {
        return size;
    }

    /**
     * _Part 1: Implement this method._
     * 
     * Adds an item to the heap maintaining the heap condition.
     * 
     * An item is added to the next available slot in the array, and then
     * bubbled up to its parent until the heap condition is restored.
     * 
     * @param item
     *            the new int to add to the heap
     */
    public void add(int item) {
        // TODO: implement this
        int parentIndex = (size-1)/2;
        int childIndex = size;
        heap[size] = item;  //put it at the end

        while (heap[parentIndex] < heap[childIndex] && parentIndex >= 0){  //check to make sure it's a proper heap
            int temp = heap[parentIndex]; //start percolating up
            heap[parentIndex] = heap[childIndex];
            heap[childIndex] = temp;
            childIndex = parentIndex;
            parentIndex = (parentIndex-1)/2;
            }
        size+=1;
    }       

    /**
     * _Part 2: Implement this method._
     * 
     * Restore the heap condition to a tree rooted at the specified index when
     * the left and right subtrees obey the heap condition, but the root may 
     * not.  This is also known as "Bubble Down".
     * 
     * That is, given the specified index, and the fact that the left and 
     * right subtrees are heaps (if they exist), ensure that the largest of 
     * these three nodes get's swapped with the root, and then recursively 
     * restore the heap condition for the subtree with the element that was 
     * moved from the root.
     * 
     * In essence, this method bubbles a value down from the root until the 
     * heap condition is restored.
     * 
     * @param index
     *            the root tree to restore
     */
    public void maxHeapify(int index) {
        // TODO: implement this
        int left, right, large, tmp;            // declare variables left child, right child, largest node, temp for swap
        int i = index;
        left = 2 * i + 1;           // left child
        right = 2 * i + 2;                  // right child

        if(left <= heap.length-1 && heap[left] > heap[i])       // find smallest child
                large = left;               // save index of smaller child
        else
            large = i;

        if(right <= heap.length-1 && heap[right] > heap[large])
                large = right;                  // save index of smaller child

        if(large != i)              // swap and percolate, if necessary
        {
                tmp = heap[i];              // exchange values at two indices
                heap[i] = heap[large];
                heap[large] = tmp;
                maxHeapify(large);}
    }

    /**
     * _Part 3: Implement this method._
     * 
     * Removes the maximum valued item from the heap and restores the heap
     * condition. If the heap is empty, this method should throw
     * a NoSuchElementException
     * 
     * This function is performed by:
     * 
     * 1. removing the root of the heap 
     * 2. placing element from the end of the heap at the root 
     * 3. calling maxHeapify to restore the heap condition 
     * 4. making sure the size is updated
     * 
     * @return the highest valued item from the heap
     * @throws NoSuchElementException if called on an empty heap
     */
    public int extractMax() {
        // TODO: implement this
        if (size < 1){
            //throw no such element
            throw new NoSuchElementException();
        }
        int max = heap[0];
        heap[0] = heap[size-1];
        size = size-1;
        maxHeapify(0);
        return max;
    }

    /**
     * _Part 4: Implement this method._
     * 
     * Checks to make sure that the *max* heap condition is upheld on a 
     * given array of integers.
     * 
     * HINT: Full credit will be given on this one if you implement this 
     * method as a *recursive* function. It will probably make sense to 
     * create a private method that takes another argument (e.g., the index 
     * of the heap's root) to indicate where the checking should begin.
     * 
     * My private method has the following signature: 
     * private static boolean check(int [] arry, int rootindx, int sz)
     * 
     * 
     * @param array
     *            the array of data to check
     * @param size
     *            the number of elements 'in' the heap (starting at index 0)
     * @return true if the *max* heap condition is upheld
     */
    public static boolean checkHeapCondition(int[] array, int size) {
        // TODO: implement this
        if (array != null)
               return helpCheck(array,0, size);
          return false;
    }
    //Helper method
    private static boolean helpCheck(int[] arr, int i, int size) {
        //Base case
        if (i == size-1)
            return true;
        //2nd base case
        if (2*i+1 >= size){
            return true;
        }
        // check if a parent's value is larger or equal to both of
        // its left child and right child
        else if (arr[i] >= arr[2*i + 1] && arr[i] >= arr[2*i + 2])
            return (helpCheck(arr, 2*i + 1, size) && helpCheck(arr, 2*i + 2,  size));
        else                                                                                                                                                                                                                                                                                                                                                                                                            
            return false;
    }
    /**
     * _Part 5: Implement this method._
     * 
     * Changes the value of an element in the heap. And bubbles the value
     * 
     * @param index
     *            the index of the item to be modified
     * @param newValue
     *            the new value of the specified item
     * @return the old value of that item
     * @throws IndexOutOfBoundsException if the specified index is invalid
     */
     public int updateValue(int index, int newValue) {    
         // TODO: implement this
        int parent = (index-1)/2;
        int leftChild = (2*index +1);
        int rightChild = (2*index+2);
         if (heap == null || index >= size ){
             throw new IndexOutOfBoundsException();}

         int oldValue = heap[index];
         heap[index] = newValue;
         while (heap[parent] < heap[index] && parent >= 0 ){
            int temp = heap[parent]; 
            heap[parent] = heap[index];
            heap[index] = heap[temp];
            index = parent;
            parent = (parent-1)/2;
         }
         //We need to check to see if the children don't exist
             if (heap[leftChild] > heap[index] || heap[rightChild] > heap[index]){
             maxHeapify(index);
             return oldValue;

         }
         else return oldValue;
         }

     }

Answer 1

方法System.out.print(Object o) 使用参数Object 的toString() 方法。如果您没有重写此方法来提供自定义行为，它将使用父方法(在本例中为默认的 Object.toString() )。

要打印 MaxHeap 的值，请重写它的 toString 方法，返回一个您想要表示此类实例的 String。例如:

@Override
public String toString(){
    return java.util.Arrays.toString(heap);
}