堆在java中的应用--PriorityQueue

简介: 堆的特点堆是一种完全二叉树的模拟,堆一般是基于数组的实现,堆分大顶堆和小顶堆,大顶堆就是堆顶是最大的数据,然后子节点总比父节点小,小顶堆则反过来。java中的优先队列就是一个小顶堆的实现。

堆的特点

堆是一种完全二叉树的模拟,堆一般是基于数组的实现,堆分大顶堆和小顶堆,大顶堆就是堆顶是最大的数据,然后子节点总比父节点小,小顶堆则反过来。java中的优先队列就是一个小顶堆的实现。

PriorityQueue的实现

堆的操作

关于堆的操作,主要就是两个。siftUp和siftDown,一个是向上调整堆,一个是向下调整堆。调整的时候java有一个使用comparator的调整,一个没有comparator的调整,调整方法基本相似,区别只是比较的时候是否使用comparator,下面主要说不是用comparator的。调整的目的是满足堆的特点。
调整的代码比较简单,加的注释已经可以疏通逻辑了。



    private void siftUpComparable(int k, E x) {
         //k就是元素的位置,x就是数组中k位置上的元素
        Comparable<? super E> key = (Comparable<? super E>) x;
        //由于是向上调整,堆顶是没有上的,所以条件就是k>0
        while (k > 0) {
            //在数组中,下标(k-1)/2就是父节点的位置
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            //java的实现是小顶堆,所以这里判断是父元素小于比较元素就表示堆调整完成
            if (key.compareTo((E) e) >= 0)
                break;
            //交换
            queue[k] = e;
            //原来的树已经满足,被交换的节点,都满足比父节点小,比子节点大,
            //由于元素交换了,说明现在的元素比较小
            //得继续调整,如果还能被调整,调整换下来的元素还是比较大的
            k = parent;
        }
        queue[k] = key;
    }
    private void siftDownComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>)x;
        int half = size >>> 1;
        //由于是向下调整,所以最后一个有子节点的节点是(len-1)/2,没有子节点的就不用调整        
        while (k < half) {
            int child = (k << 1) + 1; 
            Object c = queue[child];
            int right = child + 1;
            //找出两个子节点中最小的比较,因为是小顶堆
            if (right < size &&((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
                c = queue[child = right];
            //父都比子小就结束
            if (key.compareTo((E) c) <= 0)
                break;
            queue[k] = c;
            //由于元素交换了,下面的树形结构也得满足结构,所以继续调整
            k = child;
        }
        queue[k] = key;
    }

很明显向上调整是有一个有条件操作,向下调整则是没有特殊调整的。所以这两个操作使用的地方也是不同的。

siftDown的应用

siftDown主要是用来堆的建立。

    private void heapify() {
        //所有有子节点的元素进行堆的建立
        for (int i = (size >>> 1) - 1; i >= 0; i--)
            siftDown(i, (E) queue[i]);
    }

    public E poll() {
        if (size == 0)
            return null;
        int s = --size;
        modCount++;//这个主要是在并发操作时抛出异常的,并不是线程安全集合
        E result = (E) queue[0];
        //取出最后一个元素,然后被当做第一个元素,重新调整堆
        E x = (E) queue[s];
        queue[s] = null;
        //由于原来的部分已经是堆,所以就相当于堆顶没有调整
        if (s != 0)
            siftDown(0, x);
        return result;
    }

siftUp的应用

shifUp则是在现有成堆的情况下去添加元素的。

    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        //modCount是用来多线程环境下抛出异常的
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);//新元素被当在最后,开始向上调整
        return true;
    }

PriorityQueue的其余点

构造函数

PriorityQueue在构造函数中做了一个分类的优化

    public PriorityQueue(Collection<? extends E> c) {
        if (c instanceof SortedSet<?>) {
            SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
            this.comparator = (Comparator<? super E>) ss.comparator();
            initElementsFromCollection(ss);
        }
        else if (c instanceof PriorityQueue<?>) {
            PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
            this.comparator = (Comparator<? super E>) pq.comparator();
            initFromPriorityQueue(pq);
        }
        else {
            this.comparator = null;
            initFromCollection(c);
        }
    }

