优先队列

优先队列基本介绍

​ 优先队列又叫做堆,他是一种比较特殊的完全二叉树。所谓完全二叉树就是一层层的堆叠,本层不满就不能堆放下一层。并且优先队列还有一个特点就是如果他是大根堆那么父节点不小于子节点,如果是小根堆父节点不大于子节点。这也是一个递归定义。

为什么要是用优先队列?

  1. 首先如果我们需要查找一个第 k 大的数字,毫无疑问这个是最方便的
  2. 他的插入操作和删除操作都是 logn 的复杂度,所以说他是最经济的方式

优先队列的常用操作

插入

插入的时候我们一般采用的方式就是上滤,也就是把要插入的元素放在最后面,然后比较让这个元素向上冒,知道正确的位置。

//插入
    public void insert(int x) {
        if (size > ele.length - 1) {
            return;
        }
        //不使用0号元素
        ele[++size] = x;
        swim(size);
    }

    //上滤操作
    private void swim(int index) {
        while (index / 2 > 0) {
            if (ele[index] > ele[index / 2]) {
                int tep = ele[index];
                ele[index] = ele[index / 2];
                ele[index / 2] = tep;
            }
            index = index / 2;
        }
    }

删除操作

​ 在删除的时候我们再删除了最上面的元素之后我们还需要调整堆的平衡,这个时候我们采取的策略就是下滤,首先用最后一个元素代替要删除的那个元素,然后对该元素进行下滤,直到平衡。

//删除元素
    public int deleteMax(){
        int max = ele[1];
        ele[1] = ele[size--];
        sink(1);
        return max;
    }

    //下滤
    private void sink(int i) {
        int index = i;
        int tmp = ele[i];
        while (i * 2 < size) {
            int next = i * 2;
            if (ele[next + 1] > ele[next]) {
                ++next;
            }
            if (ele[next] > tmp) {
                // int temp = ele[index];
                ele[index] = ele[next];
                // ele[next] = temp;
                index = next;
            }
            i = next;
        }
        ele[index] = tmp;
    }

堆排序

​ 优先队列的很好的一个使用就是堆排序,他有比较好的性能,和优点。

堆排序分为两个步骤:

  1. 首先我们需要把一个无序的数组构建成一个优先队列,这个过程我们是从下往上进行的,也就是从它有两个孩子的节点开始依次向上上滤操作。

这样我们就建立了一个完整的优先队列了,接下来就是类似于删除最大元素最小元素的问题了。

  1. 然后我们只需要把最大或者最小的元素同最后一个元素交换,然后再次下滤就可以了。这一步就类似于删除顶点元素,的步骤。

这样我们就完成了整个的堆排序 ​

public class HeapSort {

  	//下滤操作	
    public void sink(int[] arr,int i,int end) {
        int index = i;
        int tmp = arr[i];
        while (i * 2 <= end) {
            int n = i * 2;
            if (n+1<=end&&arr[n] > arr[n + 1]) {
                ++n;
            }
            if (arr[n] < tmp) {
                arr[index] = arr[n];
                index = n;
            }
            i = n;
        }
        arr[index] = tmp;
    }

    public void sort(int[] arr) {
        //构建堆
        for (int i = arr.length / 2; i > 0; i--) {
            sink(arr, i, arr.length - 1);
        }
        //从堆序生成顺序
        int size = arr.length - 1;
        while (size > 0) {
            int tmp = arr[1];
            arr[1] = arr[size];
            arr[size] = tmp;
            --size;
            sink(arr, 1, size);
        }
    }

    @Test
    public void fun(){
        int[] arr = new int[]{0, 7, 2, 5, 8, 3, 9};
        sort(arr);
        System.out.println(arr);
    }

}

三大排序的分析

三大排序就是快排堆排序归并排序

  1. 堆排序的优势在于它能够在最坏的情况下使用 NLogN 的复杂度,并且在不借助辅助空间的情况下完成排序
  2. 归并当然也是最坏的情况为 NLogN 时间复杂度,但是他需要借助线性的辅助空间
  3. 快排虽然不需要借助空间,但是时间复杂度没有让人满意,最坏情况快排的复杂度到了平方级别。

看起来貌似堆排序是最完美的排序算法,但是其实不是的,下面就是一些缺点:

  1. 他的内部循环的次数要高于快排
  2. 在现代计算机上我们主存其实也不是很大的问题,这个时候归并其实也没什么不好
  3. 他是不稳定的排序算法

常见排序算法的复杂度

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

How many integers can you find(容斥原理) - HDU 1796

看这题之前先复习一下容斥原理,不然肯定看不懂,呃,如果第一次接触容斥原理的题,可能弄懂了容斥原理你还是看不懂代码,是的,等会你就知道了。

892
来自专栏PPV课数据科学社区

【学习】视觉直观感受 7 种常用排序算法

10月14日发布《统计世界的十大算法》后,很多朋友在后台询问,哪里有“视觉直观感受 7 种常用排序算法”,今天分享给大家,感谢todayx.org。 1. 快速...

3225
来自专栏PHP在线

PHP 排序算法实现讲解

所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。排序 算法在很多领域得到相...

2935
来自专栏Crossin的编程教室

【Python 第72课】map 函数

来看两个问题: 1. 假设有一个数列,如何把其中每一个元素都翻倍? 2. 假设有两个数列,如何求和? 第一个问题,普通程序员大概会这么写: lst_1 = [...

31610
来自专栏趣谈编程

希尔排序

2006
来自专栏人工智能LeadAI

排序算法对比、总结(Python代码)

排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

4018
来自专栏目标检测和深度学习

排序算法算法对比

排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

3476
来自专栏林德熙的博客

不使用数据结构反转栈

昨天有人问我一道题,我有一个栈,我不使用其他数据结构,不使用另一个栈,把这个栈里所有数据反转。

691
来自专栏机器学习从入门到成神

几种有关排序的常见面试问题

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

2012
来自专栏IT杂记

求一个数组中子数组的最大和算法(Java实现)

    前几天在微信订阅号“待字闺中”中看到的一篇文章《小技巧求一个数组中子数组的最大和》,提供下Java的实现,并且在对题目做下小修改,本来打算直接在微信里直...

3308

扫码关注云+社区

领取腾讯云代金券