Java里面的PriorityQueue底层默认使用的堆，所以我们使用PriorityQueue就能实现堆的功能。

1、小根堆实现

package test;

import java.util.Comparator;
import java.util.PriorityQueue;

/*
    add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常
    remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
    element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
    offer 添加一个元素并返回true 如果队列已满，则返回false
    poll 移除并返问队列头部的元素 如果队列为空，则返回null
    peek 返回队列头部的元素 如果队列为空，则返回null
 */
public class Test {

    public static void main(String[] args) {

        PriorityQueue<Integer>priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });

        for(int i = 10; i >= 0; i--){
            if(priorityQueue.size() < 5){
                priorityQueue.add(i);
            }else {
                priorityQueue.remove();
                priorityQueue.add(i);
            }
        }

        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.remove());
        }
    }
}

2、大根堆

package test;

import java.util.Comparator;
import java.util.PriorityQueue;

/*
    add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常
    remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
    element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
    offer 添加一个元素并返回true 如果队列已满，则返回false
    poll 移除并返问队列头部的元素 如果队列为空，则返回null
    peek 返回队列头部的元素 如果队列为空，则返回null
 */
public class Test {

    public static void main(String[] args) {

        PriorityQueue<Integer>priorityQueue = new PriorityQueue<>();

        for(int i = 0; i < 10; i++){
            if(priorityQueue.size() < 5){
                priorityQueue.add(i);
            }else {
                priorityQueue.remove();
                priorityQueue.add(i);
            }
        }

        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.remove());
        }
    }
}

堆排序是一种树形选择排序方法，它的特点是：在排序过程中，将L[1...n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的元素。

堆的定义如下：n个关键字序列L[1...n]称为堆，当且仅当该序列满足：

1、L(i)<=L(2i)且L(i)<=L(2i+1) 或

2、L(i)>=L(2i)且L(i)>=L(2i+1) (1<=i<=n/2)

满足第一种情况的称为小根堆(小顶堆，即最小的元素在根结点)；

满足第二种情况的称为大根堆(大顶堆，即最大的元素在根结点)

实现步骤：

1、构造堆；

2、得到堆顶元素，这个值就是最大值；

3、交换堆顶元素和数组中的最后一个元素，此时所有元素中的最大元素已经被放到合适的位置

4、对堆进行调整，重新让除了最后一个元素的的剩余元素中的最大值放到堆顶；

5、重复2-4这个步骤，直到堆中剩一个元素为止

api设计：

实现代码

package com.yyy;

public class HeapSort<T extends Comparable<T>> {
    //判断heap堆中索引i处的元素是否小于索引j处的元素
    private static  boolean less(Comparable[] heap, int i, int j) {
        return heap[i].compareTo(heap[j])<0;
    }

    //交换heap堆中i索引和j索引处的值
    private static  void exch(Comparable[] heap, int i, int j) {
        Comparable tmp = heap[i];
        heap[i] = heap[j];
        heap[j] = tmp;
    }



    //根据原数组source，构造出堆heap
    private static void createHeap(Comparable[] source, Comparable[] heap) {
        //把source中的元素拷贝到heap中，heap中的元素就形成一个无序的堆
        System.arraycopy(source,0,heap,1,source.length);

        //对堆中的元素做下沉调整(从长度的一半处开始，往索引1处扫描)
        for (int i = (heap.length)/2;i>0;i--){
            sink(heap,i,heap.length-1);
        }

    }



    //对source数组中的数据从小到大排序
    public static  void sort(Comparable[] source) {
        //构建堆
        Comparable[] heap = new Comparable[source.length+1];
        createHeap(source,heap);
        //定义一个变量，记录未排序的元素中最大的索引
        int N = heap.length-1;
        //通过循环，交换1索引处的元素和排序的元素中最大的索引处的元素
        while(N!=1){
            //交换元素
            exch(heap,1,N);
            //排序交换后最大元素所在的索引，让它不要参与堆的下沉调整
            N--;
            //需要对索引1处的元素进行对的下沉调整
            sink(heap,1, N);
        }

        //把heap中的数据复制到原数组source中
        System.arraycopy(heap,1,source,0,source.length);

    }


    //在heap堆中，对target处的元素做下沉，范围是0~range
    private static void sink(Comparable[] heap, int target, int range){

        while(2*target<=range){
            //1.找出当前结点的较大的子结点
            int max;
            if (2*target+1<=range){
                if (less(heap,2*target,2*target+1)){
                    max = 2*target+1;
                }else{
                    max = 2*target;
                }
            }else{
                max = 2*target;
            }

            //2.比较当前结点的值和较大子结点的值
            if (!less(heap,target,max)){
                break;
            }

            exch(heap,target,max);

            target = max;
        }
    }
}

测试代码：

public static void main(String[] args) {
        //待排序数组
        String[] arr = {"S","O","R","T","E","X","A","M","P","L","E"};
        //通过HeapSort对数组中的元素进行排序
        HeapSort.sort(arr);
        //打印排序后数组中的元素
        System.out.println(Arrays.toString(arr));
    }