数据结构之堆

[java]
/**
* 数据结构学习之队列之最大优先级队列接口
* @author Sking
*/
package 堆;

public inte易做图ce 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;
    }

    /**
     * 从最大堆中移除堆数组的首元素（”最大元素“）
     *
     * 实现方法:先用堆数组的最后一个元素填补根节点，然后从根
     * 位置开始沿着不满足堆特性的路径递归进行调整，找到最后
     * 一个元素的适合位置，使其成为最大堆。每次迭代均会涉及到
     * 一棵子树（包含三个元素），找出该子树中的最大

补充：软件开发 , Java ,