Как использовать метод HeapSort после того, как пользователь уже создал кучу?

Привет, ребята, я работаю над лабораторным заданием для своего класса программирования, и нам нужно создать кучу, в которой пользователь вводит целые числа в массив, а затем отображает его, затем мы предполагаем использовать те же значения и использовать HeapSort в первой части. было довольно легко, у меня возникли проблемы с вызовом метода HeapSort для сортировки массива каждый раз, когда я сталкиваюсь с этой ошибкой

Исключение в потоке "main" java.lang.NullPointerException
в HeapApp.heapSort(HeapApp.java:11)
в 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;
        }
    }

}

person Bartholomew Allen    schedule 09.12.2015    source источник
comment
Исправьте форматирование, выбрав код и нажав кнопку кода. Также объясните, из какой строки исходит исключение.   -  person Sami Kuhmonen    schedule 09.12.2015


Ответы (2)


  private static int [] hp; is null 

Убедитесь, что вы инициализировали массив hp перед доступом к этой строке

   int count = hp.length;

Пожалуйста, обратитесь по ссылкам

Как объявить и инициализировать массив в Java?

Как инициализировать массив в Java?

Если вы хотите использовать динамический массив, обратитесь сюда

как использовать список массивов?

person Prabhakaran Ramaswamy    schedule 09.12.2015
comment
Пожалуйста, приведите пример того, что вы имеете в виду, пожалуйста - person Bartholomew Allen; 09.12.2015

Вот пример программы для сортировки кучи. В примере используется int [] в качестве входных данных для сортировки кучи. Вызовите метод doHeapSort и передайте int[]

public static void doHeapSort(int [] inputArray)
{
    for(int i = 0; i < inputArray.length; i++)
    {
        keepMaxHeapFindingParentElement(i, inputArray);
    }
    sortAndMaintainHeap(inputArray, inputArray.length - 1);
}


private static void sortAndMaintainHeap(int [] inputArray, int lastElementIndex)
{
    if(lastElementIndex <= 0)
    {
        return;
    }
    swap(inputArray, 0, lastElementIndex);
    lastElementIndex--;
    keepMaxHeapFindingChildElement(inputArray, 0, lastElementIndex);
    sortAndMaintainHeap(inputArray, lastElementIndex);
}

private static void keepMaxHeapFindingChildElement(int [] inputHeap, int currentElementIndex, int lastElementIndex)
{
    if(currentElementIndex >= lastElementIndex)
    {
        //no more child node
        return;
    }
    int child1Index = 2*currentElementIndex + 1;
    int child2Index = 2*currentElementIndex + 2;
    int childIndex = 0;
    if(child2Index <= lastElementIndex)
    {
        childIndex = inputHeap[child1Index] > inputHeap[child2Index] ? child1Index : child2Index;
    }
    else if(child1Index <= lastElementIndex)
    {
        childIndex = child1Index;
    }
    else
    {
        return;
    }
    if(inputHeap[currentElementIndex] < inputHeap[childIndex])
    {
        swap(inputHeap, currentElementIndex, childIndex);
        keepMaxHeapFindingChildElement(inputHeap, childIndex, lastElementIndex);
    }
    else
    {
        return;
    }
}

private static void keepMaxHeapFindingParentElement(int elementIndex, int [] inputHeap)
{
    if(elementIndex == 0)
    {
        // no more parent node
        return;
    }
    int parentElementIndex = (elementIndex - 1)/2;
    if(inputHeap[elementIndex] > inputHeap[parentElementIndex])
    {
        //swap child and parent
        swap(inputHeap, elementIndex, parentElementIndex);
        keepMaxHeapFindingParentElement(parentElementIndex, inputHeap);
    }
}
person Harbeer Kadian    schedule 09.12.2015