堆(Heap)是一个可以被看成近似完全二叉树的数组。
堆可以分为大顶堆和小顶堆。
完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针,单纯地通过数组的下标,就可以找到一个节点的左右子节点和父节点。
堆常见的操作:
。
。
,空间复杂度为
。
堆结构的一个常见应用是建立优先队列(Priority Queue)。
求 Top K 的问题抽象成两类。一类是针对静态数据集合;另一类是针对动态数据集合
在优先级队列中,数据的出队顺序不是先进先出,而是按照优先级来,优先级最高的,最先出队。
堆和优先级队列非常相似:往优先级队列中插入一个元素,就相当于往堆中插入一个元素;从优先级队列中取出优先级最高的元素,就相当于取出堆顶元素。
参考:Java 的
PriorityQueue
类