优先级队列可以用有序数组来实现,这种做法的问题是,尽管删除最大数据项的时间复杂度为O(1),但是插入还是需要较长的O(N)时间,这是因为必须移动数组中平均一半的数据项以插入新数据项,并在完成插入后,数组依然有序。
这里介绍实现优先级队列的另一种结构:堆。堆是一种树,并非Java和C++等编译语言里的“堆”。由它实现的优先级队列的插入和删除的时间复杂度都是O(logN)。尽管这样删除的时间变慢了一些,但是插入的时间快的多了。当速度非常重要,且有很多插入操作是,可以选择堆来实现优先级队列。堆有如下特点:
·它是完全二叉树。即除了树的最后一层节点不需要是满的外,其他的每一层从左到右都完全是满的。
·它常常用一个数组实现。用数组实现的完全二叉树中,节点的索引有如下特点(设该节点的索引为x):
它的父节点的索引为 (x-1) / 2;
它的左子节点索引为 2*x + 1;
它的右子节点索引为 2*x + 2。
·堆中每个节点的关键字都大于(或等于)这个节点的子节点的关键字。这也是堆中每个节点必须满足的条件。所以堆和二叉搜索树相比,是弱序的。
向堆中插入数据,首先将数据项存放到叶节点中(即存到数组的最后一项),然后从该节点开始,逐级向上调整,直到满足堆中节点关键字的条件为止。
从堆中删除数据与插入不同,删除时永远删除根节点的数据,因为根节点的数据最大,删除完后,将最后一个叶节点移到根的位置,然后从根开始,逐级向下调整,直到满足堆中节点关键字的条件为止。具体的看下面的代码:
堆就讨论到这里,如有错误,欢迎留言指正~
转载:http://blog.csdn.net/eson_15/article/details/51105955