数据结构之堆（初学只需一文）数据结构之堆：初学只需一文

目录： 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、结果：