javagenericsdata-structuresmethodsmin-heap

BubbleDown function(min heap) not working


I have generated a minheap to this file but I think something I have missed but I can't identify what are the things I have missed. I have missed something on --private void bubbleDown() { }-- section but I can't find what are the things missed by me.

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

        }

}

this code used generics and min heap functions.. i need to identify what is the wrong thing did by me on bubbleDown() section


Solution


  • Explanation

    The bubbleDown() method is not a different way to insert a node and move it to it's correct position in the Heap. When bubbleDown() is called it's job is to Heapify the Binary Tree from any state. So your attempt to write the method just by changing the condition from the bubbleUp() method isn't gonna help you.


    Extra

    Here is a video that can give you the idea of how bubbleDown is supposed to work.