Реализация max-Heap в Java с помощью операций max-heapify и Build-max-heap - PullRequest
Новая
       68

Реализация max-Heap в Java с помощью операций max-heapify и Build-max-heap

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

Я получаю неправильный вывод, пожалуйста, скажите мне, где я не прав. Инструктор сказал, что для сортировки мы должны использовать псевдокод Clrs, функции buildMaxHeap и maxHeapify. Пожалуйста, помогите мне с этим кодом, так как мое назначение должно быть выполнено всего за 1 день.

Вопрос:

Как реализовать max-Heap в Java с операциями max-heapify а Build-max-heap? 

public class MaxHeap {

    private int[] HeapArray;
    public int[] getHeapArray() {
        return HeapArray;
    }

    private int size;
    private int maxsize;
    private int largest;

    private static final int FRONT = 1;

    public MaxHeap(int maxsize)
    {
        this.maxsize = maxsize;
        this.size = maxsize;
        HeapArray = new int[maxsize];
        //initialize heap array to a set of numbers, rearranged a little
        for (int i = FRONT; i < HeapArray.length; i++) {
            HeapArray[i] = maxsize-i;
        }
    }

    // Return the index of the parent of the node currently at pos
    private int parent(int pos)
    {
        return (pos / 2);
    }

    // Return the index of the leftchild of the node currently at pos
    private int leftChild(int pos)
    {
        return (2 * pos);
    }

    // Return the index of the rightchild of the node currently at pos
    private int rightChild(int pos)
    {
        return (2 * pos) + 1;
    }


    //Function to heapify the node at position i, up to the position n
    private void maxHeapify(int i, int n)
    {

        if(leftChild(i) <= n && HeapArray[leftChild(i)] > HeapArray[i] ) {
            largest = leftChild(i);

        }
        else
            largest = i;

        if(rightChild(i) <= n &&  HeapArray[rightChild(i)] > HeapArray[i] ) {
            largest = rightChild(i);

        }
        if(largest != i) {
            swap(HeapArray[i], HeapArray[largest]);
            maxHeapify(largest, n);
        }

     }



    public void buildMaxHeap() {

        int end = HeapArray.length/2;
        for(int i = end - 1; i >= 1; i--) {
            maxHeapify(i, HeapArray.length - 1);
        }


    }

    public void sort() {
        buildMaxHeap();
        int size = HeapArray.length - 1;
        for(int i = size; i >= 2 ; i--) {
            swap(HeapArray[1], HeapArray[i]);
            maxHeapify(1, i - 1);

        }

    }



    // Swap two nodes of the heap at index first second
    private void swap(int first, int seconds)
    {
        int tmp;
        tmp = HeapArray[first];
        HeapArray[first] = HeapArray[seconds];
        HeapArray[seconds] = tmp;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {

        int SIZE = 30;
        MaxHeap heap = new MaxHeap(SIZE);
        heap.sort();
        int[] heapArr = heap.getHeapArray();

        assertEquals(heapArr[0], 0);
        assertEquals(heapArr[1], 1);
        assertEquals(heapArr[2], 2);
        assertEquals(heapArr[SIZE-1], SIZE-1);
        assertEquals(heapArr.length, SIZE);
    }

}
...