大根堆实现

柔光的暖阳◎ 2022-07-12 08:13 219阅读 0赞

堆：有两种，一种是大根堆，另一种是小根堆。大根堆的意思是在跟的位置那个数是最大的。同理，小根堆的根元素是最小的。  
堆是一个满的二叉树，除了最后一个节点可能不是满的。所以用数组去数组去实现它。一个节点的index为i,则这个节点的两个子节点的下标应该为2\*i+1和2\* i+2;父结点那就是(i-1)/2;

下面是大根堆代码的实现：

public class MyHeap<E extends Comparable<E>> { 
        private Object[] array;
        private int maxSize;
        private int currentSize;
    
        public MyHeap(int max){
            maxSize = max;
            array = new Object[max];
            currentSize = 0;
        }
        public boolean isEmpty(){
            return currentSize == 0;
        }
        /** * 插入节点 * @param e */
        public boolean  insert(E e){
            if(currentSize == maxSize)
            return false;
            array[currentSize] = e;
            checkUp(currentSize++);
            return true;
        }
        /** * 向上移动函数 * @param i */
        private void checkUp(int i) {
            // TODO Auto-generated method stub
            int parent = (i-1)/2;
            E object = (E) array[i];
            /** * 说一下解决思路：插入的节点是在数组最后一个位置，需要拿到这个节点的父结点，也就是parent的位置 * 然后就跟父结点比较，如果比父结点大的话那就需要去交换，这里可能会忘了数组索引是要大于等于0的 * */
            while (i>0&&object.compareTo((E) array[parent])>0) {
                array[i] = array[parent];
                i = parent ;
                parent = (parent-1)/2;
            }
            array[i] = object;
        }
        public E remove(){
            E e = (E) array[0];
            array[0] = array[--currentSize];
            checkDown(0);
            return e;
        }
        /** * 使小的节点向下走 * @param i */
        private void checkDown(int i) {
            int laChrid;
            E e  = (E) array[i];
            while(i<currentSize/2){
                int left = 2*i+1;
                int right = left +1;
                E e2 = (E) array[left];
                if(right<currentSize&&e2.compareTo((E)array[right])<0)
                    laChrid = right;
                else {
                    laChrid = left;
                }
                if(e.compareTo((E)array[laChrid])>=0)
                    break;
                array[i] = array[laChrid];
                i = laChrid;
            }
            array[i] = e;
        }
    }