Как сложить Макс-кучу?

Question

Я пытаюсь реализовать Max-heap с двумя методами insert и extract_max. Но extract_max в настоящее время не работает должным образом, поскольку не извлекает наибольшее целое число в куче, что, как я полагаю, связано с heapify. Я пытался отлаживать в течение нескольких часов, но не могу понять, где это идет не так. Любой вклад будет высоко оценен.

class Heap {
    int heap_array[];
    int n_elems = 0;
    int capacity;

    // Constructor
    Heap(int _capacity) {
        capacity = _capacity;
        heap_array = new int[capacity];
    }


    /**
     * Private method for maintaining the heap.
     * @param i, index of the element to heapify from
     **/
    private void heapify(int i) {
        int left = 2*i + 1;
        int right = 2*i+ 2;
        int largest = i;
        //if left ≤ heap_length[A] and A[left] > A[largest] then:
        if (left <= n_elems && heap_array[left] > heap_array[largest]) {
            largest = left;
            //System.out.println("largest = left");
        }

        //if right ≤ heap_length[A] and A[right] > A[largest] then:
        if (right <= n_elems && heap_array[right] > heap_array[largest]) {
            //System.out.println("largest = right");
            largest = right; 
        }
        //if largest ≠ i then:
        if (largest != i) { 
            int swap = heap_array[i]; 
            heap_array[i] = heap_array[largest]; 
            heap_array[largest] = swap; 

            // Recursively heapify the affected sub-tree 
            heapify(largest); 
        } 
    }

    /**
     * Add an element to the heap and ensure the heap property
     * Throws an exception if trying to add elements to a full heap.
     * @param x Element to add
     */
    public void insert(int x) throws Exception {
        if(is_full()) {
            throw new Exception("The heap is full");
        } else {
            // Insert the element at end of Heap 
            heap_array[n_elems++] = x; 
            //n_elems++;
            // Heapify from root
            heapify(0); 


        }

    }


   public int extract_max() throws Exception {
    //Get the largest
       // Get the last element 
    int root = heap_array[0];

       int lastElement = heap_array[n_elems]; 

       // Replace root with first element 
       heap_array[0] = lastElement; 

       // Decrease size of heap by 1 
       n_elems--;

       // heapify the root node 
       heapify(0);

       // return new size of Heap 
       return root;

   }

    public int capacity() {
        return capacity;
    }

    public int size() {
        return n_elems;
    }

    public boolean is_empty() {
        return n_elems == 0;
    }

    public boolean is_full() {
        return n_elems == capacity;
    }

    public void print() {
        for(int i = 0; i < n_elems; i++) {
            System.out.println(heap_array[i]);
        }
    }





    /**
     * Remove and return largest element, and maintain the heap property.
     * Throws an exception if trying to extract an element from an empty heap.
     */



    /**
     * For convenience, a small program to test the code.
     * There are better ways of doing this kind of testing!
     * @throws Exception 
     *
     */
    static public void main(String args[]) throws Exception { // A simple test program
        // Declare two heaps. Both should work nicely!
        Heap h1 = new Heap(100);
        Heap h2 = new Heap(10);
        int data[] = {1, 4, 10, 14, 7, 9, 3, 8, 16};


        //
        // Insert 1 element to heap 1, and several to heap 2.
        //

        h2.insert(9);
        h2.insert(10);
        h2.insert(8);
        h2.insert(11);
        h2.insert(12);
        h2.insert(15);
        System.out.println("Size " + h2.size());
        h2.print();

        System.out.println("Max " + h2.extract_max());
    }  
}

Answer 1

Первая проблема в том, что ваш insert неверен. Просто добавление в конец и вызов heapify(0) не принесет вам никакой пользы. heapify собирается исследовать элемент root и его двух дочерних элементов, решить, что root является самым большим элементом, и выйти, ничего не делая. В результате вы просто последовательно добавляете элементы в список.

Чтобы вставить его в мак-кучу, выполните следующие действия:

1. Добавьте новый элемент в конец кучи.
2. Переместите элемент вверх кучи в правильное положение.

Так что insert должно выглядеть так:

public void insert(int x) throws Exception {
    if(is_full()) {
        throw new Exception("The heap is full");
    }
    // Insert the element at end of Heap 
    heap_array[n_elems++] = x; 

    // now sift it up
    int current = nelems-1;
    int parent = (current-1)/2;
    while (current > 0 && heap_array[current] > heap_array[parent]) {
        int swap = heap_array[parent];
        heap_array[parent] = heap_array[current];
        heap_array[current] = swap;
        current = parent;
        parent = (current-1)/2;
    }
}

Я думаю у вас также есть проблема в extract_max. У вас есть:

int lastElement = heap_array[n_elems];

Но последний элемент фактически имеет индекс n_elems-1]. Я думаю, вы хотите:

int lastElement = heap_array[n_elems-1];

Это имеет смысл, потому что если n_elems == 1, то единственным элементом в куче будет root, в heap_array[0];