java实现数据结构08.01（堆详解代码之自定义最大堆）

r囧r小猫 2023-06-23 07:00 15阅读 0赞

## 自定义数组 ##

/** * @description: 数组类,E为泛型，可以使用任意对象 * @author: liangrui * @create: 2019-12-05 20:25 **/
    public class Array<E> { 
    
        //数据
        private E[] data;
        //实际数据个数
        private int size;
    
        /** * 有参构造函数 * @param capacity 数据容量 */
        public Array(int capacity){ 
            data=(E[]) new Object[capacity];
            size=0;
        }
    
        /** * 无参构造函数，this(10)代表调用有参构造函数，赋予容量10 */
        public Array(){ 
            this(10);
        }
    
        public Array(E[] arr){ 
            data=(E[])new Object[arr.length];
            size=arr.length;
            for (int i = 0; i < size; i++) { 
                data[i]=arr[i];
            }
        }
    
        /** * 重新设置数组容量，使数组具有可伸缩性 * @param newCapacity 设置的容量大小 */
        private void resetCapacity(int newCapacity){ 
            E[] newData=(E[]) new Object[newCapacity];
            for (int i = 0; i < size; i++) { 
                newData[i]=data[i];
            }
            data=newData;
        }
    
        /** * @return 获取数组中元素个数 */
        public int getSize(){ 
            return size;
        }
    
        /** * @return 获取数组的容量 */
        public int getCapacity(){ 
            return data.length;
        }
    
        /** * @return 判断数组是否为空，为空返回true，不为空返回false */
        public boolean isEmpty(){ 
            return size==0;
        }
    
        /** * 指定数组位置添加数据 * @param index 数组下标 * @param e 添加的数据 */
        public void add(int index,E e){ 
    
            //如果插入的位置下标小于0或者大于数组元素的数量，即不合法。抛出异常。
            if (index<0||index>size){ 
                throw new IllegalArgumentException("Add failed. Require index>=0 and index<=size.");
            }
    
            //如果数组元素等于数组容量，即数组已满,可以扩容2倍
            if(size==data.length){ 
                resetCapacity(2*data.length);
            }
    
            //从最后一个元素遍历到存储的下标，逐个把前一个的元素赋值到后一个，从而保证元素不丢失，且把要添加的index位置空出来
            for (int i = size-1; i >=index ; i--) { 
                data[i+1]=data[i];
            }
    
            //把e赋值到index所在的数组位置
            data[index]=e;
            //元素数量+1。
            size++;
        }
    
        /** * 从最后面添加数据 * @param e 添加的数据 */
        public void addLast(E e){ 
            add(size,e);
        }
    
        /** * 在数组最前面添加数据 * @param e 添加的数据 */
        public void addFirst(E e){ 
            add(0,e);
        }
    
        /** * 查询数组信息 * @return 返回数组信息 */
        @Override
        public String toString(){ 
            //创建StringBuilder对象，实现字符串拼接
            StringBuilder sb=new StringBuilder();
            //第一行为数组的元素个数和数组的容量
            sb.append(String.format("Array Size:%d. Array Capacity:%d.\n",size,data.length));
            //第二行为数组的数据
            sb.append("[");
            for (int i = 0; i < size; i++) { 
                sb.append(data[i]);
                //如果不是最后一个元素，拼接","
                if (i!=size-1){ 
                    sb.append(",");
                }
            }
            sb.append("]");
            //返回字符串
            return sb.toString();
        }
    
        /** * 获取指定下标的数据 * @param index 下标 * @return 返回对应数组中的数据 */
        public E get(int index){ 
            //非法索引
            if (index<0||index>=size){ 
                System.out.println(index);
                throw new IllegalArgumentException("Get failed. Index is Illegal.");
            }
            return data[index];
        }
    
        /** * 修改指定下标的数据 * @param index 下标 * @param e 修改后的数据 */
        public void set(int index,E e){ 
            //非法索引
            if (index<0||index>=size){ 
                throw new IllegalArgumentException("Set failed. Index is Illegal.");
            }
            data[index]=e;
        }
    
        /** * 查询数组中是否包含某元素 * @param e 查询的元素 * @return 存在返回true,不存在返回false */
        public boolean contains(E e){ 
            for (int i = 0; i < size; i++) { 
                //包含
                if (data[i].equals(e)){ 
                    return true;
                }
            }
            //遍历结束，不包含
            return false;
        }
    
        /** * 查询某元素的索引 * @param e 查询的元素 * @return 返回元素索引，元素不存在返回-1 */
        public int findIndex(E e){ 
            for (int i = 0; i < size; i++) { 
                if (data[i].equals(e)){ 
                    return i;
                }
            }
            return -1;
        }
    
        /** * 查询所有相同元素的索引 * @param e 元素 */
        public void findAllIndex(E e){ 
            StringBuilder sb=new StringBuilder();
            sb.append("AllIndex:");
            for (int i = 0; i < size; i++) { 
                if (data[i].equals(e)){ 
                    sb.append(i+" ");
                }
            }
            System.out.println(sb.toString());
        }
    
        /** * 删除指定索引的元素 * @param index 索引 */
        public E removeByIndex(int index){ 
            //非法索引
            if (index<0||index>=size){ 
                throw new IllegalArgumentException("Remove failed. Require index>=0 and index<size.");
            }
            E removeElement=data[index];
            //依次将(i+1)的元素赋值到i
            for (int i = index; i < size-1; i++) { 
                data[i]=data[i+1];
            }
            //元素个数-1
            size--;
            //设置为null,程序优化
            data[size]=null;
    
            //当元素个数小于容量的1/4，则减少容量为原来的1/2，且数组容量要大于1
            if (size<data.length/4&&data.length/2!=0){ 
                resetCapacity(data.length/2);
            }
            return removeElement;
        }
    
        /** * 删除第一个元素 */
        public E removeFirst(){ 
            return removeByIndex(0);
        }
    
        /** * 删除最后一个元素 */
        public E removeLast(){ 
            return removeByIndex(size-1);
        }
    
        /** * 删除指定元素 * @param e 指定的元素 */
        public E removeElement(E e){ 
            int index=findIndex(e);
            if (index==-1){ 
                throw new IllegalArgumentException("Remove failed.The element is nonexistent.");
            }else { 
                return removeByIndex(index);
            }
        }
    
        /** * 删除所有相同的元素e * @param e 要删除的元素 */
        public void removeAllElement(E e){ 
            int index=findIndex(e);
            if (index==-1){ 
                System.out.println("Remove failed.The element is nonexistent.");
            }else { 
                for (int i = 0; i < size; i++) { 
                    if (data[i].equals(e)){ 
                        removeByIndex(i);
                    }
                }
            }
        }
    
        /** * 交换两个元素 * @param i * @param j */
        public void swap(int i,int j){ 
            if (i<0||i>=size||j<0||j>=size){ 
                throw new IllegalArgumentException("Illegal Index.");
            }
            E e=data[i];
            data[i]=data[j];
            data[j]=e;
        }
    
    
    
    }

