优先队列

优化、沉甸,什么时候都可以赚到钱。

优先队列,做两件事情:1、删除最大元素;2、插入元素。分别用delMax()和insert()表示。

实现方式有多种:

1、无序数组

实现类似于下压栈,就是我们常见到的push()和pop()。

2、有序数组

在insert()里添加代码,使较大元素右移一格,可以使数组保持有序。最大元素就会在数组的一边。

3、链表

先实现基于链表的下压栈,然后修改pop()找到最大元素,或者修改push()保证所有元素逆序来删除链表首元素。

4、堆

二叉堆数组里,每个元素保证大于等于另外两个特定位置的元素。根结点就会是最大结点。

在二叉堆里,k结点的父结点是k/2,k结点的子结点是2K或2K+1。

堆有序化有两种操作:1、上浮(子结点比你结点大,上浮);2、下沉(父结点比子结点小,下沉)。

堆里插入元素:新元素加到数组末尾,上浮到适合位置。

堆里删除最大元素:删除顶端元素,把最后一个元素放到顶端,下沉到适合位置。

二叉堆的优势是可以使两个操作用时与队列大小仅成对数关系。

还有多叉堆,明天再看:)

后记(下面以聊家常为主,没时间没兴趣的朋友请直接忽略):

关于算法的事情,@xiaotie 兄有最新的回复,大家可以自行看看:http://ourcoders.com/thread/show/6615/

我短期内会把算法仅作为业余爱好,主要精力还是好好优化好公司项目。

这一波的思考,对我有很大的帮助,一个是提出了“递减原则”,补上我的方法论里一直缺的一颗棋。一个是让我又重新开始看算法。只要开始,就有了不断优化的可能。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 数据结构与算法--优先队列和堆排序 在某些数据处理的例子中,总数据量太大,无法排序(甚至无法全部装进内存)。例如,...
    sunhaiyu阅读 4,669评论 0 2
  • 优先队列 支持删除最大元素和插入元素两种操作的数据结构可以称之为优先队列。可以用无序数组|有序数组(下压栈), 链...
    melouverrr阅读 4,117评论 0 0
  • 一、优先队列 1.简单介绍 优先队列是一种抽象的数据结构,它与我们生活中的许多场景息息相关。比如我们的电脑或者手机...
    丶legend阅读 4,457评论 0 0
  • 本文的目标是要做出优先队列和堆排序两个Demo。 完全二叉树 优先队列 堆排序 完全二叉树 完全二叉树的定义是建立...
    囧书阅读 10,433评论 13 48
  • 1. 基本概念 比如:输入N个字符串,我们需要找打最大的M个字符串。我们可以将N个字符串进行排序,然后取最大的M个...
    不会code的程序猿阅读 3,468评论 0 0

友情链接更多精彩内容