泡泡功能（最小堆）不起作用

Question

我已经为这个文件生成了一个Minheap，但我认为我错过了一些东西，但我无法确定我错过了什么。我错过了 - 私人void bubbledown（）{} - 部分，但我找不到我错过了什么。

        private int default_size = 100; // how big the heap should be

        private T[] array;
        private int size;

        public Heap() {
            @SuppressWarnings("unchecked")
            T[] tmp = (T[]) (new Comparable[default_size]);
            array = tmp;
            size  = 0;
        }

        boolean isRoot(int index) { return (index == 0);   }
        int leftChild(int index)  { return 2 * index + 1;  }
        int parent(int index)     { return (index - 1) / 2; }
        int rightChild(int index) { return 2 * index + 2;   }
        T myParent(int index) { return array[parent(index)]; }
        T myLeftChild(int index) { return array[leftChild(index)]; }
        T myRightChild(int index) { return array[rightChild(index)]; }
        boolean hasLeftChild(int i) { return leftChild(i) < size-1; }
        boolean hasRightChild(int i){ return rightChild(i) < size-1; }

        private void swap(int a, int b) {
            T tmp = array[a];
            array[a] = array[b];
            array[b] = tmp;
        }

        public boolean isEmpty() { return (size == 0); }


        /* adding heap */
        public void add(T value) {
            if(size == default_size) throw new IllegalStateException("Full array");
            array[size++] = value;
            bubbleUp();
        }

        public void bubbleUp() {
            if(size == 0) throw new IllegalStateException("Shape error");
            int index = size - 1;
            while(!isRoot(index)) {
                if(myParent(index).compareTo(array[index]) <= 0) break;
                /* else part */
                swap(parent(index), index);
                index = parent(index);
            }
        }

        /* removing */

        public T remove() {
            if(isEmpty()) return null;
            T res = array[0]; /* root */
            array[0] = array[size-1];
            size --;
            bubbleDown();
            return res;
        }

// i think this section having wrong something
        private void bubbleDown() {
        int parent = 0;
        int leftChild = 2*parent + 1;
        int rightChild = 2*parent + 2;

        int choice = compareAndPick(leftChild, rightChild);

        while (choice != -1)
        {
            swap(choice, parent);
            parent = choice;
            choice = compareAndPick(2*choice+1, 2*choice+2);
        }
    }
    private int compareAndPick(int leftChild, int rightChild)
    {
        if (leftChild >= default_size || array[leftChild] == null) return -1;
        if (array[leftChild].compareTo(array[rightChild]) <= 0 || (array[rightChild] == null))
            return leftChild;
        return rightChild;
    }


        public void show() {
            for(int i=0; i<size; i++)
                System.out.print(array[i] + " ");
            System.out.println("=======");
        }


        public static void main(String [] args) {
            Heap<Integer> heap = new Heap<Integer>();

            for(int i=0; i<10; i++) {
                heap.add((Integer)(int)(Math.random() * 100));
                heap.show();
            }


            System.out.println("You should see sorted numbers");
            while(!heap.isEmpty()) {
                System.out.print(heap.remove());
                System.out.print(" ");
                heap.show();
            }
            System.out.println();

        }

}

此代码使用了通用和最小堆功能。.我需要确定我在BubbleDown（）e节上做了什么是错误的事情

Answer 1

---

说明

bubbledown（）方法不是插入节点并将其移至堆中正确位置的方法。当bubbledown（）称为heapify来自任何状态的二进制树。因此，您尝试仅通过从bubbleup（）方法更改条件来编写该方法无法帮助您。

---

额外的

是a video 可以为您提供bubbledown 应该工作。

---