SortedSet本身是排序的,所以可以直接把数据拷贝到priorityqueue中。

    private void initElementsFromCollection(Collection<? extends E> c) {
        Object[] a = c.toArray();
        if (a.getClass() != Object[].class)
            a = Arrays.copyOf(a, a.length, Object[].class);
        int len = a.length;
        if (len == 1 || this.comparator != null)
            for (int i = 0; i < len; i++)
                if (a[i] == null)
                    throw new NullPointerException();
        //获取元素和长度
        this.queue = a;
        this.size = a.length;
    }

PriorityQueue一般也是排序的,但是这里做了一个防备,就是对于继承PriorityQueue的部分需要另外对待。java默认没有它的子类,这里是防止开发者自己的实现,万一不是排序或者堆的情况,直接拷贝数组是有问题的。

    private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
        if (c.getClass() == PriorityQueue.class) {
            this.queue = c.toArray();
            this.size = c.size();
        } else {
            //PriorityQueue的不确定子类
            initFromCollection(c);
        }
    }

剩下的情况都是依靠initFromCollection来的。其实主要就是下面的两个步骤。

    private void initFromCollection(Collection<? extends E> c) {
        //拷贝数组
        initElementsFromCollection(c);
        //建堆
        heapify();
    }

初始化元素大小

现在面试有一些会问这个,所以说一下,初始化11,arrayList是10,之所以不同应该是11正好是一个满二叉树的数字。

private static final int DEFAULT_INITIAL_CAPACITY = 11;

扩容

说这个也是因为面试可能会问。原来的长度小于64,就直接涨一倍再加2,否则涨0.5倍。至于为什么非要+2,我也不清楚。除了hash结构,扩容有hash计算方便问题,剩下的还没发现扩容有什么特别的讲究。

    private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        //原来的长度小于64,就直接涨一倍再加2,否则涨0.5倍
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        queue = Arrays.copyOf(queue, newCapacity);
    }

堆排序

堆排序就是先建立堆,然后移除第一个数,剩下的部分继续调整堆,这样每次都是拿出剩下中最大或者最小的元素,这样就是排序了。

linux中sort函数也是堆排序的实现,而且上面有一段注释

/**
  43 * sort - sort an array of elements
  44 * @base: pointer to data to sort
  45 * @num: number of elements
  46 * @size: size of each element
  47 * @cmp_func: pointer to comparison function
  48 * @swap_func: pointer to swap function or NULL
  49 *
  50 * This function does a heapsort on the given array. You may provide a
  51 * swap_func function optimized to your element type.
  52 *
  53 * Sorting time is O(n log n) both on average and worst-case. While
  54 * qsort is about 20% faster on average, it suffers from exploitable
  55 * O(n*n) worst-case behavior and extra memory requirements that make
  56 * it less suitable for kernel use.
  57 */

这里和快排对比说明了为什么选择堆排序。

1,时间复杂度

堆排序的平均时间复杂度为O(nlogn),最坏情况也是O(nlogn),快排的平均时间复杂度也是O(nlogn),但是最坏情况是O(n*n)。

2,空间复杂度

堆排序是O(1),快排是O(logn)。快排是递归调用,所以空间要求更多一些。

其实这样比较,感觉堆排序怎么也比快排更好,但是众所周知,快排是内排序最快,而且注释也说明平均情况下,快排是比堆排序快20%的。那问题来了,为什么会这样呢?

堆排序为什么比快排慢

首先时间复杂度的计算本身是一个忽略一些情况的估算,其实和程序执行的结果不完全一致,例如程序中有比较,交换数值的操作,但是这些并不会作为评估时间复杂度的方式,但是这些是程序执行的一个操作。时间复杂度只能保证数量级直接的比较,例如nlogn是比n*n快的,但是并不代表nlogn和nlogn的执行是一样快的。

堆排序相比快排,浪费时间的一个点就是在做无效的比较交换。例如大顶堆,最上面的元素是最大的,堆排序会把最大的拿出来,然后把当时的最后一个换上去,继续建立堆。这里有个很明显的问题,就是在一次堆建立后,从最后拿的元素没有原来堆顶下面两个元素大,那么就有很多无用的比较交换,其实本来就小,还得和大的都比较一次并且换位置。这里是堆排序的一个优化点,很多人都在这里做了优化方案。

