用php实现一个堆

　　堆(heap)是一个很有用的数据结构。堆可以用于实现优先队列。比如一个任务队列，其中中有很多任务，而且不断有新的加进来。要求每次找到其中优先级最高的那个来处理。如果每添加一个就要排序一次的话开销是很大的，时间复杂度为O(nlogn)，但实际上我们要的只是其中最大的那个，因此完全没有必要全部排序。堆这种数据结构保证了堆顶的元素始终是最大的。而且每添加一个新元素，或者弹出堆顶元素的时间复杂度仅为O(logn)。即使是有40亿个元素，也最多需要交换32次。排序树（比如二叉搜索树）插入删除的复杂度虽然也是O(logn)，但堆算法更简单，常系数也更小。同时，堆可以放在一个扁平的数组中，不用额外的指针来维护结构，所使用的空间也更少。

[下载代码]