精华内容
下载资源
问答
  • java大根堆和小根堆
    2022-02-21 19:20:18

    java使用优先队列实现大顶堆和小顶堆,默认是小根堆,当然记不住默认也没有关系

    小根堆创建

    PriorityQueue<Integer> minHeap = new PriorityQueue<>(k,(a,b) -> a-b);

    大根堆创建

    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k,(a,b) -> b-a);

    其中构造器中的k表示创建堆的大小,之后用Lambda表达式快速实现自定义排序

    更多相关内容
  • Java 中的大根堆和小根堆

    千次阅读 2019-09-02 22:34:15
    小根堆和大根堆 **完全二叉树:**完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时...

    小根堆和大根堆

    完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

    满二叉树:除了叶子节点外,每个节点的两个子节点都全的二叉树。

    小根堆:首先小根堆是一个完全二叉树,并且任何子树的最小值是它的根节点。

    大根堆:同理,大根堆也是一个完全二叉树,并且任何子树的最大值是它的根节点。

    Java 中现成的堆

    PriorityQueue:

    PriorityQueue<Integer> queue1 = 
    		new PriorityQueue<Integer>();
    queue1.add(10);
    queue1.add(8);
    System.out.println(queue1.poll()); // 8
    PriorityQueue<Integer> queue2 = 
    		new PriorityQueue<Integer>((o1,o2) -> o1 - o2);
    queue2.add(10);
    queue2.add(8);
    System.out.println(queue2.poll()); // 8
    PriorityQueue<Integer> queue3 = 
    		new PriorityQueue<Integer>((o1,o2) -> o2 - o1);
    queue3.add(10);
    queue3.add(8);
    System.out.println(queue3.poll()); // 10
    

    PriorityQueue:默认自然排序(升序)是小根堆,可以通过传递一个自己的比较器,来定义大根堆。此外PriorityQueue存放的元素,要么有自然排序,否则必须实现比较器。不然会报运行时异常ClassCastException 。

    展开全文
  • 大根堆 小根堆 Java

    2021-05-19 14:00:58
    Java 大根堆 小根堆Java中的堆可以使用PriorityQueue,默认是小根堆, Queue<Integer> min = new PriorityQueue<>(); 大根堆的写法: max = new PriorityQueue<>(new Comparator<Integer&...

    Java 大根堆 小根堆

    在Java中的堆可以使用PriorityQueue,默认是小根堆,

    Queue<Integer> min = new PriorityQueue<>();
    

    大根堆的写法:

    max = new  PriorityQueue<>(new Comparator<Integer>(){
      @Override
      public int compare(Integer o1, Integer o2){
        return o2 - o1;
      }
    });
    

    使用lambda表达式:

    max = new PriorityQueue<>((x, y) -> (y - x));
    

    补充:注意,考虑到Integer运算溢出的问题,可以这样写:

    max = new PriorityQUeue<>(Comparator.reverseOrder());
    
    展开全文
  • 主要介绍了Java实现堆排序(大根堆)的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着编来一起学习学习吧
  • 文章目录四、堆、改进堆、对排序及其应用1、堆和完全二叉树2、用数组实现大根堆3、堆排序4、加强堆(小根堆) 四、堆、改进堆、对排序及其应用 1、堆和完全二叉树 堆(heap)是计算机科学中一类特殊的数据结构的统称...

    四、堆、改进堆、堆排序及其应用

    1、堆和完全二叉树

    • 堆(heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:
      • 堆中某个结点的值总是不大于或不小于其父结点的值;
      • 堆总是一棵完全二叉树。
      • 大根堆:根节点的值不小于叶子节点的值,所有子树都是这样
      • 小根堆:根节点的值不大于叶子节点的值,所有子树都是这样
    • 完全二叉树
      • 一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与[满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。
      • 简单来说,完全二叉树只可能出现两种情况。要么二叉树是满的;要么除了最后一层都是满的,并且最后一层的节点从左依次到右,不能间隔。
      • 对于数中的第i个节点
        1. 左孩子节点 : 2 * i + 1
        2. 右孩子节点 : 2 * i + 2
        3. 父亲节点 : (i - 1) / 2 向下取整

    2、用数组实现大根堆

    • 同完全二叉树的编号一样。数组第0个位置表示堆的根,第i个位置的左孩子节点为2 * i + 1,右孩子节点 : 2 * i + 2,父亲节点 : (i - 1) / 2 向下取整。
    • 对于n个元素的堆来说
    • heapify和heapInsert时间复杂度都是O(log2n)
    • 所有堆的弹出和加入操作都是O(log2n)操作
    package heap;
    
    public class Heap{
        //堆中真实存放的数据
        private int[] heapData;
        //堆的大小
        private int heapSize;
        //堆的容量限制
        private int limit;
    
        public Heap(int limit) {
            this.limit = limit;
            heapData = new int[limit];
            heapSize = 0;
        }
    
        public boolean isEmpty(){
            return heapSize == 0;
        }
    
        /**
         * 堆上浮操作,从当前位置开始,一直交互到合适的位置
         * @param index          从当前位置开始上浮
         */
        private void heapInsert(int index) {
            while (heapData[index] > heapData[(index - 1) / 2]){
                swap(index,(index - 1) / 2);
                index = (index - 1) / 2;
            }
        }
    
        /**
         * 堆下沉
         * @param index 当前需要下沉元素的索引
         */
        private void heapify(int index){
            int left = 2 * index + 1;
            //有左孩子
            while (left < heapSize){
                //找出左右孩子节点中较大的数值的索引,若没有则最大就是左孩子节点
                int largest = left + 1 < heapSize && heapData[left + 1] > heapData[left] ? left + 1 : left;
              //比较左右孩子中较大的数值与父亲节点的数值
                int maxIndex = heapData[largest] > heapData[index] ? largest : index;
                //说明父亲较大不需要比较,直接退出
                if(maxIndex == index){
                    break;
                }
                swap(index,maxIndex);
                index = maxIndex;
                left = 2 * index + 1;
            }
        }
    
        /**
         * 给堆中加入数据,并将数据上浮到合适的位置
         * @param data          待插数据
         * @throws Exception    堆满
         */
        public void push(int data) throws Exception {
            if(heapSize == limit){
                throw new Exception("当前堆已满......");
            }
            heapData[heapSize] = data;
            heapInsert(heapSize++);
        }
    
        /**
         * 堆弹出操作
         * @return
         * @throws Exception
         */
        public int pop() throws Exception {
            if(heapSize == 0){
                throw new Exception("当前堆已空......");
            }
            //先将要弹出元素交换到最后一个位置
            //将交换后的元素下沉到合适位置
            int ans = heapData[0];
            heapData[0] = heapData[heapSize - 1];
            heapSize--;
            heapify(0);
    
            return ans;
        }
    
        private void swap(int i,int j){
            int temp = heapData[i];
            heapData[i] = heapData[j];
            heapData[j] = temp;
        }
        
    }
    
    

    3、堆排序

    • 仿照前面写的堆,我们可以利用数组建立一个大根堆,从数组0号位置开始加入,建立好堆,然后依次弹出。这里进行排序可以不进行弹出,直接交换到数组最后位置即可。前面我们知到,所有堆的弹出和加入操作都是O(log2n)操作。那么对于每个元素都要进行1次加入和 弹出操作,所以堆排序时间复杂度为O(nlog2n)。

    • 直接把数组改为堆

    package heap;
    
    import java.util.Arrays;
    
    public class HeapSort {
    
        public static void heapInsert(int[] arr,int index){
            while (arr[index] > arr[(index - 1) / 2 ]){
                swap(arr,index,(index - 1) / 2);
                index = (index - 1) / 2;
            }
        }
    
        public static void heapify(int[]  arr,int index,int heapSize){
            int left = 2 * index + 1;
            while (left < heapSize){
                //找出左右孩子节点中较大的数值的索引,若没有则最大就是左孩子节点
                int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
                //比较左右孩子中较大的数值与父亲节点的数值
                int maxIndex = arr[largest] > arr[index] ? largest : index;
                //说明父亲较大不需要比较,直接退出
                if(maxIndex == index){
                    break;
                }
                swap(arr,index,maxIndex);
                index = maxIndex;
                left = 2 * index + 1;
            }
        }
    
        private static void swap(int[] arr,int i,int j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
    
        public static void heapSort(int[] arr){
    //        //先建立堆
    //        //从上往下建立堆 O(n * log n)
    //        for(int i = 1; i < arr.length;i++){
    //            heapInsert(arr,i);
    //        }
    
            //从下往上建立堆 O(n) 越多的节点移动的越少
            for (int i = arr.length - 1;i >= 0;i--){
                heapify(arr,i,arr.length);
            }
    
            //依次把最大的元素交换到数组最后
            int heapSize = arr.length;
            swap(arr,0,--heapSize);
            while (heapSize > 0){
                heapify(arr,0,heapSize);
                swap(arr,0,--heapSize);
            }
        }
    
    
        public static int[] generateRandomArray(int maxLen,int maxValue){
            int len = (int) (Math.random() * maxLen) + 1;
            int[] arr = new int[len];
            for (int i = 0;i < len;i++){
                arr[i] =  (int) (Math.random() * maxValue) + 1;
            }
            return arr;
        }
    
        public static void main(String[] args) {
            int testTime = 10000;
            int maxLen = 1000;
            int maxValue= 10000;
    
            System.out.println("测试开始...............");
            for (int time = 0; time < testTime;time++){
                int[] arr = generateRandomArray(maxLen, maxValue);
                int[] copyArr = new int[arr.length];
                System.arraycopy(arr,0,copyArr,0,arr.length);
                heapSort(arr);
                Arrays.sort(copyArr);
                for(int i = 0;i < arr.length;i++){
                    if(arr[i] != copyArr[i]){
                        System.out.println("出错了.....");
                        System.exit(1);
                    }
                }
            }
            System.out.println("测试结束...............");
        }
    
    
    }
    
    

    4、加强堆(小根堆)

    • 加强堆可以修改堆中任一元素的大小且维护堆的性质,并且使得删除操作也是O(logN)操作
    • 通过反向索引表,可以根据元素直接找到位置。用空间换区时间,进而执行其他操作。
    package heap;
    
    import java.util.ArrayList;
    import java.util.Comparator;
    import java.util.HashMap;
    
    public class HeapGreater<T> {
        //堆中存放元素的地方
        private ArrayList<T> heap;
        //方向索引表,可以方便找到元素在堆中的位置
        private HashMap<T, Integer> indexMap;
        //记录堆的大小
        private int heapSize;
        //比较器,根据传入元素的排序要求进行排序
        private Comparator<T> comparator;
    
        public HeapGreater(Comparator<T> comparator) {
            this.comparator = comparator;
            heapSize = 0;
            heap = new ArrayList<>();
            indexMap = new HashMap<>();
        }
    
        /**
         * 判断堆是否为空
         *
         * @return
         */
        public boolean isEmpty() {
            return heapSize == 0;
        }
    
        /**
         * 返回堆的大小
         *
         * @return
         */
        public int size() {
            return heapSize;
        }
    
        /**
         * 判断某个元素是否在堆中
         *
         * @param obj
         * @return
         */
        public boolean contains(T obj) {
            return indexMap.containsKey(obj);
        }
    
        /**
         * 加入堆
         *
         * @param obj
         */
        public void push(T obj) {
            heap.add(obj);
            indexMap.put(obj, heapSize);
            heapInsert(heapSize++);
        }
    
        /**
         * 弹出堆
         *
         * @return
         */
        public T pop() {
            T ans = heap.get(0);
            swap(0, heapSize - 1);
            indexMap.remove(ans);
            heap.remove(--heapSize);
            heapify(0);
            return ans;
        }
    
        /**
         * 修改某一位置的值
         *
         * @param obj
         */
        public void resign(T obj) {
            heapInsert(indexMap.get(obj));
            heapify(indexMap.get(obj));
        }
    
        /**
         * 删除堆中某个元素
         */
        public void remove(T obj) {
            //将最后一个元素先保存起来
            //并且找到需要删除元素的索引,删除堆中的左后一个元素
            //在以前索引的位置放入最后一个元素,并且调整堆大小
            T replace = heap.get(heapSize - 1);
            int index = indexMap.get(obj);
            indexMap.remove(obj);
            heap.remove(--heapSize);
            if (obj != replace) {
                heap.set(index, replace);
                indexMap.put(replace, index);
                resign(replace);
            }
        }
    
        private void heapInsert(int index) {
            while (comparator.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
                swap(index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }
    
        private void heapify(int index) {
            int left = 2 * index + 1;
            while (left < heapSize) {
                int smallest = (left + 1 < heapSize) &&
                        comparator.compare(heap.get(left + 1), heap.get(left)) < 0
                        ? left + 1 : left;
                int minIndex = comparator.compare(heap.get(smallest), heap.get(index)) < 0 ? smallest : index;
                if (index == minIndex) {
                    break;
                }
                swap(minIndex, index);
                index = minIndex;
                left = 2 * index + 1;
            }
        }
    
        /**
         * 交换堆中两个位置的元素,并且更改反向索引表中的相应记录
         *
         * @param i
         * @param j
         */
        private void swap(int i, int j) {
            T o1 = heap.get(i);
            T o2 = heap.get(j);
    
            heap.set(i, o2);
            heap.set(j, o1);
            indexMap.put(o1, j);
            indexMap.put(o2, i);
    
        }
    }
    
    
    展开全文
  • java使用PriorityQueue即优先队列实现大根堆和小根堆
  • Java利用PriorityQueue类实现小根堆和大根堆(其中需要使用Comparator类) 堆:是一颗完全二叉树。通俗点说,一棵树最多只能最后一层不是满的,且不满的最后一层结点从左到右依次排列,那么这棵树就是完全二叉树。 ...
  • 标题:Java中优先队列,大根堆小根堆 小根堆,得到最大的前k个, 1。在一堆元素中,先放入k个,【堆顶元素最小,内部实现的】, 2。然后放入第k+1个元素时,与堆顶元素比较, 3.若大于堆顶元素,则放入堆中,【<...
  • Java实现小根堆和大根堆(PriorityQueue)

    千次阅读 2020-06-28 08:23:01
    1、小根堆实现 package test; import java.util.Comparator; import java.util.PriorityQueue; /* add 增加一个元索 如果队列已满,则抛出一个IIIegaISlabEepeplian异常 remove 移除并返回队列头部的元素 如果...
  • 修改PriorityQueue大根堆
  • Java的优先队列默认是小根堆 import java.util.PriorityQueue; public class Zz { public static void main(String[] args) throws Exception{ PriorityQueue<Integer>a=new PriorityQueue<>(); ...
  • 大根堆/小根堆排序

    2021-01-02 13:14:14
    堆排序之大根堆/小根堆篇堆Min-heapMax-heap堆的存储堆的操作:insert堆的操作:Removemax堆的操作: buildHeap堆排序示例 堆 ** 1>: 完整的二叉树 2>:heap中存储的值是偏序 ** Min-heap 父节点的值小于或等于...
  • 小根堆Java实现

    2021-02-26 20:12:24
    假设 i 为当前节点,那么 (i - 1) / 2 为父节点根据大小排序可分为小根堆和大根堆根堆即元素越小越在上方,大根堆则相反。这里注意:元素大小并不是按数组下标来排序的,下图的数字对应数组的坐标堆的应用:堆...
  • 大根堆和小根堆可以容易获取数据结构内最大值、最小值的数据结构,在很多地方上都有应用。 理解: 大根堆/小根堆,是一棵完全二叉树。特点是节点都大于/小于它的孩子节点。 每次弹出元素的时候,总是从树的最顶端弹...
  • 通常用优先队列来实现小根堆和大根堆 //默认为根堆(看成升序排列) Queue<Integer> minHeap =new PriorityQueue<Integer>() 假如要实现大根堆,可以用lambda 写法来构建比较规则 //默认为...
  • PriorityQueue是Java中内置的数据结构,表示堆。 PriorityQueue类继承于抽象类AbstractQueue,而AbstractQueue类实现了Queue... // 默认为小根堆 Queue<Integer> a = new PriorityQueue<>(); System
  • 大根堆和小根堆

    千次阅读 2019-03-27 19:13:17
    大根堆和小根堆在排序和选择第K大的数中经常有用到。 在Java中是可以直接实现这两个中结构的,使用的优先队列 public class TIMU1 { //小根堆 public PriorityQueue<Integer> minHead = new PriorityQueue...
  • //小根堆 PriorityQueue<Integer> queue = new PriorityQueue(); for (int val : input) { if (queue.size() ) { queue.add(val); } else { if (val > queue.peek()) { queue.poll(); queue.add(val); } } } while ...
  • 1、大顶堆:头部为堆中最大的值 2、顶堆:头部为队中最小的值 ...构建小根堆。 PriorityQueue small=new PriorityQueue<>(); 构建大根堆。 PriorityQueue pq = new PriorityQueue((a, b) -> b - a); ...
  • PriorityQueue实现大根堆和小根堆

    千次阅读 2020-02-06 15:51:32
    小根堆 import java.util.PriorityQueue; PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();//小根堆 从源码上看PriorityQueue的入列操作并没对所有加入的元素进行优先级排序。仅仅保证...
  • //构建大根堆:将array看成完全二叉树的顺序存储结构 private int[] buildMaxHeap(int[] array){ //从最后一个节点array.length-1的父节点(array.length-1-1)/2开始,直到节点0,反复调整堆 for(int i=(array....
  • 大根堆Java实现

    千次阅读 2022-03-26 11:41:12
    // 大根堆建立 // 核心方法:heapInsertheapify /** * 插入元素时候:堆上升 * 删除元素时候:堆下沉 * 堆排序删除相关 */ public class BigHeap{ // 大根堆 private int[] heap; // 堆结构 private int ...
  • 树结构实际应用-大根堆小根堆之堆排序

    多人点赞 热门讨论 2022-03-19 12:03:22
    树结构实际应用-大根堆小根堆之堆排序 堆排序基本介绍 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复 杂度均为O(nlogn),它也是不稳定排序。 堆是具有以下...
  • 大根堆的插入删除 大根堆的插入 大根堆的删除 完整代码 堆的概念以及问题思考 堆的概念:如果有关键字集合k = {k0,k1,k2,......,k(n-1)},把它的所有元素按完全二叉树的顺序存储方式存储在一个一维...
  • 下面对Java中的栈、队列、小根堆和大根堆做一个简单的介绍。 它们都有共用的collections接口中定义的常见函数isEmpty(),可以判断该数据结构中是否还有元素。 栈 Java中有Stack类,但现在已经过时了,不推荐使用。一...
  • Java 堆排序(大根堆小根堆

    千次阅读 2017-12-21 16:24:36
    整理网上的最大及最小代码public abstract class Sorter { public abstract void sort(int[] array); }public class HeapSorter extends Sorter { @Override public void sort(int[] array) { heapSort(arr
  • 优先队列中元素默认排列顺序是升序排列,即小根堆。 根据实践,默认情况的排序,如果只是打印整个队列,拿只针对队头元素。如果是poll(),则会按照升序(小根堆)推出。 若要实现整个队列的升序或者降序...
  • Java大根堆创建重建及堆排序

    千次阅读 2018-08-04 23:22:22
    堆又分为大根堆和小根堆大根堆:在完全二叉树中,任何一个子树的最大值都为该子树的父节点。 小根堆:在完全二叉树中,任何一个子树的最小值都为该子树的父节点。 大根堆的创建与堆排序 堆结构在Java中十分...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,894
精华内容 1,957
关键字:

java大根堆和小根堆