堆定义：是一颗完全二叉树，除了树的最后一层节点不要求是满的，其他层次从左到右都是满的。

使用数组来实现存储,结构如下

如果一个节点下标为i,则其父节点的下标为i/2,两个子节点位置分别为2k,2k+1.

/** * 自定义大根堆的实现   * * @param <T> */public class Heap<T extends Comparable<T>> {    private T[] nodes;    private int NUM;    public Heap() {        this.NUM = 0;    }    public Heap(int size) {        nodes = (T[]) new Comparable[size];        this.NUM = 0;    }    /**     * 删除堆中最大元素  目前这个插入法来说，也就是根节点     * 与子节点进行比较，     *     * @return T     */    public T delMax() {        //暂时将最后一个节点放到根节点，然后下沉算法让根节点放到合适的位置        if (nodes == null || NUM == 0) {            return null;        }        T max = nodes[1];        exchange(1, NUM);        NUM--;        sink(1); //让堆重新有序        return max;    }    /**     * 下沉算法使得k处的元素在堆中有一个正确的位置     */    private void sink(int index) {        //不断的比较其与子节点的值， 如果子节点比当前节点的值大，则交换。        while (index * 2 <= NUM) {            int max;            if (index * 2 + 1 <= NUM) {                max = less(2 * index, 2 * index + 1) ? 2 * index + 1 : 2 * index;            } else {                max = index * 2;            }            if (!less(index, max)) {                break;            }            exchange(index, max);            index = max;        }    }    public void insert(T t) {        nodes[++NUM] = t;        //堆是有序的 所以需要将元素放置到合理的位置        swim(NUM);    }    /**     * 上浮算法使得k处的元素在堆中有一个正确的位置     * 与父节点进行比较，     */    private void swim(int index) {        //不断的比较其与父节点的值， 如果父节点比当前节点的值小，则交换。        while (index > 1) {            if (less(index / 2, index)) {                exchange(index / 2, index);            }            index = index / 2;        }    }    /**     * 比较i和j处元素大小     *     * @param i     * @param j     * @return     */    private boolean less(int i, int j) {        return nodes[i].compareTo(nodes[j]) < 0;    }    private void exchange(int i, int j) {        T temp = nodes[i];        nodes[i] = nodes[j];        nodes[j] = temp;    }}

测试类如下

public static void main(String[] args) {    Heap<String> heap = new Heap<>(10);    heap.insert("A");    heap.insert("B");    heap.insert("C");    heap.insert("D");    heap.insert("E");    heap.insert("F");    heap.insert("G");    String max;    while ((max = heap.delMax()) != null) {        System.out.print(max);    }}