大根堆Java实现：

使用树组表示的完全二叉树的下表有如下规律：
0
1 2
3 4 5 6
7 8 ...

其中针对于k节点，其父节点是 (k-1)/2 (注意： 0节点除外)
对于k节点，其两个儿子节点分布是: left = 2*k + 1 ; right = 2 *k + 2;

大根堆两个主要算法：

• 向上调整算法： 主要用于插入新元数的时候；
• 向下调整算法： 用于从数组创建一个大根堆，或者删除元素的时候；

最后一个节点是heapSize -1 那么最后一个节点的父节点就是最后一个非叶子节点：（完全二叉树规律）；
最后一个非叶子节点是（heapSize - 2）/2;

package BaseDataStructure;

import java.util.Arrays;

public class Heap {
        int[] arr = new int[10];
        int heapSize = 0;

        public void push(int value) {
            arr[heapSize++] = value;
            adjustUp((heapSize-2)/2);
        }

        public void poll(){

            swap(0, heapSize-1);
            heapSize --;

            adjustDown(0);

        }

        // 构建一个最大堆的过程：就是从后往前
        // 针对每个非叶子节点，做向下调整算
        // 参数是：将传如数组，构建大根堆。
        public void buildMaxHeap(int[] _arr){
            arr = _arr;
            heapSize = _arr.length;
            // 找到非叶子节点，然后向下调整;
            for(int i = (arr.length -2)/2; i >= 0; i --){
                adjustDown(i);
            }
        }

        // 向下调整算法
        public void adjustDown(int k){
            // 非叶子节点，不用向下调整。
            // 判断叶子节点：(堆大小是1 或 就一般的最后一个节点的父节点之后的节点都是叶子)
            if(heapSize == 1 || k > (heapSize-2)/2  )
                return;
            int left = 2*k +1, right = 2 * k + 2, largest = left;
            if(right < heapSize && arr[right] > arr[left]){
                largest = right;
            }
            if(arr[largest] > arr[k]){
                swap(largest, k);
                adjustDown(largest);
            }

        }
        
        // 向上调整算法
        public void adjustUp(int k){
            if(k < 0)
                return;
            int left = 2 * k + 1, right = 2 * k +2, largest = left;

            if(right < heapSize && arr[right] > arr[left]){
                  largest  = right;
            }

            if(arr[largest] > arr[k]){
                swap(largest, k);
                adjustUp((k-1)/2);
            }

        }
        void swap(int i, int j){
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }

        // 排序只需要一直删除，堆顶元素， 放到堆末尾;
        // 大根堆，就能进行从小到大排序。
        void sort(){
            for(int i = 0; i < arr.length; i++){
                poll();
            }
        }

}

import java.util.Arrays;

public class TestDemo{
    public static void main(String[] args) {
        Heap heap = new Heap();


        heap.buildMaxHeap( new int[]{3,4,5,6,9} );

        System.out.println( Arrays.toString(heap.arr) );

        heap.sort();

        System.out.println( Arrays.toString(heap.arr ));

    }
}