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());
        }
    }
}

1、二叉堆

首先参考了一下$\to$什么是二叉堆？ 此博客也是在看了这篇微信推文的基础上写的。

什么是二叉堆？

二叉堆本质上是一种完全二叉树，它分为两个类型：
1.最大堆
2.最小堆

什么是最大堆呢？最大堆任何一个父节点的值，都大于等于它左右孩子节点的值。

什么是最小堆呢？最小堆任何一个父节点的值，都小于等于它左右孩子节点的值。

二叉堆的根节点叫做堆顶。

最大堆和最小堆的特点，决定了在最大堆的堆顶是整个堆中的最大元素；最小堆的堆顶是整个堆中的最小元素。

2、一个例子

一个二叉堆的操作大致有三种，
1. 调整堆
2. 插入元素
3. 取出堆顶元素

假设给我的一串数字是：【10 2 4 21 15 13 18 7 11】 ，即：

int[] a = new int[] {10,2,4,21,15,13,18,7,11};

下面过一遍堆的调整、插入和取出。提醒一点，向上调整只比较一次，向下调整比较两次。 下面会有提到。

2.1 生成完全二叉树：

对于任何一个序列，我们所需要做的是先把它当作一颗完全二叉树，就是下面这样子。

2.2、调整为小根堆

堆调整是向下调整， 从后往前依次调整每棵子树，每次调整时需要比较两次，子节点之间一次，较小的（对小根堆来说）子节点和根节点之间一次。

先在最后一颗子树上调整：

比较子节点。7更小一点。

于是7和21比较，发现7比21更小。调换两个节点的值。

往上，调整前一颗子树。比较子节点，13与18比较，13小。13再与4比较，4小。于是此子树也不需要做调整。

再往上，还是无需调整。

再往上，2较小，2与10比较。这里我没提子节点之间的比较了，其实是有的，下面也都一样，省略了。不懂我说什么可以前翻一下下黄字处。

把10换下来。同理，7与10比较。

7小。调整节点。

10小。至此小根堆就调整好了。

调整完后，输出的序列应为：【2 7 4 10 15 13 18 21 11】。

2.3、插入元素

插入是堆调整中唯一往上调整的一个环节， 刚才说了，往上调整只比较一次，因为插入时，堆已经调整好了，父节点一定是比子节点小的。任一向上调整环节，如果插入的节点小于父节点，交换两个节点，否则调整结束。

假设插入一个1。先把1插在完全二叉树的末尾，再依次向上调整调整。如果小于父节点，便与父节点交换，直到小于时停止。

1与15比较并调整。

1与7比较并调整。

1与2比较并调整。

插入完成。

插入1完成后的序列为：【1 2 4 10 7 13 18 21 11 15】。

2.4、取出堆顶元素

堆只能从堆顶取元素。对于小根堆，每次取出的元素就是最小的元素。方法就是用堆中最后一个元素，覆盖堆顶元素，然后去掉最后一个元素。再次从上往下调整。同样，每次调整比较两次 。

15覆盖1，并去掉15。

15比较小的子节点2小，所以向下调整。

15比较小的子节点7小，所以向下调整。因为已经被调整到了页节点上，所以停止。

取出小根堆堆顶元素后的序列为：【2 7 4 10 15 13 18 21 11 】。

2.5、Java代码

import java.rmi.dgc.*;
import javax.lang.model.element.*;

class HeapOperator { //实现的是一个小根堆
	public static void Adjust(int a[]){
		int len = a.length;
		int[] b = new int[len];
		int FatherNodeNum = len / 2;
		if(len % 2 == 0){//如果数组a的长度为偶数
			if(a[len - 1] < a[FatherNodeNum - 1]){//父节点大于子节点
				int tmp = a[len - 1];
				a[len - 1] = a[FatherNodeNum - 1];
				a[FatherNodeNum - 1] = tmp;
			}
			--FatherNodeNum;
		}
		//下面的每个父节点都有两个子节点
		while (FatherNodeNum > 0) {
			int k = FatherNodeNum; //k一直跟着当前的节点，直到此节点被换到叶子结点上
			while (k <= len / 2) { //len/2 - 1是第一个叶节点的下标
				int lNode = 2 * k - 1; //左子节点下标
				int rNode = 2 * k; //右子节点下标
				if(a[lNode] <= a[rNode]){//如果左子节点小于等于右子节点
					if (a[lNode] < a[k - 1]) { //同时左子节点小于父节点
						int tmp = a[lNode];  
						a[lNode] = a[k - 1];
						a[k - 1] = tmp;
						k = 2 * k; //记下此节点是数组中第几个值
					}
					else { //如果父节点不小于最小的子节点的值 跳出循环
						break;
					}
				}
				else { //若右节点更小一点
					if (a[rNode] < a[k - 1]) { //如果右子节点小于父节点
						int tmp = a[rNode];
						a[rNode] = a[k - 1];
						a[k - 1] = tmp;
						k = 2 * k + 1; //记下此节点是数组中第几个值
					}
					else { //如果父节点不小于最小的子节点的值 跳出循环
						break;
					}
				}
			}
			--FatherNodeNum;
		}
	}
	