## 自定义最大堆（最大堆，也是一种二叉树，父永远比孩子大，基于数组创建最大堆） ##

/** * @description: 最大堆，也是一种二叉树，父永远比孩子大，基于数组创建堆 * @author: liangrui * @create: 2019-12-17 19:26 **/
    public class MaxHeap<E extends Comparable> { 
        private Array<E> array;
    
        /** * 有参构造函数 * @param capacity 容器大小 */
        public MaxHeap(int capacity){ 
            array=new Array<>(capacity);
        }
    
        /** * 无参构造函数 */
        public MaxHeap(){ 
            array=new Array<>();
        }
    
        public MaxHeap(E[] arr){ 
            array=new Array<>(arr);
            for (int i = parent(array.getSize()-1); i >=0 ; i--) { 
                shiftDown(i);
            }
        }
    
        /** * 获取元素个数 * @return */
        public int getSize(){ 
            return array.getSize();
        }
    
        /** * 查看堆是否为空 * @return */
        public boolean isEmpty(){ 
            return array.isEmpty();
        }
    
        /** * 获取父亲的下标 * @param index * @return */
        public int parent(int index){ 
            if (index<0||index>=array.getSize()){ 
                throw new IllegalArgumentException("Illegal index.");
            }
            return (index-1)/2;
        }
    
        /** * 获取左孩子下标 * @param index * @return */
        public int leftChildIndex(int index){ 
            return (index*2)+1;
        }
    
        /** * 获取有孩子下标 * @param index * @return */
        public int rightChildIndex(int index){ 
            return (index*2)+2;
        }
    
        /** * 添加元素 * @param e 添加的元素 */
        public void add(E e){ 
            array.addLast(e);
            shiftUp(array.getSize()-1);
        }
    
        /** * 如果新添加的元素比父亲大，则将新添加的元素与父亲互换 * @param i */
        private void shiftUp(int i) { 
            while (i>0&&array.get(i).compareTo(array.get(parent(i)))>0){ 
                array.swap(i,parent(i));
                i=parent(i);
            }
        }
    
        /** * 删除指定元素 * @param e */
        public void remove(E e){ 
            int index = array.findIndex(e);
            array.set(index,array.get(array.getSize()-1));
            array.removeLast();
            shiftDown(index);
        }
    
        // 取出堆中最大元素
        public E extractMax(){ 
    
            E ret = array.get(0);
    
            array.swap(0, array.getSize() - 1);
            array.removeLast();
            shiftDown(0);
    
            return ret;
        }
    
        /** * 如果新赋值的元素比孩子小，则新赋值的元素与最大的孩子互换 * @param index */
        private void shiftDown(int index) { 
            while(leftChildIndex(index) < array.getSize()){ 
                int j = leftChildIndex(index); // 在此轮循环中,data[k]和data[j]交换位置
                if( j + 1 < array.getSize() &&
                        array.get(j + 1).compareTo(array.get(j)) > 0 )
                    j ++;
                // data[j] 是 leftChild 和 rightChild 中的最大值
    
                if(array.get(index).compareTo(array.get(j)) >= 0 )
                    break;
    
                array.swap(index, j);
                index = j;
            }
        }
    
        /** * 替换最大的元素 * @param e * @return */
        public E replaceMax(E e){ 
            E bofore=array.get(0);
            array.set(0,e);
            int index = array.findIndex(e);
            shiftDown(index);
            return bofore;
        }
    
    
    
    }

