[java]
/**
* 数据结构学习之队列之最大优先级队列接口
* @author Sking
*/
package 堆;
public interface MaxPriorityQueue {
/**
* 判断最大优先级队列是否为空
* @return 最大优先级队列为空则返回true，否则false
*/
public boolean isEmpty();
/**
* 返回最大优先级队列的元素个数
* @return 最大优先级队列的元素个数
*/
public int size();
/**
* 返回最大优先级队列的“最大”元素
* @return 最大优先级队列的“最大”元素，如果队列为空则返回null
*/
public Comparable< > getMax();
/**
* 插入指定元素到最大优先级队列
* @param theObject 待插入元素
*/
public void put(Comparable< > theObject);
/**
* 移除最大优先级队列的“最大”元素，并返回
* @return 最大优先级队列的“最大”元素，队列为空则返回null
*/
public Comparable< > removeMax();
}
[java]
/**
* 数据结构学习之队列之最大优先级队列
* 使用数组形式的堆结构实现最大优先队列
* @author Sking*
*/
package 堆;
import java.lang.reflect.Array;
public class MaxHeap{
@SuppressWarnings("rawtypes")
Comparable[] heap;// 堆数组，索引位置0不使用
int size;// 元素个数
/**
* 指定堆数组初始容量的构造方法
*
* @param initialCapacity
* 堆数组的初始容量
*/
public MaxHeap(int initialCapacity) {
if (initialCapacity < 1)
throw new IllegalArgumentException("initialCapacity must be >= 1");
heap = new Comparable[initialCapacity + 1];
size = 0;
}
/**
* 无参构造函数，默认堆数组的初始容量为10
*/
public MaxHeap() {
this(10);
}
/**
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 获取堆数组中的元素个数
*/
public int size() {
return size;
}
/**
* 获取堆数组中的首元素（“最大元素')
*/
@SuppressWarnings({ "rawtypes" })
public Comparable getMax() {
return (size == 0) null : heap[1];
}
/**
* 插入元素导最大堆中，重新调整使数组仍保持“堆特性”
*
* 实现方法：将插入元素放在数组尾部，递归比较当前元素与
* 父亲节点元素 不满足堆特性的条件，则递归向上往“根"的方
* 向冒泡（比较移动），直到新元素的父节点元素大于”它“
*/
@SuppressWarnings({ "rawtypes", "unchecked" })
public void put(Comparable theElement) {
if (size == heap.length - 1) {// 堆数组已满，分配新空间
/*
* heap.getClass().getComponentType()
* 获取数组元素类型对应的Class对象
* Array.newInstance(Class< >,int)
* 指定元素类型和数组长度创建新的数组实例
*/
Comparable[] newArray = (Comparable[]) Array.newInstance(heap
.getClass().getComponentType(), 2 * heap.length);
// 复制堆元素到新数组中
System.arraycopy(heap, 0, newArray, 0, heap.length);
heap = newArray;
}
int currentNode = ++size;// 新元素插入索引
// 新元素沿着到根的路径向上冒泡（比较交换），直到新元素的父结点元素“大于”它
while (currentNode != 1
&& heap[currentNode / 2].compareTo(theElement) < 0) {
// 父节点元素下移
heap[currentNode] = heap[currentNode / 2];
currentNode /= 2;
}
heap[currentNode] = theElement;
}
/**
* 从最大堆中移除堆数组的首元素（”最大元素“）
*
* 实现方法:先用堆数组的最后一个元素填补根节点，然后从根
* 位置开始 沿着不满足堆特性的路径递归进行调整，找到最后
* 一个元素的适合位置，使其成为最大堆。每次迭代均会涉及到
* 一棵子树（包含三个元素），找出 该子树中的最大元素作为当
* 前子树的根节点。如果最大元素就是数组末尾元素 则递归停止，
* 否则交换元素位置，并递归调整。
*
* 注意点：最大元素一开始就被保存，用于最后的返回值。所以调
* 整操作可以安全使用 首元素。并且调整以后数组末尾位置将空出。
*/
@SuppressWarnings({ "unchecked", "rawtypes" })
public Comparable removeMax() {
if (size == 0)// 堆数组为空
return null;
Comparable maxElement = heap[1];// ”最大"元素
Comparable lastElement = h