最大堆(Java数组实现)

￡神魔★判官ぃ 2021-10-23 07:23 278阅读 0赞

## 最大堆 ##

data\[1\]开始存，data\[0\]空着不用。也可以把data\[0\]当成size来用。

public class MaxHeap<T extends Comparable<? super T>> {
        private T[] data;
        private int size;
        private int capacity;
    
        public MaxHeap(int capacity) {
            this.data = (T[]) new Comparable[capacity + 1];
            size = 0;
            this.capacity = capacity;
        }
    
        public int size() {
            return this.size;
        }
    
        public boolean isEmpty() {
            return size == 0;
        }
    
        public int getCapacity() {
            return this.capacity;
        }
    
        /**
         * @return 查看最大根(只看不删, 与popMax对比)
         */
        public T seekMax() {
            return data[1];
        }
    
        public void swap(int i, int j) {
            if (i != j) {
                T temp = data[i];
                data[i] = data[j];
                data[j] = temp;
            }
        }
    
        public void insert(T item) {
            size++;
            data[size] = item;
            shiftUp(size);
        }
    
        /**
         * @return 弹出最大根(弹出意味着删除, 与seekMax对比)
         */
        public T popMax() {
            swap(1, size--);
            shiftDown(1);
            return data[size + 1];
        }
    
        /**
         * @param child 孩子节点下角标是child，父节点下角表是child/2
         */
        public void shiftUp(int child) {
            while (child > 1 && data[child].compareTo(data[child / 2]) > 0) {
                swap(child, child / 2);
                child = child / 2;
            }
        }
    
        /**
         * @param a data数组中某个元素的下角标
         * @param b data数组中某个元素的下角标
         * @return 哪个元素大就返回哪个的下角标
         */
        private int max(int a, int b) {
            if (data[a].compareTo(data[b]) < 0) {//如果data[b]大
                return b;//返回b
            } else {//如果data[a]大
                return a;//返回a
            }
        }
    
        /**
         * @param a data数组中某个元素的下角标
         * @param b data数组中某个元素的下角标
         * @param c data数组中某个元素的下角标
         * @return 哪个元素大就返回哪个的下角标
         */
        private int max(int a, int b, int c) {
            int biggest = max(a, b);
            biggest = max(biggest, c);
            return biggest;
        }
    
    
        /**
         * @param father 父节点下角标是father,左右两个孩子节点的下角表分别是：father*2 和 father*2+1
         */
        public void shiftDown(int father) {
            while (true) {
                int lchild = father * 2;//左孩子
                int rchild = father * 2 + 1;//右孩子
                int newFather = father;//newFather即将更新，父、左、右三个结点谁大，newFather就是谁的下角标
    
                if (lchild > size) {//如果该father结点既没有左孩子，也没有右孩子
                    return;
                } else if (rchild > size) {//如果该father结点只有左孩子，没有右孩子
                    newFather = max(father, lchild);
                } else {//如果该father结点既有左孩子，又有右孩子
                    newFather = max(father, lchild, rchild);
                }
    
                if (newFather == father) {//说明father比两个子结点都要大，表名已经是大根堆，不用继续调整了
                    return;
                } else {//否则，还需要继续调整堆，直到满足大根堆条件为止
                    swap(father, newFather);//值进行交换
                    father = newFather;//更新father的值，相当于继续调整shiftDown(newFather)
                }
            }
        }
    
        public static void main(String[] args) {
            //创建大根堆
            MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
            //向堆里存
            for (int i = 0; i < 100; i++) {
                maxHeap.insert((int) (Math.random() * 100));
            }
    
            //创建数组
            Integer[] arr = new Integer[100];
            //从堆里取，放进数组里
            for (int i = 0; i < 100; i++) {
                arr[i] = maxHeap.popMax();
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    }

##  最大堆：shiftDown()函数与上面不一样 ##

public class MaxHeap<T extends Comparable<? super T>> {
        private T[] data;
        private int size;
        private int capacity;
    
        public MaxHeap(int capacity) {
            data = (T[]) new Comparable[capacity + 1];
            this.capacity = capacity;
            size = 0;
        }
    
        public int size() {
            return size;
        }
    
        public boolean isEmpty() {
            return size == 0;
        }
    
        public void insert(T item) {
            data[size + 1] = item;
            size++;
            shiftUp(size);
        }
    
        /**
         * @return 弹出最大根(弹出意味着删除, 与seekMax对比)
         */
        public T popMax() {
            T ret = data[1];
            swap(1, size);
            size--;
            shiftDown(1);
            return ret;
        }
    
        /**
         * @return 查看最大根(只看不删, 与popMax对比)
         */
        public T seekMax() {
            return data[1];
        }
    
        public void swap(int i, int j) {
            if (i != j) {
                T temp = data[i];
                data[i] = data[j];
                data[j] = temp;
            }
        }
    
        public void shiftUp(int k) {
            while (k > 1 && data[k / 2].compareTo(data[k]) < 0) {
                swap(k, k / 2);
                k /= 2;
            }
        }
    
        public void shiftDown(int father) {
            while (2 * father <= size) {
                int newFather = 2 * father;
                if (newFather + 1 <= size && data[newFather + 1].compareTo(data[newFather]) > 0) {//data[j] data[j+1]两者取大的那个
                    newFather = newFather + 1;
                }
                if (data[father].compareTo(data[newFather]) >= 0) {
                    break;
                } else {
                    swap(father, newFather);//值进行交换
                    father = newFather;//newFather是(2*father)或者是(2*father+1),也就是继续shiftDown(newFather);
                }
            }
        }
    
        public static void main(String[] args) {
            //创建大根堆
            MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
            //向堆里存
            for (int i = 0; i < 100; i++) {
                maxHeap.insert((int) (Math.random() * 100));
            }
    
            //创建数组
            Integer[] arr = new Integer[100];
            //从堆里取，放进数组里
            for (int i = 0; i < 100; i++) {
                arr[i] = maxHeap.popMax();
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    }

转载于:https://www.cnblogs.com/noKing/p/7954898.html