优先队列

清醒疯子 发布于 2015年08月25日 | 更新于 2015年08月25日
无人欣赏。

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

优先队列,做两件事情: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/ 我短期内会把算法仅作为业余爱好,主要精力还是好好优化好公司项目。

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

暂无回复
登录 或者 注册
相关帖子
格式建议
  • 本站使用 Markdown 格式,想了解这一格式请阅读:《用Markdown语法写文章》
  • 内容框下有实时预览框,请预览后发帖。
  • 文字前面请不要空4个英文空格
  • 每段文字之间请回两次车
  • 贴代码前点击左侧工具栏的“贴代码”按钮(
    ),然后在出现的“enter code here”处贴入你的代码。
  • 回复特定回复的时候,请点击该回复右侧的回复链接,系统将自动创建楼号和@通知。
  • @他人的时候注意,id后面请加一个空格。
  • 使用左侧工具栏“贴链接”按钮(
    )创建的优酷、土豆、youtube视频链接,将自动生成播放区域,不需要使用其他包含方式。
  • 如果要创作长篇格式复杂的帖子,本站建议Mac用户使用Mou软件,离线写好,贴入即可。