堆是数据结构的一种,它和顺序结构和链式结构相同,都有自己的合适的应用场景。
利用堆,可以实现优先队列
队列:先进先出,一般来说是按照时间来排序。
优先队列:按照优先级别进行,先后的调用,优先级别高的优先被调用,并且我们的队列是动态改变的,在什么时间都有可能有新的请求入队,而且某个请求的优先级可能也会发生改变。
在n个元素中,选出前m个元素,如果采用排序的话最好的性能也要NlogN,但是如果我们采用优先队列的话,它的性能就能被优化到NlogM。
优先队列的实现
入队 | 出队 | |
---|---|---|
普通数组 | O(1) | O(n) |
顺序数组 | O(n) | O(1) |
堆 | O(lgn) | O(lgn) |
这样我们整个用堆实现的优先队列的级别就是O(lgn)级别了,而用数组实现的则是O(n)级别。
好了,大概介绍了什么是堆,以及堆的作用,下面我的文章还会介绍如何实现一个堆和堆的一些算法,想深入了解的可以看一下我下面的文章。