在 java 中使用 comparable for MaxHeap 中的 Bubble up

Question

我试图在 java 中插入一个 maxHeap，然后将对象冒泡。这就是我所做的，我不确定我应该如何处理冒泡方法。

我明白冒泡背后的算法，如下：

获取父节点
查看L_childNode是否小于父节点。如果是，则用 L_child.
查看R_childNode是否小于父节点。如果是，则用 L_child.

请指出我做错了什么？

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

Answer 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

在 java 中使用 comparable for MaxHeap 中的 Bubble up

using comparable in java for Bubble up in MaxHeap

java

heap

max-heap