0

I am trying to insert in a maxHeap in java and then bubble up the object. This is what I have done, I am not sure how I should approach the bubble up method.

I do understand the algorithm behind bubble up, which is as follows:

  1. get parent node
  2. see if L_childNode is less than parent Node. If Yes, then swap parent with L_child.
  3. see if R_childNode is less than parent Node. If Yes, then swap parent with L_child.

Please point out what am I doing wrong?

private int getLeftChild(int n){
        return x*2+1;
    }

    private int getRightChild(int n){
        return x*2+2;
    }

    public void insert (E item) {
        //Integer pos_lastEl= new Integer (heapArray.lastElement());
        heapArray.add(item);


        bubbleUp(item);
    }

    //To use to reheap up when item inserted at end of heap (complete tree)
    private void bubbleUp(E x){
        int place = heapArray.size()-1;
        int parent=(place-1)/2;
        if ((parent>=0) && (parent.compareTo(heapArray.get(getLeftChild))<0)){
            swap(place,parent);
        }else ((parent>=0 && (parent.compareTo(heapArray.get(getRightChild))<0))){
            swap(place,parent);
        }
    }

    //swaps two objects at index i and j
    private void swap(int i, int j){
        int max=heapArray.size();
        if(i>=0 && i<max && j>=0 && j<max){
            E temp=heapArray.get(i);
            //put J item in I
            heapArray.set(i,heapArray.get(j));
            heapArray.set(j,temp);
        }
    }
4

1 回答 1

1

您的主要问题是使用if而不是while将新添加的元素冒泡到正确的位置。

您的代码中还有一些其他问题，抱歉，我不得不进行一些重构以使其足够干净：

public class MaxHeapTest<E extends Comparable<E>> {
    List<E> heapArray = new ArrayList<>();

    public static void main(String... args) {
        int N = 13;
        MaxHeapTest<Integer> maxHeap = new MaxHeapTest();
        for (int i = 0; i < N; ++i) { // ascending;
            maxHeap.insert(i);
        }

        while (!maxHeap.isEmpty()) { // descending now;
            System.out.print(maxHeap.delMax() + " ");
        }
    }

    public E delMax() {
        E e = heapArray.get(0);
        swap(0, heapArray.size() - 1);
        heapArray.remove(heapArray.size() - 1);
        sinkDown(0);
        return e;
    }

    public void insert(E item) {
        heapArray.add(item);
        bubbleUp(item);
    }

    public boolean isEmpty() {
        return heapArray.isEmpty();
    }

    private void bubbleUp(E x) {
        int k = heapArray.indexOf(x);
        int j = (k - 1) / 2;
        while (j >= 0) {
            if (heapArray.get(j).compareTo(heapArray.get(k)) < 0) {
                swap(k, j);
                k = j;
                j = (j - 1) / 2;
            } else break;
        }
    }

    private void sinkDown(int k) {
        int j = 2 * k + 1;
        while (j < heapArray.size()) {
            if (j < heapArray.size() - 1 && heapArray.get(j).compareTo(heapArray.get(j + 1)) < 0) j++;
            if (heapArray.get(k).compareTo(heapArray.get(j)) < 0) {
                swap(k, j);
                k = j;
                j = 2 * j + 1;
            } else break;
        }
    }

    private void swap(int i, int j) {
        E temp = heapArray.get(i);
        heapArray.set(i, heapArray.get(j));
        heapArray.set(j, temp);
    }
}

之后maxHeap，我们可以轻松地将降序输出为：

12 11 10 9 8 7 6 5 4 3 2 1 0
于 2018-07-27T02:49:49.467 回答