嘿伙计们，我正在为我的编程课做一个实验室作业，我们必须创建一个堆，用户将整数输入到数组中然后显示它，然后我们假设使用这些相同的值并在第一部分很好地使用 HeapSort相当容易，我每次尝试调用 HeapSort 方法以对数组进行排序时遇到问题我想出了这个错误
HeapApp.heapSort(HeapApp.java:11)
处 HeapApp.main( HeapApp.java:88) 处的线程“main”java.lang.NullPointerException中的异常
错误特别指出
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;
}
}
}