JAVA认证：解析从堆到优先队列的实现

会计考友

优先队列，顾名思义，就是一种按照必然优先级存储和掏出数据的队列。它可以说是队列和排序的完美连系体，不仅可以存储数据，还可以将这些数据按照我们设定的轨则进行排序。
; Q! f, d" v- m8 C; Q" e( f先说说优先队列的实现吧。有一点需要澄清，良多人一向觉得Priority Queue就是一个Priority Heap，这种说法当然是片面的。既然优先队列只是存储数据和排序的连系，那么按照我们学过的常识，可以列出以下的实现体例：无序数组、无序链表、有序数组、有序链表以及二叉查找树，当然还有堆。这些体例在实现中当然也有优先级，下表就是一些体例的实现根基操作的时刻机能对比：
- t& C" P$ t8 Y
) ?* W7 \; W6 n图1 一些优先队列的实现方案的时刻机能对比
% O1 G0 A9 C, d从这张内外我们可以按照时刻复杂度这个优先级来进行一次排序，当然，你会选用最后一种二叉查找树作为实现优先队列的方案，可是现实上我们采用的是堆。堆，就是一种二叉树，堆和二叉查找树是近似的，可是也有些许分歧：从外形来看，二叉查找树可以有分歧的外形，而堆只能是完全二叉树；在时刻机能上，二者并无较着的区别。堆也是有序的，我们一般将其分为大顶堆和小顶堆。小顶堆，顾名思义，就是这个堆的子结点的值小于父结点的值；相反的，大顶堆就是堆的子结点的值都大于父结点的值。
在实现的时辰，我们经常使用基于数组的堆，即堆中的元素保留在一个数组中，而这个数组元素的保留也是按照必然纪律的：如不美观父结点的位置为n，那么，其对应的摆布子结点的位置分袂是2n+1和2n+2。也就是说，我们在视觉上（如不美观用绘图形象化暗示堆的话）和素质上将堆服装成两种工具，这样既便于理解，也利于实现，素质的实现是用数组是因为考虑到数组的一些机能。
' f. t3 _; S# ?6 ~, B0 U堆有两个很根基的操作：增添、删除。先来说耸ё裒加元素，假设有下面这样一个堆：

( g8 n5 o. E2 b7 U& I这时辰，有一个元素1要添加进来，这时辰应该怎么办呢？第一步，将元素添加到堆的最后一个位置。