Проблема в реализации метода build-heap для min-heap - PullRequest
Новая
       17

Проблема в реализации метода build-heap для min-heap

0 голосов
/ 31 октября 2019

Я пытаюсь создать алгоритм минимальной кучи и могу заставить работать методы insert, delete, pop, trickleUp и trickleDown, но у меня проблемы с конструктором, который должен использовать алгоритм build-heap.

Метод прост, так как он просто хочет построить новую кучу из массива. Кроме того, я собираюсь реализовать алгоритм сортировки кучи, который требует, чтобы heapify () поддерживал свойство кучи. Но я застрял, есликонструктор и поэтому не уверен, что мой heapify () правильный или нет. Как только конструктор сработает, сортировка кучи станет простой в реализации. 

/** Construct a new heap from an array of unsorted data.
 * 
 * Complexity: O(n)
 * @param data       Array to populate the heap from
 * @param capacity   Capacity of the heap (must be >= data.length)
 * @param comparator Comparator to use when comparing elements
     */

MinHeap(T[] data, int capacity) {


    for(int i = data.length/2 + 1; i >= 0;i--){       
    heapify(data,i);       
  }
 }


public  void heapify(Comparable[] data,int i){

    int smallest = i;

    if(size >left(i) && data[left(i)].compareTo(data[i])< 0 )

    {
        smallest = left(i);
    }
    else{
        smallest = i;
    }

    if(size>right(i) && data[right(i)].compareTo(data[i])< 0)

    {
        smallest = right(i);
    }

    if(smallest !=i)
    {
        Comparable temp = data[i];
        data[i] = data[smallest];
        data[smallest] = temp; 
        heapify(data,smallest);
    }
}

////// Тестовый файл 

@Test public void testArrayConstruction() {
    System.out.println("array construction");

    for(int i = 0; i < 100; ++i) {
        Integer[] data = randomArray(i);
        MinHeap h = new MinHeap(data, i*2);

        assertEquals(h.capacity(), i * 2);
        assertEquals(h.size(), i);

        // Collections has min/max, but of course those don't work on arrays.
        Integer smallest = data[0];
        for(Integer x : data)
            if(x < smallest)
                smallest = x;                        

        checkHeapOrder(h);
        assertEquals(h.top(), smallest);           
    }

Integer[] randomArray(int size) {
    Integer[] arr = new Integer[size];
    for (int i = 0; i < size; ++i) {
        arr[i] = Math.round((float) Math.random() * Integer.MAX_VALUE);
    }

    return arr;
}

 void checkHeapOrder(MinHeap h) {
    assertTrue(h != null);

    for(int i = 1; i < h.size() / 2; ++i) 
        assertTrue("Heap order property is broken at element at position " 
 + i,
                   h.data[i].compareTo(h.data[i*2]) < 0 && 
                   h.data[i].compareTo(h.data[i*2 + 1]) < 0);
}

Это строка в тестовом файле, где возникает проблема: целое число наименьшее = данные [0];Здесь метод не может инициализировать наименьший 0-й элемент массива. Я пытался настроить программу, но каждый раз получал одну и ту же ошибку. Я считаю, что тестовый файл также может быть неправильным, поэтому просто хочу убедиться. 

testArrayConstruction caused an Error: 0
java.lang.ArrayIndexOutOfBoundsException

1 Ответ

0 голосов
/ 31 октября 2019

Вы не включили код для randomArray () ...

Если предположить, что этот метод создает рандомизированный массив с размером, равным аргументу метода, то ваш вызов 

Integer[] data = randomArray(0);

создает массив размером 0.

Вы не можете прочитать элемент с индексом 0, потому что массив размера 0 не имеет элементов.

...