主文件：

package heap;

import java.lang.reflect.Array;
import java.util.Comparator;
import java.util.Arrays;


/**
 * @program: bintree
 * @description: 基于数组实现的二叉堆
 * @author: fwb
 * @create: 2019-06-25 19:29
 **/
public class Heap<E> {
    //实现任意类的大小比较
    private Comparator<E> comparator;
    private int size;
    private E[] elementData;
    //类似于treeMap的设计模式
    //默认初始容量
    private static final int DEFAULT_CAPACCITY = 10;

    public Heap(){
        this(DEFAULT_CAPACCITY,null);
    }

    public Heap(int initialCapacity){
        this(initialCapacity,null);
    }

    public Heap(int initialCapacity,Comparator<E> comparator){
        this.elementData = (E[]) new Object[initialCapacity];
        this.comparator = comparator;
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    /**
    * @Description: 比较两个元素的大小
    * @Param: [o1, o2]
    * @return: int
    */
    private int compare(E o1,E o2){
        if (comparator == null){
            //此时E必须为Compareable接口的子类
            return ((Comparable<E>)o1).compareTo(o2);
        }
        return comparator.compare(o1,o2);
    }

    private int leftChildIndex(int index){
        return index * 2 + 1;
    }

    private int rightChildIndex(int index){
        return index * 2 + 2;
    }

    private int fatherChildIndex(int index){
        if(index == 0){
            throw new IllegalArgumentException("根节点无父亲");
        }
        return (index - 1)/2;
    }

    //添加元素，默认在数组末尾添加元素，此时添加元素之后可能会破坏堆的定义
    /// 元素上浮（判断当前元素与父节点元素的大小）
    public void add(E e){
        //首先判断数组是否满了
        if (elementData.length == size){
            grow();
        }
        //向数组末尾添加元素
        elementData[size++] = e;
        //siftUp,因为size++跑到下一位去了
        siftUp(size -1);
    }
    private void grow(){
        int oldCap = elementData.length;
        int newCap = oldCap + (oldCap < 64 ? oldCap : oldCap >>1);
        if (newCap > Integer.MAX_VALUE - 8){
            throw new IndexOutOfBoundsException("数组过大");
        }
        elementData = Arrays.copyOf(elementData,newCap);
    }

    private void siftUp(int index){
        //index不是根节点，并且大于他的父节点
        while(index > 0 && compare(elementData[index],elementData[fatherChildIndex(index)]) > 0){
            swap(index,fatherChildIndex(index));
            index = fatherChildIndex(index);
        }
    }

    private void swap(int indexA,int indexB){
        E temp = elementData[indexA];
        elementData[indexA] = elementData[indexB];
        elementData[indexB] = temp;
    }

    //找到堆中最大元素，(大顶堆最大元素就是第一个elementData[o])
    public E findMax(){
        if(isEmpty()){
            throw new IndexOutOfBoundsException("head is empty");
        }
        return elementData[0];
    }

    //取出最大值，并将他的最大值返回
    //将堆顶元素与堆的最后一个元素交换位置，然后将交换后堆的最后一个元素删除
    //siftDown，将交换后的元素下沉
    //将其与自己的左右孩子比较，与其中最大的交换位置，
    //直到成为叶子节点（左孩子的节点下标值大于节点个数），或者比左右孩子都大
    public E extractMax(){
        E result = findMax();
        //交换最后一个元素与堆顶元素位置
        swap(0,size-1);
        //删除最后一个元素
        elementData[--size] = null;
        //siftDown
        siftDown(0);
        return result;
    }
    /**
    * @Description: 将二叉树当前节点下沉到正确位置
    * @Param: [index]
    * @return: void
    */
    private void siftDown(int index){
        while(leftChildIndex(index) < size){
            //当前节点左孩子下标
            int j  = leftChildIndex(index);
            //判断是左孩子大还是右孩子大
            if (j + 1 < size){//之所以是小于size而不是小于等于是因为前面size--
                //此时有右孩子
                if (compare(elementData[j],elementData[j + 1]) < 0){
                    //此时j为右孩子指引下标
                    j++;
                }
                //此时element[j]一定是左右孩子的最大值
            }
            if (compare(elementData[index],elementData[j]) > 0){
                break;
            }else{
                swap(index,j);
                index = j;
            }
        }
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        for(E e : elementData)
            if (e != null)
            res.append(e+"、");
        return res.toString();
    }
}

测试文件(以及堆排序)

package heap;

import java.util.Random;

/**
 * @program: bintree
 * @description:
 * @author: fwb
 * @create: 2019-06-26 17:03
 **/
public class HeapTest {
    public static void main(String[] args) {
//        int[] nums = new int[]{62,41,30,28,16,22,13,19,17,15};
//        Heap<Integer> heap = new Heap<>();
//        for(int i : nums){
//            heap.add(i);
//        }
//        heap.add(52);
//        heap.extractMax();
//        System.out.println(heap);

        /*
        堆排序，
         */
        int n = 100000;
        Random random =  new Random();
        Heap<Integer> heap = new Heap<>(n);
        for (int i = 0;i < n;i++){
            heap.add(random.nextInt(Integer.MAX_VALUE));//在整数的最大范围内取1000000个随机数
        }
        int[] nums = new int[n];
//        while(!heap.isEmpty()){
//            nums[i++] = heap.extractMax();
//            for (int j = 1;j < n;j++){
//                if (nums[j -1] < nums[j]){
//                    throw new IllegalArgumentException("Error");
//                }
//            }
//        }
        for (int j = heap.getSize() - 1;j >= 0;j--){
            nums[j] = heap.extractMax();
        }
        for (int j : nums){
            System.out.println(j + "、");
        }
        System.out.println("Test Completed!");
    }
}