java - 用户已经创建了 Heap 后，如何使用 HeapSort 方法？

Question

大家好，我正在为我的编程课做实验作业，我们必须创建一个堆，用户可以在其中将整数输入数组然后显示它，然后我们假设使用这些相同的值并很好地使用 HeapSort第一部分相当简单，我每次尝试调用 HeapSort 方法对数组进行排序时都遇到了问题，我遇到了这个错误

Exception in thread "main" java.lang.NullPointerException
at HeapApp.heapSort(HeapApp.java:11)
at HeapApp.main(HeapApp.java:88)

错误具体指出

int count = hp.length; 

和

HeapApp.heapSort(HP);

请帮忙!这是我这门课最后的作业之一!

堆类

import java.util.ArrayList;
import java.util.NoSuchElementException;


public class Heap<T extends Comparable<T>> {

private  ArrayList<T> items;


public Heap() {
    items = new ArrayList<T>();
}

private void siftUp() {
    int k = items.size() - 1;
    while (k > 0) {
        int p = (k-1)/2;
        T item = items.get(k);
        T parent = items.get(p);
        if (item.compareTo(parent) > 0) {
            // swap
            items.set(k, parent);
            items.set(p, item);

            // move up one level
            k = p;
        } else {
            break;
        }
    }
}

public void insert(T item) {
    items.add(item);
    siftUp();
}

private void siftDown() {
    int k = 0;
    int l = 2*k+1;
    while (l < items.size()) {
        int max=l, r=l+1;
        if (r < items.size()) { // there is a right child
            if (items.get(r).compareTo(items.get(l)) > 0) {
                max++;
            }
        }
        if (items.get(k).compareTo(items.get(max)) < 0) {
                // switch
                T temp = items.get(k);
                items.set(k, items.get(max));
                items.set(max, temp);
                k = max;
                l = 2*k+1;
        } else {
            break;
        }
    }
}

public T delete() 
throws NoSuchElementException {
    if (items.size() == 0) {
        throw new NoSuchElementException();
    }
    if (items.size() == 1) {
        return items.remove(0);
    }
    T hold = items.get(0);
    items.set(0, items.remove(items.size()-1));
    siftDown();
    return hold;
}

public int size() {
    return items.size();
}

public boolean isEmpty() {
    return items.isEmpty();

}

public String toString() {
    return items.toString();
}


}

import java.util.Scanner;


public class HeapApp {



/**
 * @param args
 */
public static void main(String[] args) {
    Heap<Integer> hp = new Heap<Integer>();


    Scanner sc = new Scanner(System.in);
    HeapApp HP = new HeapApp();
    System.out.print("Enter next int, 'done' to stop: ");
    String line = sc.next();

    while (!line.equals("done")) {
        hp.insert(Integer.parseInt(line));
        System.out.println(hp);
        System.out.print("Enter next int, 'done' to stop: ");
        line = sc.next();
    }

    while (hp.isEmpty()) {
        //int max = hp.delete();
        System.out.println(hp);
    }


    System.out.println(hp);
    HP.heapSort(HP);
    System.out.println("After sorting " + hp);

 }




private static int [] hp;



public static void heapSort(HeapApp HP){
        int count = hp.length;

        //first place a in max-heap order
        heapify(hp, count);

        int end = count - 1;
        while(end > 0){
            //swap the root(maximum value) of the heap with the
            //last element of the heap
            int tmp = hp[end];
            hp[end] = hp[0];
            hp[0] = tmp;
            //put the heap back in max-heap order
            siftDown(hp, 0, end - 1);
            //decrement the size of the heap so that the previous
            //max value will stay in its proper place
            end--;
        }
    }

    public static void heapify(int[] hp, int count){
        //start is assigned the index in a of the last parent node
        int start = (count - 2) / 2; //binary heap

        while(start >= 0){
            //sift down the node at index start to the proper place
            //such that all nodes below the start index are in heap
            //order
            siftDown(hp, start, count - 1);
            start--;
        }
        //after sifting down the root all nodes/elements are in heap order
    }

    public static void siftDown(int[] hp, int start, int end){
        //end represents the limit of how far down the heap to sift
        int root = start;

        while((root * 2 + 1) <= end){      //While the root has at least one child
            int child = root * 2 + 1;           //root*2+1 points to the left child
            //if the child has a sibling and the child's value is less than its sibling's...
            if(child + 1 <= end && hp[child] < hp[child + 1])
                child = child + 1;           //... then point to the right child instead
            if(hp[root] < hp[child]){     //out of max-heap order
                int tmp = hp[root];
                hp[root] = hp[child];
                hp[child] = tmp;
                root = child;                //repeat to continue sifting down the child now
            }else
                return;
        }
    }

}

Answer 1

  private static int [] hp; is null 

在访问此行之前验证您是否初始化了 hp 数组

   int count = hp.length;

请引用链接

How do I declare and initialize an array in Java?

How to initialize an array in Java?

如果你想使用动态数组那么请引用这里

how to use an array list?