java数据结构-堆

一.堆

①堆的概念:如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆

这里堆的存储结构就是上一个树的文章提到的二叉树顺序存储

堆的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树

虽然堆是一个二叉树结构，但是存储的时候用顺序表/数组，但是利用了根和子类2k+1,2k+2的下标关系构成了二叉树的结构

小根堆示例

(a) 逻辑结构

plaintext

10 / \ 15 56 / \ \ 25 30 70

(b) 存储结构（数组形式）

[10, 15, 56, 25, 30, 70]

大根堆示例

(a) 逻辑结构

plaintext

70 / \ 56 30 / \ \ 25 15 10

(b) 存储结构（数组形式）

[70, 56, 30, 25, 15, 10]

②堆的存储方式:从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储

将元素存储到数组中后，可以根据二叉树的性质对树进行还原。假设i为节点在数组中的下标，则有：
·如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
·如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
·如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子

③堆的两个调整方式:

堆的向下调整（siftDown）

• 作用：当堆顶元素被替换（例如取出堆顶后，用最后一个元素替代），新的堆顶可能比子节点小（大根堆）或大（小根堆），需要向下 “沉” 到正确位置，以维护堆的性质。
• 适用场景：构建初始堆、取出堆顶元素后、堆排序过程中。
• 核心逻辑：
  1. 从当前父节点开始，先找到它的左右子节点中的最优子节点（大根堆找较大的子节点，小根堆找较小的子节点）。
  2. 如果父节点破坏了堆的性质（例如大根堆中，父节点值 < 最优子节点值），就交换父子节点的位置。
  3. 然后将当前节点更新为子节点，继续向下比较，直到到达叶子节点或调整到位。

堆的向上调整（siftUp）

• 作用：当新元素插入到堆的末尾时，该元素可能比父节点大（大根堆）或小（小根堆），需要向上 “浮” 到正确位置，以维护堆的性质。
• 适用场景：向堆中插入元素时。
• 核心逻辑：
  1. 从新插入的子节点开始，不断与父节点比较。
  2. 如果子节点破坏了堆的性质（例如大根堆中，子节点值 > 父节点值），就交换父子节点的位置。
  3. 然后将当前节点更新为父节点，继续向上比较，直到到达堆顶或调整到位。

核心区别总结

④堆的创建：

首先明确一个规律：两个向上调整和向下调整的代码在大根堆和小跟堆只有比较符号的区别

所以下面都以大根堆为例

