package xyz.zrui.algorithm.heap;

public class IndexMxaHeap<T extends Comparable> {

    protected T[] data;

    protected int count;

    protected Integer[] indexes;

    protected int capacity;


    public IndexMxaHeap(int capacity){

        this.indexes = new Integer[capacity + 1];

        this.data = (T[]) new Comparable[capacity + 1];

        this.count = 0;

        this.capacity = capacity;

    }



    private void swap(Object[] arr,int i,int j){

        Object temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

    }



    private void shiftUp(int k){

        while ( k > 1 && data[indexes[k / 2]].compareTo(data[indexes[k]]) < 0){
            swap(indexes,k, k / 2);
            k /= 2;
        }

    }


    private void shiftDown(int k){
        while (k * 2 <= count ) {

            int j = k * 2;
            if (j + 1 <= count && data[indexes[j + 1]].compareTo(data[indexes[j]]) > 0) {
                j += 1;
            }

            if (data[indexes[j]].compareTo(data[indexes[k]]) <= 0){
                break;
            }

            swap(indexes,j,k);

            k = j;
        }
    }

    public T getItem(int i){
        return data[i + 1];
    }


    public int extractMaxIndex() {

        int ret = indexes[1] - 1;

        swap(indexes, count, 1);

        count--;

        shiftDown(1);
        return ret;
    }

    public T extractMax() {

        T ret = data[indexes[1]];

        swap(indexes, count, 1);

        count--;

        shiftDown(1);
        return ret;
    }


    public void insert(int i, T t){

        i += 1;
        data[i] = t;
        indexes[count + 1] = 1;

        count ++;
        shiftUp(count);


    }

    void change(int i, T t){

        data[i + 1] = t;
        // 找到indexes[j] == i, i 表示data[i]在堆中的元素的位置
        // 之后shiftUp(j),再shiftDown(j)
        for (int j = 1; j <= count; j ++){
            if(indexes[j] == i){
                shiftDown(j);
                shiftUp(j);
            }
        }

    }




}

@@ -27,16 +27,43 @@
 .heap;%0A%0A
+%0Aimport java.util.Arrays;%0A%0A
 public c
@@ -69,26 +69,26 @@
 class IndexM
-x
 a
+x
 Heap%3CT exten
@@ -241,10 +241,10 @@
 dexM
-x
 a
+x
 Heap
@@ -1672,17 +1672,17 @@
  + 1%5D = 
-1
+i
 ;%0A%0A     
@@ -2036,14 +2036,519 @@
 %0A%0A    %7D%0A
-%0A%0A
+    public static void main(String%5B%5D args) %7B%0A%0A        IndexMaxHeap%3CInteger%3E heap = new IndexMaxHeap%3C%3E(10);%0A        Integer%5B%5D arr = %7B15,17,19,13,22,16,28,30,41,62%7D;%0A%0A        for (int i = 0; i %3C arr.length; i ++) %7B%0A            heap.insert(i,arr%5Bi%5D);%0A        %7D%0A%0A        for (int i = 0; i %3C= arr.length; i++) %7B%0A            System.out.print(heap.indexes%5Bi%5D + %22 %22);%0A        %7D%0A        System.out.println(%22%22);%0A        Arrays.asList(heap.data).forEach(d -%3E %7B%0A            System.out.print(d + %22 %22);%0A        %7D);%0A%0A    %7D
 %0A%0A%7D%0A

rename IndexMaxHeap.java