	public static int[] InsertNode(int a[],int m){//先实现的简单一点，假设a数组不为空
		int len = a.length + 1;
		int[] b = new int[len];
		System.arraycopy(a, 0, b, 0, len - 1); //将数组a的内容拷贝到b中
		b[len - 1] = m;//b数组的最后一个元素先赋值为m
		int k = len; //k-1就是新加入的节点的父节点
		while(k > 1){ //k为根节点的时候停下来
			if (b[k - 1] >= b[k/2 - 1]) { //若加入的节点不小于其父节点
				break; //直接跳出循环
			}
			else {//否则交换一下子节点和父节点的值
				int tmp = b[k - 1];
				b[k - 1] = b[k/2 - 1];
				b[k/2 - 1] =tmp; 
				k = k/2;
			}
		}
		return b;
	}
	
	public static int[] FetchNode(int a[]){
		int len = a.length - 1;
		int[] b = new int[len];
		System.arraycopy(a, 0, b, 0, len); //把a数组的前len-1给赋给b
		b[0] = a[a.length - 1]; //去除a的最小元素，为保持树状，覆盖第一个元素
		int k = 1; //现在要把二叉堆从上到下调整
		while(k <= len / 2){ //k为叶节点的时候停下来
			int lNode = 2*k - 1; //左子节点的下标
			int rNode = 2*k; //右子节点的下标
			if(b[lNode] <= b[rNode]){
				if (b[lNode] < b[k - 1]) {
					int tmp = b[lNode];
					b[lNode] = b[k - 1];
					b[k - 1] = tmp;
					k = 2*k;
				}
				else {
					break; //当此节点不小于任何一个子节点的时候，他也会跳出循环
				}
			}
			else {
				if (b[rNode] < b[k - 1]) {
					int tmp = b[rNode];
					b[rNode] = b[k - 1];
					b[k - 1] = tmp;
					k = 2*k + 1;
				}
				else {
					break; //当此节点不小于任何一个子节点的时候，他也会跳出循环
				}
			}
		}
		return b;
	}
	
	public static void main(String[] args) {
		int[] a = new int[] {10,2,4,21,15,13,18,7,11};
		Adjust(a); //将其调整为小根堆
		int i = 0;
		System.out.print("调整过后的小根堆为：");
		while (i < 9) {
			System.out.print(a[i]+" ");
			++i;
		}
		System.out.print("\n");
		int[] b = new int[a.length + 1];
		b = InsertNode(a, 1); //在小根堆里面插入一个1
		i = 0;
		System.out.print("插入1后的小根堆为：");
		while (i < 10) {
			System.out.print(b[i]+" ");
			++i;
		}
		System.out.print("\n");
		int[] c = new int[a.length];
		c = FetchNode(b);
		i = 0;
		System.out.print("取出小根堆最小元素后的小根堆：");
		while (i < 9) {
			System.out.print(c[i]+" ");
			++i;
		}
		System.out.print("\n");
	}
}

运行结果：

调整过后的小根堆为：2 7 4 10 15 13 18 21 11
插入1后的小根堆为：1 2 4 10 7 13 18 21 11 15
取出小根堆最小元素后的小根堆：2 7 4 10 15 13 18 21 11

3、画图工具

写这篇博文主要是最近可能要用Java编程，所以提前练练手，但是又引发了我一直没有解决的问题。程序员画流程图一般都用什么工具？ 我网上找了一下，最后集大家的智慧找到了draw.io 。这是一款在线画图软件，支持各种格式的导出，包括html、xml、PDF等等，也支持中文并且完全免费，这里我都是导出为png格式。下面给一张截图。

可能截图看不太清，想了解的可以自己再找找资料，试试看好不好用。

好了，老铁们，到这趴~~

堆排序是一种树形选择排序方法，它的特点是：在排序过程中，将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));
    }