交换次数可以通过下面这个网站对比模拟。http://sorting.at/

堆排序的应用

例如对最差时间有要求的场景,例如上面说的sort的例子

大数据量的筛选:求一亿个数字里面最小的10个数字(剑指offer题目)

目录
相关文章
|
2天前
|
缓存 安全 算法
Java内存模型深度解析与实践应用
本文深入探讨Java内存模型(JMM)的核心原理,揭示其在并发编程中的关键作用。通过分析内存屏障、happens-before原则及线程间的通信机制,阐释了JMM如何确保跨线程操作的有序性和可见性。同时,结合实例代码,展示了在高并发场景下如何有效利用JMM进行优化,避免常见的并发问题,如数据竞争和内存泄漏。文章还讨论了JVM的垃圾回收机制,以及它对应用程序性能的影响,提供了针对性的调优建议。最后,总结了JMM的最佳实践,旨在帮助开发人员构建更高效、稳定的Java应用。
|
14天前
|
存储 Java 程序员
Java面试题:方法区在JVM中存储什么内容?它与堆内存有何不同?
Java面试题:方法区在JVM中存储什么内容?它与堆内存有何不同?
37 10
|
8天前
|
分布式计算 DataWorks Java
DataWorks操作报错合集之使用ODPS Tunnel Upload功能时,遇到报错:Java 堆内存不足,该如何解决
DataWorks是阿里云提供的一站式大数据开发与治理平台,支持数据集成、数据开发、数据服务、数据质量管理、数据安全管理等全流程数据处理。在使用DataWorks过程中,可能会遇到各种操作报错。以下是一些常见的报错情况及其可能的原因和解决方法。
|
14天前
|
存储 安全 Java
Java面试题:在JVM中,堆和栈有什么区别?请详细解释说明,要深入到底层知识
Java面试题:在JVM中,堆和栈有什么区别?请详细解释说明,要深入到底层知识
27 3
|
14天前
|
存储 缓存 监控
Java面试题:解释堆和栈的OutOfMemoryError通常在什么情况下会发生
Java面试题:解释堆和栈的OutOfMemoryError通常在什么情况下会发生
20 3
|
14天前
|
监控 Java 数据库连接
Java面试题:如何诊断和解决Java应用的内存泄漏问题?
Java面试题:如何诊断和解决Java应用的内存泄漏问题?
18 2
|
18小时前
|
供应链 安全 Java
以典型 Java 应用为例,完整的软件供应链会包含什么
以典型 Java 应用为例,完整的软件供应链会包含什么
5 0
|
18小时前
|
NoSQL Java
如何使用jmap命令获取Java堆信息
如何使用jmap命令获取Java堆信息?
5 0
|
19小时前
|
存储 缓存 安全
深入理解Java内存模型(JMM)及其在并发编程中的应用
本文旨在探索Java内存模型(JMM)的奥秘,并揭示其在并发编程中的关键作用。我们将通过数据支撑,案例分析,以及对比研究的方法,深入剖析JMM的核心概念、原理和机制。文章将提供丰富的实例,包括同步块、volatile关键字的使用,以及线程间的通信机制,来具体展示JMM如何管理并发环境下的数据一致性和可见性问题。我们还将讨论JMM在现代多核处理器架构下面临的挑战,以及如何在编写高效且线程安全的代码时避免常见的并发陷阱。最后,文章将提出一些最佳实践,帮助开发者充分利用JMM的特性,以提升应用程序的性能和可靠性。
|
5天前
|
存储 安全 Java
深入理解Java内存模型(JMM)及其在并发编程中的应用
Java内存模型(JMM)是Java虚拟机规范中定义的一套规则,它指导着线程如何通过内存交互。JMM不仅关乎数据一致性与可见性问题,还直接影响到并发程序的正确性和性能。本文将探讨JMM的核心概念、工作原理及其在高效并发编程中的实践应用,旨在为读者提供一套完整的理论框架和实战技巧,以应对复杂并发环境下的挑战。