用php实现一个堆

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

[下载代码]

5 thoughts on “用php实现一个堆

  1. Scarecrow

    我是文科生,我想问的是,这个堆在PHP中应用在哪里?我是说在WEB上,举个典型例子。

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.