Используя сопоставимый в Java для Bubble в MaxHeap

Question

Я пытаюсь вставить в MaxHeap в Java, а затем всплыть объект. Это то, что я сделал, я не уверен, как я должен подходить к методу пузыря.

Я понимаю алгоритм за пузырем, который заключается в следующем:

1. получить родительский узел
2. посмотрим, меньше ли L_childNode, чем родительский узел. Если да, то поменяйте родительский элемент с L_child.
3. посмотрим, меньше ли 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