import java.util.Arrays; public class TestHeap { public int elem[]=new int [10]; public int usedsize;

堆类：成员变量有用来储存的数组和已使用容量（不是数组最大容量）

public void initelem(int arr[]){ for (int i = 0; i < arr.length; i++) { this.elem[i]=arr[i]; this.usedsize++; } }

初始化堆（默认数组容量 10），并从外部数组导入数据，如果默认数组容量10不够需要手动修改

public boolean isfull(){ return usedsize==elem.length; }

判断是否满了：直接返回已使用大小是否等于堆数组最大容量

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

判断是否为空：

public void createheap(){ for(int p=(this.usedsize-1-1)/2;p>=0;p--){ //总共十个，那最后一个编号是9，父亲是4，那就需要总长度=(10-1)-1)/2得到最后一个非叶子节点(有子节点的节点) siftdown(p,this.usedsize) ; //才能得到父的下标 }//这里是个循环所以不会有处理不完的情况！ } public void siftdown(int p,int usedsize){ //从上到下大根堆 p一般是0开始 int child=2*p+1; while(child<usedsize){ //找到p的左右孩子的最大值且保证下标合法 if(child+1<usedsize&&elem[child]<elem[child+1]){ child++;//如果左子叶比右子叶小(合法情况下)，那就把child++标到右子叶，然后再跟root比大小 } if(elem[child]>elem[p]){ int temp=elem[child]; elem[child]=elem[p]; elem[p]=temp; p=child; // 4. 交换后，原父节点p的值可能现在在child的位置上， child=2*p+1; // 它可能比它新的子节点还要小，因此需要继续向下调整 } else{ break;// 5. 如果父节点p的值已经大于等于它的最大子节点， } // 说明以p为根的子树已经是最大堆了，调整结束 } }

构建大根堆：构建方法 → 控制向下调整

createheap()负责组织循环，从最后一个非叶子节点往前遍历，逐个调用siftdown()；而siftdown()负责对单个父节点对应的子树进行「从上到下」调整，使其成为大根堆。两者配合，最终将一个无序数组转换成符合大根堆特性的数组。

createheap()关键细节说明

1. 循环起始下标：(this.usedsize-1-1)/2（最后一个非叶子节点）

   • 第一步：this.usedsize - 1是堆中「最后一个有效元素」的下标（记为lastChild），这个元素是叶子节点。
   • 第二步：根据完全二叉树的数组存储特性，任意子节点的父节点下标 = (子节点下标 - 1) / 2。
   • 第三步：代入lastChild，得到(lastChild - 1)/2 = (usedsize-1-1)/2，这就是「最后一个非叶子节点」的下标。
   • 为什么选它？这个节点的子节点都是叶子节点（天然符合大根堆，无需调整），是调整的「最优起点」，不会出现调整结果被下层数据破坏的情况。

2. 循环方向：p >= 0（从后往前遍历）

   • 循环变量p从「最后一个非叶子节点」逐步递减到0（根节点），遍历所有非叶子节点。
   • 为什么从后往前？保证每调用一次siftdown()，当前节点的下层子树已经是合法的大根堆，siftdown()能正常生效，最终从底层到顶层，整棵树成为大根堆。

3. 循环体：siftdown(p, this.usedsize)

   • 传入两个参数：当前要调整的父节点p，堆的有效元素个数this.usedsize（限制调整范围，避免越界）。
   • 作用：对当前p对应的子树做调整，使其成为大根堆，为上层节点的调整打下基础。

siftdown()关键细节说明

1. 子节点初始化：child = 2*p + 1

   • 利用完全二叉树的数组存储特性，左子节点下标 =2*父节点下标 + 1，右子节点下标 =2*父节点下标 + 2（即child+1）。
   • 先默认左子节点为候选，后续再通过判断切换为右子节点（最大值）。

2. 找最大子节点的逻辑：child+1<usedsize&&elem[child]<elem[child+1]

   • 这是大根堆调整的核心优化，必须先判断右子节点是否合法（child+1 < usedsize），再比较大小，否则会出现数组越界异常。
   • 最终child一定指向「左右子节点中值更大的那个」，保证交换后父节点是子树的最大值，符合大根堆特性。

3. 循环终止的两种情况

   • 情况 1：child >= usedsize（循环条件不满足）：当前节点已经是叶子节点，没有子节点，无需调整。
   • 情况 2：elem[child] <= elem[p]（执行break）：当前父节点 >= 最大子节点，子树符合大根堆特性，调整到位。

两个方法的配合流程（通俗举例）

假设usedsize=6，数组为[3,1,4,1,5,9]，完整流程如下：

1. createheap()计算起始下标：(6-1-1)/2=2（对应元素4）。
2. 循环开始，p=2→ 调用siftdown(2,6)，调整后数组变为[3,1,9,1,5,4]（以 2 为根的子树成大根堆）。
3. p=1→ 调用siftdown(1,6)，调整后数组变为[3,5,9,1,1,4]（以 1 为根的子树成大根堆）。
4. p=0→ 调用siftdown(0,6)，调整后数组变为[9,5,4,1,1,3]（以 0 为根的整棵树成大根堆）。
5. 循环结束，大根堆构建完成。

总结

1. createheap()是「组织者」，负责从最后一个非叶子节点往前遍历，批量调用siftdown()。
2. siftdown()是「执行者」，负责单个子树的从上到下调整，核心是找最大子节点、比较交换、循环下沉。
3. 两者配合的核心逻辑：从底层到顶层，逐步将每个子树调整为大根堆，最终构建出完整的大根堆。
4. 关键公式：最后一个非叶子节点下标(usedsize-1-1)/2，子节点下标2*p+1（左）、2*p+2（右）。

public void siftup(int child){ //向上调整|配合push！child在push里 int p=(child-1)/2; while(p>=0) { if (elem[child] > elem[p]) { int temp = elem[child]; elem[child] = elem[p]; elem[p] = temp; child = p; p = (child - 1) / 2; } else { break; } } } public void push(int val){//插入数组 if(isfull()){//如果满了就扩容数组 elem= Arrays.copyOf(elem,2*elem.length); } elem[usedsize]=val; siftup(usedsize); usedsize++;//加入调整完后在++计数器 }

这两段代码是大根堆的「元素插入 + 维护堆特性」完整逻辑：push()负责将新元素插入到堆的末尾（并处理扩容），siftup()负责将新插入的元素向上调整到正确位置，最终保证插入后依然是一个合法的大根堆。

其中push()是插入的「入口方法」，siftup()是插入后的「辅助调整方法」，两者紧密配合，下面先分别解析，再讲整体流程(向上调整（siftup()）走的就是「一条单一的垂直线路」，不会分叉，也不会涉及其他兄弟节点。)。

siftup()这个方法我们之前单独解析过，这里结合push()方法，重点讲它和push()的配合逻辑，以及核心细节回顾。

siftup()与push()配合的关键细节

1. 参数child的来源：push()中传入的usedsize，也就是新元素的插入下标，两者完全对应，保证调整的是刚插入的新元素。
2. 调整的目的：新元素插入末尾后，可能比父节点大（破坏大根堆），通过siftup()让它 “上浮” 到合适位置，最终保证插入后整个堆依然是合法的大根堆。
3. 无需关注兄弟节点：和siftdown()不同，siftup()只需要和直接父节点比较，不需要关注兄弟节点，因为父节点本身已经符合大根堆特性（大于等于其他子节点），交换后依然能保证堆特性

push()关键细节补充

1. 插入位置的选择：elem[usedsize]

   • 堆的底层是完全二叉树，插入元素只能在完全二叉树的末尾（对应数组的usedsize下标），不能随意插入其他位置，否则会破坏完全二叉树的结构，后续无法正常维护堆特性。
   • 例如：当前usedsize=5（有效元素下标0~4），新元素插入下标5，这是完全二叉树的下一个可用节点，插入后仍保持完全二叉树结构。

2. 扩容的时机与规则

   • 时机：插入前先判断isfull()（usedsize == elem.length），堆满时才扩容，避免无效扩容。
   • 规则：2*elem.length（容量翻倍），这样可以保证扩容的时间复杂度平均为O(1)，是工业级代码的常用选择。
   • 注意：Arrays.copyOf()会创建一个新数组，复制原数组的所有元素，然后返回新数组，这里直接赋值给elem，完成堆底层数组的替换。

3. usedsize++的位置：调整后自增

   • 为什么要放在siftup()之后？因为siftup()调整时，需要传入新元素的下标（usedsize），如果先自增，usedsize就会变成新值，传入的下标就错了（对应不到新元素）。
   • 例如：新元素插入下标5，siftup(5)调整完成后，usedsize自增为6，表示堆的有效元素个数变为6，逻辑正确。

public int poll(){ int val=elem[0]; elem[0]=elem[usedsize-1]; elem[usedsize-1]=val; siftdown(0,usedsize-1); usedsize--; return val; }

删除堆顶元素：因为堆顶元素都是最大值/最小值(排序后的)，所以删除就直接让它跟最后一个元素交换位置，然后向下调整(从0到usedsize-1)，最后usedsize-1，此时就相当于这个元素消失

public int peek(){ if(isEmpty()){ return -1; } else{ return elem[0];//堆顶 } }

获取堆顶元素:不为空的话直接获取堆数组的0下标元素

public void heapSort(){ int end=usedsize-1; while(end>0){ int temp=elem[0]; elem[0]=elem[end]; elem[end]=temp; siftdown(0,end); end--; } }

这段代码是基于大根堆实现的升序排序算法（堆排序），核心逻辑是「反复提取堆顶最大值，放到数组末尾，再调整剩余元素为大根堆」，最终将无序的堆数组转换为有序的升序数组。

1.end变量的核心作用

end是「当前堆的有效范围边界」，有两个核心功能：

• 功能 1：作为「已归档最大值的存放位置」，每次交换elem[0]和elem[end]，就是把最大值放到end下标归档。
• 功能 2：作为「剩余堆的有效范围上限」，调用siftdown(0, end)时，end限制了堆的有效范围为0~end-1，避免调整已归档的元素。
• 举例：初始end=5（有效元素0~5），交换后最大值归档到5，再调用siftdown(0,5)，只调整0~4的元素，5不再参与。

2.siftdown(0, end)的关键作用

• 交换堆顶和末尾元素后，新的堆顶（原末尾元素）大概率是较小值，会破坏大根堆特性。
• 调用siftdown(0, end)可以将0~end-1的剩余元素重新调整为大根堆，保证下一次循环能提取到剩余元素的最大值。
• 注意：这里传入的第二个参数是end，而不是usedsize，目的是「排除已归档的元素」，只处理剩余未排序的部分。

3. 循环终止条件：end>0

• 当end=0时，数组中只剩下标0的元素，它本身就是有序的，无需继续循环。
• 整个循环执行usedsize-1次（从usedsize-1到1），每次归档一个最大值，最终完成排序。

4. 排序结果的特性

• 基于大根堆的堆排序，结果是升序数组。
• 基于小根堆的堆排序，结果是降序数组（逻辑类似，只是每次归档最小值）。
• 注意：堆排序完成后，原有的大根堆结构会被完全破坏，数组变为有序数组，后续无法再正常使用push()、poll()等堆操作（除非重新调用createheap()构建堆）。

5. 为什么不用siftup()？

• 堆排序中调整剩余元素时，用siftdown()效率更高（时间复杂度O(log n)）。
• 新的堆顶需要 “下沉” 到正确位置，siftdown()直接从上到下调整，而siftup()是从下到上，不适合这个场景（新堆顶是从末尾交换过来的，大概率需要向下调整）。

6.为什么进行一次siftdown就能确保交换首位后是大根堆了

siftdown(0, end)看似是「一次方法调用」，但方法内部的while循环已经完成了「完整的从上到下调整」—— 它不是只比较一次，而是沿着最优子节点的线路，把新堆顶「下沉」到正确位置，最终让整个剩余堆恢复大根堆特性。

而且，执行这次siftdown()有个重要前提：交换前，剩余元素（0~end-1）本身就是一个合法的大根堆，只是堆顶被替换成了较小值，其他子树依然保持大根堆特性（这是堆排序循环的关键，每一轮都能保证这个前提）。

[3, 1, 4, 1, 5, 9]执行 heapSort() 排序 第 1 轮循环（end=5） 交换 elem [0]（9）和 elem [5]（3），数组变为 [3, 5, 4, 1, 1, 9]（9 已归档）。 调用 siftdown (0,5)，调整 0~4 元素为大根堆，数组变为 [5, 3, 4, 1, 1, 9]。 end--，end=4。 第 2 轮循环（end=4） 交换 elem [0]（5）和 elem [4]（1），数组变为 [1, 3, 4, 1, 5, 9]（5 已归档）。 调用 siftdown (0,4)，调整 0~3 元素为大根堆，数组变为 [4, 3, 1, 1, 5, 9]。 end--，end=3。 第 3 轮循环（end=3） 交换 elem [0]（4）和 elem [3]（1），数组变为 [1, 3, 1, 4, 5, 9]（4 已归档）。 调用 siftdown (0,3)，调整 0~2 元素为大根堆，数组变为 [3, 1, 1, 4, 5, 9]。 end--，end=2。 第 4 轮循环（end=2） 交换 elem [0]（3）和 elem [2]（1），数组变为 [1, 1, 3, 4, 5, 9]（3 已归档）。 调用 siftdown (0,2)，调整 0~1 元素为大根堆，数组变为 [1, 1, 3, 4, 5, 9]。 end--，end=1。 第 5 轮循环（end=1） 交换 elem [0]（1）和 elem [1]（1），数组变为 [1, 1, 3, 4, 5, 9]（1 已归档）。 调用 siftdown (0,1)，调整 0~0 元素为大根堆，数组变为 [1, 1, 3, 4, 5, 9]。 end--，end=0。

⑤建堆的时间复杂度：因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

前提假设

假设树的高度为h。

• 第 1 层：2^0个节点，需要向下移动h-1层
• 第 2 层：2^1个节点，需要向下移动h-2层
• 第 3 层：2^2个节点，需要向下移动h-3层
• 第 4 层：2^3个节点，需要向下移动h-4层
• ……
• 第h-1层：2^{h-2}个节点，需要向下移动1层

---

总移动步数推导

需要移动节点的总移动步数为：①

两边乘以 2：②

用② - ①进行错位相减：T(n)=1−h+21+22+23+24+⋯+2h−2+2h−1T(n)=20+21+22+23+24+⋯+2h−2+2h−1−hT(n)=2h−1−h

---

代入节点总数关系

因为满二叉树的节点总数n = 2^h - 1，所以h = \log_2(n+1)。代入得：T(n)=n−log2​(n+1)≈n

---

结论

因此：建堆的时间复杂度为O(N)。

二.PriorityQueue

①概念：是 Java 集合框架中一种特殊的队列，它的核心特点是「队头元素始终是队列中优先级最高的元素」，而非遵循普通队列的 FIFO（先进先出）规则。

其实就是java自带的无限容量(满了自动扩容)的小根堆

定义方法：

PriorityQueue<Integer> q1 = new PriorityQueue<>(); PriorityQueue<Integer> q2 = new PriorityQueue<>(100);//初始容量可以自己定但是定不定无影响

②常用方法：

PriorityQueue<Integer> arr=new PriorityQueue<>(); arr.offer(1); arr.offer(3); arr.offer(6); arr.offer(4); System.out.println(arr);//输出[1, 3, 6, 4]，即二叉树层序遍历 System.out.println(arr.peek());// 1 arr.poll();//int t=arr.poll(); System.out.println(arr.size());//3

③常见题目：

(1)top-k问题：找到第k大/小的元素 or 找到前k大/小的元素2

现在要找到第k小的元素：
第一种做法是 整体排序选出前k个
第二种做法是整体建立一个大小为N的小跟堆，逐步提取堆顶元素
第三种做法是把前K个元素创建为大根堆，遍历剩下的N-K个元素和堆顶元素比较，如果比堆顶元素小，则堆顶元素删除，当前元素入堆

前两个做法都是排序，然后提取，很简单的思路

但是第三个做法很特别，要找第k小，用容量为k的大根堆，反过来，如果是要找第k大，用容量为k的小根堆

首先我们不需要有序数组，先把数组的前k个放进大根堆，然后大根堆会自动排序出这三个最大的在堆顶，然后我们就遍历剩下的n-k个数，如果有比堆顶还小的，那就把堆顶元素删除，然后插入这个元素，然后自动排序，进行下一次对比

最后就会发现，大根堆中的k个就是前k小的元素，而堆顶就是第k小的元素

但是如果你想用大根堆，PriorityQueue是小根堆，你又不想手动实现大根堆，怎么办？↓

④元素的比较:在Java中，基本类型的对象可以直接比较大小。

但是如果引用类型的变量直接用>/<的话会编译失败

因为：对于用户实现自定义类型，都默认继承自Object类，而Object类中提供了equal方法，而==默认情况下调用的就是equal方法，但是该方法的比较规则是：没有比较引用变量引用对象的内容，而是直接比较引用变量的地址，但有些情况下该种比较就不符合题意

那么如果我想向优先级队列中插入某个对象时，需要对按照对象中内容来调整堆，那该如何处理呢

(1)覆写基类的equals

public class Person { // 核心属性（用于判断逻辑相等） private int id; private String name; // 非核心属性（不参与 equals 判断） private int age; // 构造器、getter/setter 省略（自行补充） public Person(int id, String name, int age) { this.id = id; this.name = name; this.age = age; } @Override public boolean equals(Object obj) { // 步骤 1：判断引用是否相等 if (this == obj) return true; // 步骤 2：判断 null + 类型是否一致 if (obj == null) return false; if (getClass() != obj.getClass()) return false; // 步骤 3：强制类型转换 Person other = (Person) obj; //下面就是判断内容一样但是地址不一样的Person // 步骤 4：逐一比较核心属性 // 基本类型（id）：== 比较 if (this.id != other.id) return false; // 引用类型（name）：处理 null + equals() 比较 if (this.name == null) { if (other.name != null) return false; } else if (!this.name.equals(other.name)) return false; // 所有核心属性相等，返回 true return true; } }

这里的this，指的是引用equals方法的：比如 a.equals(b) 这里的a就是this，b就是obj

一般覆写 equals 的套路就是上面演示的
1. 如果指向同一个对象，返回 true
2. 如果传入的为 null，返回 false
3. 如果传入的对象类型不是 目标类，返回 false
4. 按照类的实现目标完成比较，例如这里只要id，名字，一样，就认为是相同的人（按你的需求选择什么情况可以相等）

总结：不用继承，直接重写equals方法

(2)基于Comparble接口类的比较

Comparble是JDK提供的泛型的比较接口类，源码实现具体如下：

public interface Comparable<E> { // 返回值: // < 0: 表示 this 指向的对象小于 o 指向的对象 // == 0: 表示 this 指向的对象等于 o 指向的对象 // > 0: 表示 this 指向的对象大于 o 指向的对象 int compareTo(E o); }

对用用户自定义类型，如果要想按照大小与方式进行比较时：在定义类时，继承Comparble接口即可，然后在类中重写compareTo方法。

compareTo(T o)方法的返回值规则（关键，必须遵循）：

• 返回正数：表示当前对象（this）大于参数对象（o）。
• 返回0：表示当前对象（this）等于参数对象（o）。
• 返回负数：表示当前对象（this）小于参数对象（o）。

// 实现 Comparable<Student> 泛型接口，指定比较的对象类型是 Student public class Student implements Comparable<Student> { // 成员属性 private String name; // 姓名 private int score; // 成绩（核心排序字段1） private int age; // 年龄（核心排序字段2） // 构造器 public Student(String name, int score, int age) { this.name = name; this.score = score; this.age = age; } // 覆写 compareTo() 方法，定义自然排序规则 @Override public int compareTo(Student other) { // 规则1：先按成绩降序排列（当前对象成绩 > 其他对象成绩 → 返回负数，因为降序和默认升序相反） // 成绩降序：other.score - this.score（如果 this.score > other.score，结果为负，符合 compareTo 返回负数表示 this 小于 other（降序效果）） int scoreCompare = other.score - this.score; if (scoreCompare != 0) { return scoreCompare; // 成绩不同，直接返回成绩比较结果 } // 规则2：成绩相同，按年龄升序排列（当前对象年龄 > 其他对象年龄 → 返回正数，符合升序规则） // 年龄升序：this.age - other.age（默认升序规则） return this.age - other.age; } // 重写 toString() 方法，方便打印输出 @Override public String toString() { return "Student{name='" + name + "', score=" + score + ", age=" + age + "}"; } // getter/setter 可选，此处省略 }

简单版：

public class Stu implements Comparable<Stu>{ int score1; int score2; String name; public Stu(int score1,int score2,String name){ this.score1=score1; this.score2=score2; this.name=name; } @Override public int compareTo(Stu o){ int res = this.score1-o.score1; if(res!=0){ return res; } return this.score2-o.score2; } }

注意点：

1.implements Comparable<Student>，要写类名

2.返回一定是返回一个int数值，如果返回值>0,那么就说明调用者>括号内者，=，<同理

总结：在自定义类里继承接口后重写方法

(3)基于比较器比较(继承Comparator接口)

public class Stu { int score1; String name; // 构造器 public Stu(int score1, String name) { this.score1 = score1; this.name = name; } // 覆写 toString()，方便打印结果 @Override public String toString() { return "Stu{score1=" + score1 + ", name='" + name + "'}"; } }

import java.util.Comparator; // 显式实现 Comparator<Stu> 接口，指定泛型类型为 Stu public class StuComparator implements Comparator<Stu> { // 覆写 compare() 方法，这是接口唯一的抽象方法 @Override public int compare(Stu s1, Stu s2) { // 简单规则：按 score1 升序排列（核心逻辑，极简） // 返回值规则：<0 → s1排在s2前面；=0 → 逻辑相等；>0 → s1排在s2后面 return s1.score1 - s2.score1; } }

public class TestComparatorWithoutSort { public static void main(String[] args) { // 1. 创建两个待比较的 Stu 对象 Stu stu1 = new Stu(85, "李四"); Stu stu2 = new Stu(90, "张三"); // 2. 创建自定义 Comparator 实例（比较工具） StuComparator stuComparator = new StuComparator(); // 3. 手动调用 compare() 方法，比较 stu1 和 stu2，接收返回值 int compareResult = stuComparator.compare(stu1, stu2); // 4. 根据返回值，判断两个对象的大小关系（核心：解读返回值） if (compareResult < 0) { System.out.println("结论：stu1 < stu2（按 score1 升序，stu1 应排在 stu2 前面）"); } else if (compareResult == 0) { System.out.println("结论：stu1 = stu2（按 score1 比较，两者逻辑相等）"); } else { System.out.println("结论：stu1 > stu2（按 score1 升序，stu1 应排在 stu2 后面）"); } } }

总结：要写两个类。一个是自定义Stu类(不需要继承)，另一个是继承Comparator 接口(<>里面依旧要写自定义类)用来比较的类。然后实例化比较类，然后就可以调用里面的比较方法获取返回值，根据返回值> < = 0来执行对应操作

因此：PriorityQueue想从小根堆变成大根堆：

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); 加上一个重写的接口即可，这里的Comparator.reverseOrder()是java自带的取反接口

当然也有手动重写接口：

// 第一步：自己手动实现 Comparator 接口，定义大根堆的比较规则（降序） class MyMaxHeapComparator implements Comparator<Integer> { // 覆写 compare() 方法，实现降序逻辑（对应大根堆） @Override public int compare(Integer a, Integer b) { // 大根堆需要：数值大的元素优先级高，堆顶为最大值 // 降序逻辑：b - a（返回正数表示 a < b，负数表示 a > b，0 表示相等） return b - a; } } // 第二步：使用自定义比较器构建大根堆 public class CustomMaxHeapDemo { public static void main(String[] args) { // 传入自己实现的 MyMaxHeapComparator，构建大根堆 PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new MyMaxHeapComparator());

最后一步这样也可以： MyMaxHeapComparator myMaxHeapComparator=new MyMaxHeapComparator() PriorityQueue<Integer> maxHeap = new PriorityQueue<>(myMaxHeapComparator); 总之要实例化/匿名类