java如何heapify Maxheap？

Question

我试图用两个方法insert和extract_max实现一个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将检查根元素及其两个子元素，确定根元素是最大的项，然后退出，什么也不做。因此，您只需按顺序将内容添加到列表中

要插入到最大堆中，请执行以下操作：

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;
    }
}

我想你在^{方面也有问题。你有：

int lastElement = heap_array[n_elems];

但最后一个元素实际上位于索引n_elems-1]。我想你想要：

int lastElement = heap_array[n_elems-1];

这是有意义的，因为如果n_elems == 1，那么堆中唯一的项将是根，在heap_array[0]