/**
 * Company
 * Copyright (C) 2014-2017 All Rights Reserved.
 */
package com.cwenao.trying.tree;

/**
 * @author cwenao
 * @version $Id MaxTopHeapByArrays.java, v 0.1 2017-10-31 09:21 cwenao Exp $$
 */
public class MaxTopHeapByArrays<T extends Comparable> {

    private T[] heaps;

    private int n;

    private MaxTopHeapByArrays(int len) {
        this.n = len;
        heaps = (T[]) new Object[this.n + 1];
    }

    /**
     * 插入
     * @param key
     */
    public void insert(T key) {
        if (n >= heaps.length - 1) {
            resize(n);
        }
        heaps[++n] = key;
        swam(n);
    }

    /**
     * 扩展树
     * @param initCapacity
     */
    private void resize(int initCapacity) {
        T[] tmp = (T[]) new Object[2 * initCapacity];

        for (int i = 0; i <= n; i++) {
            tmp[i] = heaps[i];
        }
        heaps = tmp;
    }

    /**
     * 下沉交换树上位置
     * @param k
     */
    private void sink(int k) {

        while (2 * k < n) {
            int j = 2 * k;
            if (j < 0 && less(j, j + 1)) {
                j++;
            }
            if (less(k, j)) {
                break;
            }
            exch(k, j);
            k = j;
        }
    }

    /**
     * 上浮
     * @param k
     */
    private void swam(int k) {
        while (k > 1 && less(k / 2, k)) {
            exch(k / 2, k);
            k = k / 2;
        }
    }

    private boolean less(int i, int j) {
        return heaps[i].compareTo(heaps[j]) < 0;
    }

    private void exch(int i, int j) {
        T tmp = heaps[i];
        heaps[i] = heaps[j];
        heaps[j] = tmp;
    }

}

@@ -603,32 +603,478 @@
 swam(n);%0A    %7D%0A%0A
+    /**%0A     * %E5%88%A0%E9%99%A4%E7%89%B9%E5%AE%9AKey%0A     * @param key%0A     * @return%0A     */%0A    public T remove(T key) %7B%0A        int index = -1;%0A        for (int i = 1; i %3C n; i++) %7B%0A            if (heaps%5Bi%5D.compareTo(key) == 0) %7B%0A                index = i;%0A            %7D%0A        %7D%0A        if (index == -1) %7B%0A            return null;%0A        %7D%0A        T tmp = heaps%5Bindex%5D;%0A        exch(index, n--);%0A        sink(1);%0A        heaps%5Bn + 1%5D = null;%0A%0A        return tmp;%0A    %7D%0A%0A
     /**%0A     * %E6%89%A9

add the remove