目录：
1、定义
2、个性
3、名词
4、实操
注释：
一、定义：
堆（heap）是计算机科学中一类非凡的数据结构的统称。堆通常是一个能够被看做一棵树的数组对象。n个元素的序列{k1,k2,ki,…,kn}当且仅当满足以下关系时，称之为堆。(ki<=k2i且ki<=k2i+1)或者(ki>=k2i且ki>=k2i+1)解析：我在这个文章中用的是数组来实现堆，我就用数组举例：例如：一个数组[2,1,3,4,5,6,7,8]这个能够当成一个相似齐全二叉树的构造，根当初是2，但还不是堆，而堆分成最大堆，和最小堆，咱们以最小堆举例，咱们想让这个齐全二叉树的数组，变成堆，就须要调整，让它们合乎根<=左结点并且根<=右结点，在这里调整咱们也分为两种，咱们能够用向上调整或者向下调整，当初咱们应用向下调整法，从顶开始往下调整，而后向下调整只有都须要合乎堆得属性，就能够失去最小堆[1,2,3,4,5,6,7,8]；以上对定义以及大抵逻辑解析实现，接下来咱们齐全依据这个逻辑解析做实操代码，请急躁往下看
二、个性：
1. 堆中某个结点的值总是不大于或不小于其父结点的值2. 堆总是一棵齐全二叉树3. 堆是非线性数据结构，相当于一维数组，有两个间接后继三、名词：
最大堆/大根堆/大顶堆：
根结点最大的堆
最小堆/小根堆/小顶堆：
根结点最小的堆
四、实操：
1、创立堆接口类：
/** * 堆接口类 * 利用场景： * 优先队列 * 取最大值/最小值 * @author gxw * @date 2021/11/4 早晨21:58 */public interface Heap { //构建堆办法 void buildHeap(int[] arr); //增加元素 void add(int g); //替换元素，将第i个地位的元素值替换为g void replace(int i, int g); //删除顶元素 boolean pop(); //向上堆排序 void shift_up(int now); //向下堆排序 void shit_down(int now); //获取顶值 int getTopValue(); //展现堆 void display();}2、创立最大堆实现类：
/** * 最大堆，也称大跟堆，也称大顶堆 * @author gxw * @date 2021/11/4 早晨22:21 */public class MaxHeap implements Heap { //堆数组 private int[] heapArr; //堆总结点 private int size; //堆深 private int depth; //堆最大寄存结点 private int maxSize; public MaxHeap(int maxSize){ this.maxSize = maxSize; this.heapArr = new int[maxSize]; } @Override public void buildHeap(int[] arr) { if(arr == null && arr.length <= 0) return; //进行构建最大堆 for (int g : arr) { add(g); } } @Override public void add(int g) { //先判断堆是否曾经满了 if(size == maxSize) return; //增加到堆得最初 heapArr[size] = g; //结点数加1 size++; //树深判断是否能够加，如果 2^depth -1 < size // （原理：通过堆深计算所有总结点值，如果小于以后的堆有结点值，天然须要加1） if(Math.pow(2, depth) - 1 < size) depth++; //向上调整 shift_up(size); } @Override public void replace(int i, int g) {//i 代表逻辑地位，不代表数组角标，还需减一 //判断如果角标不在正确范畴内，不能够操作 if(i < 0 || i > size) return; //批改值 heapArr[i - 1] = g; //向上调整 shift_up(i); } @Override public boolean pop() { if(size == 0) return false; //移除最大值(大根值)，并将最初一个值赋给大根值 heapArr[0] = heapArr[size - 1]; //结点数量减一 size--; //向下调整, 1代表逻辑第一个值，不代表数组第一个 shit_down(1); return true; } @Override public void shift_up(int now) {//now 逻辑数值，不代表物理数组角标，还需减一 for(int i = 0;i < depth - 1;i++){ //获取父结点的地位，因为是数组所以减一 int parentIndex = (int) Math.floor(now / 2) - 1; //replace 办法专有，如果父角标小于0，阐明到顶完结 if(parentIndex < 0) break; int nowIndex = now - 1;//因为是数组，所以角标-1 //判断以后数是否大于父结点，如果大于就替换 if(heapArr[nowIndex] > heapArr[parentIndex]){ //替换 int temp = heapArr[parentIndex]; heapArr[parentIndex] = heapArr[nowIndex]; heapArr[nowIndex] = temp; //而后从以后持续往上判断 now = parentIndex + 1; }else{//如果不大于，就完结调整 break; } } } @Override public void shit_down(int now) {//now 逻辑数值，不代表物理数组角标，还需减一 for(int i = 0;i < depth - 1;i++){ //获取左右子结点值最大的地位 int sonIndex = heapArr[2 * now - 1] > heapArr[2 * now ] ? 2 * now - 1 : 2 * now ; int nowIndex = now - 1;//因为是数组，所以角标-1 //判断以后数是否小于子结点，如果小于就替换 if(heapArr[nowIndex] < heapArr[sonIndex]){ //替换 int temp = heapArr[sonIndex]; heapArr[sonIndex] = heapArr[nowIndex]; heapArr[nowIndex] = temp; //而后从以后持续往下判断 now = sonIndex + 1; }else{//如果不小于，就完结调整 break; } } } @Override public int getTopValue() { return heapArr[0]; } @Override public void display() { for(int i = 0;i < size;i++){ System.out.print(heapArr[i] + " "); } System.out.println(""); }}3、创立最小堆实现类：
/** * 最小堆，也称小跟堆，也称小顶堆 * @author gxw * @date 2021/11/4 早晨22:22 */public class MinHeap implements Heap { //堆数组 private int[] heapArr; //堆总结点 private int size; //堆深 private int depth; //堆最小寄存结点 private int maxSize; public MinHeap(int maxSize){ this.maxSize = maxSize; this.heapArr = new int[maxSize]; } @Override public void buildHeap(int[] arr) { if(arr == null && arr.length <= 0) return; //进行构建最小堆 for (int g : arr) { add(g); } } @Override public void add(int g) { //先判断堆是否曾经满了 if(size == maxSize) return; //增加到堆得最初 heapArr[size] = g; //结点数加1 size++; //树深判断是否能够加，如果 2^depth -1 < size // （原理：通过堆深计算所有总结点值，如果小于以后的堆有结点值，天然须要加1） if(Math.pow(2, depth) - 1 < size) depth++; //向上调整 shift_up(size); } @Override public void replace(int i, int g) {//i 代表逻辑地位，不代表数组角标，还需减一 //判断如果角标不在正确范畴内，不能够操作 if(i < 0 || i > size) return; //批改值 heapArr[i - 1] = g; //向上调整 shift_up(i); } @Override public boolean pop() { if(size == 0) return false; //移除最小值(大根值)，并将最初一个值赋给大根值 heapArr[0] = heapArr[size - 1]; //结点数量减一 size--; //向下调整, 1代表逻辑第一个值，不代表数组第一个 shit_down(1); return true; } @Override public void shift_up(int now) {//now 逻辑数值，不代表物理数组角标，还需减一 for(int i = 0;i < depth - 1;i++){ //获取父结点的地位，因为是数组所以减一 int parentIndex = (int) Math.floor(now / 2) - 1; //replace 办法专有，如果父角标小于0，阐明到顶完结 if(parentIndex < 0) break; int nowIndex = now - 1;//因为是数组，所以角标-1 //判断以后数是否小于父结点，如果小于就替换 if(heapArr[nowIndex] < heapArr[parentIndex]){ //替换 int temp = heapArr[parentIndex]; heapArr[parentIndex] = heapArr[nowIndex]; heapArr[nowIndex] = temp; //而后从以后持续往上判断 now = parentIndex + 1; }else{//如果不大于，就完结调整 break; } } } @Override public void shit_down(int now) {//now 逻辑数值，不代表物理数组角标，还需减一 for(int i = 0;i < depth - 1;i++){ //获取左右子结点值最小的地位 int sonIndex = heapArr[2 * now - 1] < heapArr[2 * now ] ? 2 * now - 1 : 2 * now ; int nowIndex = now - 1;//因为是数组，所以角标-1 //判断以后数是否大于子结点，如果大于就替换 if(heapArr[nowIndex] > heapArr[sonIndex]){ //替换 int temp = heapArr[sonIndex]; heapArr[sonIndex] = heapArr[nowIndex]; heapArr[nowIndex] = temp; //而后从以后持续往下判断 now = sonIndex + 1; }else{//如果不小于，就完结调整 break; } } } @Override public int getTopValue() { return heapArr[0]; } @Override public void display() { for(int i = 0;i < size;i++){ System.out.print(heapArr[i] + " "); } System.out.println(""); }}4、测试：
public static void main(String[] args) { int[] arr = {2,3,3,2,6,7,11,11}; /** * 最大堆，大根堆，大顶堆 */ MaxHeap maxHeap = new MaxHeap(20); //构建最大堆 System.out.println("初始构建最大堆"); maxHeap.buildHeap(arr); maxHeap.display(); //增加数 System.out.println("增加9"); maxHeap.add(9); maxHeap.display(); //替换值 System.out.println("将第6个数值替换成10"); maxHeap.replace(6, 10); maxHeap.display(); //移除最大值 System.out.println("移除最大值"); maxHeap.pop(); maxHeap.display(); //获取最大值 System.out.println("获取最大值"); System.out.println(maxHeap.getTopValue()); /** * 最小堆，小根堆，小顶堆 */ MinHeap minHeap = new MinHeap(20); //构建最小堆 System.out.println("初始构建最小堆"); minHeap.buildHeap(arr); minHeap.display(); //增加数 System.out.println("增加1"); minHeap.add(1); minHeap.display(); //替换值 System.out.println("将第6个数值替换成10"); minHeap.replace(6, 10); minHeap.display(); //移除最小值 System.out.println("移除最小值"); minHeap.pop(); minHeap.display(); //获取最小值 System.out.println("获取最小值"); System.out.println(minHeap.getTopValue());}5、后果：
—————————————END———————————
本文为数据结构堆得学习总结，心愿能够帮忙到诸位，如果内容有问题，还请贵人指出，谢谢！