package chap06_Heap_Sort;import static org.junit.Assert.*;import java.util.ArrayList;import java.util.Arrays;import org.junit.Test;/** * 优先队列，二叉堆数组实现，数组的size最好大一些，至少比里面的堆大一些，来实现堆的扩展（插入元素） *  * @author xiaojintao *  */public class PriorityQueue {    /**     * 返回当前下标下父节点的下标     *      * @param i     * @return     */    protected static int parent(int i) {        if (i == 0)            return i;        return (i - 1) / 2;    }    /**     *      * @param i     * @return     */    protected static int left(int i) {        return 2 * i + 1;    }    /**     *      * @param i     * @return     */    protected static int right(int i) {        return 2 * (i + 1);    }    /**     * 重建最大堆，从i开始到size（不包含size索引），size为堆的大小     *      * @param a     * @param i     * @param size     */    protected static void maxHeapify(int[] a, int i, int heapsize) {        int l = left(i);        int r = right(i);        int tmp;        while (l < heapsize & r < heapsize) {            if (a[i] >= a[l] & a[i] >= a[r])                return;            else if (a[l] > a[r]) {                tmp = a[i];                a[i] = a[l];                a[l] = tmp;                i = l;            } else {                tmp = a[i];                a[i] = a[r];                a[r] = tmp;                i = r;            }            l = left(i);            r = right(i);        }        if (l < heapsize) {            if (a[i] < a[l]) {                tmp = a[i];                a[i] = a[l];                a[l] = tmp;                i = l;            }        }        return;    }    /**     *      * @param a     * @return     */    static int heapMaximum(int[] a) {        return a[0];    }    /**     *      * @param a     * @param heapsize     * @return     */    static int heapExtractMax(int[] a, int heapsize) {        if (heapsize < 1)            return -1;        int max = a[0];        a[0] = a[heapsize];        heapsize--;        maxHeapify(a, 0, heapsize);        return -1;    }    /**     * 将数组a转换成最大堆,不要用递归方法，尽量用迭代方法实现     *      * @param a     */    protected static void buildMaxHeap(int[] a) {        int n = a.length;        for (int i = n / 2; i >= 0; i--) {            maxHeapify(a, i, n);        }    }    /**     * 将堆上x位置处的值增加为key     *      * @param a     * @param x     * @param key     */    static void heapIncreaseKey(int[] a, int x, int key) {        a[x] = key;        if (x == 0)            return;        int i;        int tmp;        do {            i = parent(x);            if (a[i] >= a[x])                break;            else {                tmp = a[i];                a[i] = a[x];                a[x] = tmp;                x = i;            }        } while (i != 0);    }    /**     * 向堆中插入元素，size为当前堆的尺寸,插入后，空位置处为int的最小值，min_value     *      * @param n     * @param size     * @param key     */    static void maxHeapInsert(int[] n, int key, int heapsize) {        if (heapsize == n.length)            System.err.println("heap is full");        heapsize++;        n[heapsize-1] = key;        buildMaxHeap(n);    }    @Test    public void testName() throws Exception {        int[] a = { 2, 5, 3, 7, 8, 12, 0, 2, 45, 32 };        int[] a1 = new int[12];        for (int i = 0; i < a1.length; i++) {            if (i < a.length)                a1[i] = a[i];            else                a1[i] = Integer.MIN_VALUE;        }        System.out.println(Arrays.toString(a1));        // heapIncreaseKey(a, 3, 50);        maxHeapInsert(a1, 65, 10);        System.out.println(Arrays.toString(a1));    }}