## main测试 ##

import java.util.Random;
    
    public class Main { 
    
        private static double testHeap(Integer[] testData, boolean isHeapify){ 
    
            long startTime = System.nanoTime();
    
            MaxHeap<Integer> maxHeap;
            if(isHeapify)
                maxHeap = new MaxHeap<>(testData);
            else{ 
                maxHeap = new MaxHeap<>();
                for(int num: testData)
                    maxHeap.add(num);
            }
    
            int[] arr = new int[testData.length];
            for(int i = 0 ; i < testData.length ; i ++)
                arr[i] = maxHeap.extractMax();
    
            for(int i = 1 ; i < testData.length ; i ++)
                if(arr[i-1] < arr[i])
                    throw new IllegalArgumentException("Error");
            System.out.println("Test MaxHeap completed.");
    
            long endTime = System.nanoTime();
    
            return (endTime - startTime) / 1000000000.0;
        }
    
        public static void main(String[] args) { 
    
            int n = 1000000;
    
            Random random = new Random();
            Integer[] testData = new Integer[n];
            for(int i = 0 ; i < n ; i ++)
                testData[i] = random.nextInt(Integer.MAX_VALUE);
    
            double time1 = testHeap(testData, false);
            System.out.println("Without heapify: " + time1 + " s");
    
            double time2 = testHeap(testData, true);
            System.out.println("With heapify: " + time2 + " s");
    
            MaxHeap<Integer> maxHeap=new MaxHeap<>();
            for (int i = 0; i < 5; i++) { 
                maxHeap.add(i);
            }
    
            System.out.println(maxHeap.replaceMax(9));
    
            System.out.println(maxHeap.replaceMax(10));
        }
    }

## 测试结果： ##

> Test MaxHeap completed.  
> Without heapify: 1.0160211 s  
> Test MaxHeap completed.  
> With heapify: 0.8520585 s  
> 4  
> 9