优先队列 - V2EX

优化、沉甸，什么时候都可以赚到钱。
优先队列，做两件事情： 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/
我短期内会把算法仅作为业余爱好，主要精力还是好好优化好公司项目。

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