★ FEATURED ARTICLE 一堆1概念1.1 堆的概念堆是一种特殊的完全二叉树它保证每个父节点的值都不大于或不小于其子节点的值因此堆顶永远是最大或最小的元素。其具有以下性质堆中某个节点的值总是不大于或不小于其父节点的值堆总是一棵完全二叉树堆又分为大根堆和小根堆父节点比子节点大的是大根堆反之则是小根堆。1.2 堆的存储因为堆是一棵完全二叉树所以能以按层序从上到下、从左到右的顺序存储在数组中根节点为下标0。存储结构如下图所示注在二叉树章节我们曾提及二叉树分为链式存储和线性存储。但若使用数组存储非完全二叉树其会存在大量空节点造成空间上的浪费而完全二叉树则可以按照层序遍历顺序进行存储不会浪费空间因此一般的完全二叉树 使用线性存储非完全二叉树 使用链式存储并且在调整堆时我们可以使用到以下性质获取节点下标简单来说就是由父得子左孩子下标 父 * 2 1右孩子下标 父 * 2 2由子得父父节点下标 子 - 1/ 22实现及重要方法讲解接下来将以小根堆为例进行讲解代码中所有抛出的异常都是自定义异常类。2.1 类定义由概念部分我们可知堆是一颗完全二叉树可以使用数组进行存储因此定义elem数组作为基本存储结构定义usedSize变量用于记录堆中有效元素个数定义DEFAULT_INITIAL_CAPACITY 作为默认堆容量。public class MyHeap { private int[] elem; private int usedSize 0; private static final int DEFAULT_INITIAL_CAPACITY 11; }2.2 siftUp向上调整在向上调整时siftUp函数一般接收待调整的子节点下标child作为形参列表其执行逻辑如下1若是child 0则说明往上还有节点故进入循环继续调整2利用父节点下标 子 - 1/ 2这一性质获取到父节点下标使用parent记录3比较子节点和父节点值大小3.1子节点值 父节点值父节点大于子节点违反小根堆性质因此交换父子节点元素值将其调整为小根堆再让child parent继续向上调整因为交换后修改了以parent为子节点的树故向上调整即是调整受影响的树3.2子节点值 父节点值父节点小于等于子节点是小根堆无需调整直接返回即可默认整棵树是小根堆因此当目前子树是小根堆时即无需再调整4循环结束则说明整棵树调整完毕调整流程如下图所示代码如下所示/** * 向上调整 * param child 新插入节点位置 */ private void siftUp(int child) { // 当child0时则说明已调整完整棵树 while(child 0) { // 获取父节点下标 int parent (child - 1) / 2; if(this.elem[child] this.elem[parent]) { // 父节点子节点 交换元素并使child parent向上继续调整 swap(child, parent); child parent; } else { // 父节点子节点 符合小根堆无需调整直接返回 break; } } }2.3 siftDown向下调整在向下调整时siftDown函数一般需要接收待调整子树的父节点下标parent与堆有效元素个数len用于明确向下调整的结束位置这两个参数其执行逻辑如下1利用左孩子下标 父 * 2 1这一性质获取到左孩子下标使用child记录2若是child len则说明左孩子存在进入循环3判断右孩子是否存在若是右孩子存在 且 右孩子值左孩子值则child保存右孩子下标child保存左右孩子中值最小的那个4比较child子节点与parent父节点值大小4.1子节点值 父节点值父节点大于子节点违反小根堆性质因此交换父子节点元素值将其调整为小根堆再执行parent childchild child * 2 1继续向下调整因为交换后修改了以child为父节点的树故向下调整即是调整受影响的树4.2子节点值 父节点值父节点小于等于子节点是小根堆无需调整直接返回即可默认整棵树是小根堆因此当目前子树是小根堆时即无需再调整5循环结束则说明整棵树调整完毕注使用len确定向下调整的结束位置其本质是判断当前节点是否还有左右子树。若是childlen则说明左右子树不存在没有受影响的子树整颗树调整完毕。调整流程如下图所示代码如下所示/** * 向下调整 * param parent 根节点下标 * param len 调整界限 */ private void siftDown(int parent, int len) { // 获取左孩子下标 int child parent * 2 1; // 左孩子存在则进入循环调整 while(child len) { // child保存左右孩子中值最小的那个 if(child 1 len this.elem[child 1] this.elem[child]) { child ; } if(this.elem[child] this.elem[parent]) { // 调整本树并继续向下调整 swap(child, parent); parent child; child child * 2 1; } else { break; } } }2.4 add / poll / peek1 add 在堆中插入元素新增逻辑如下1判满若满则扩容2不满则将尾插新元素3向上调整受影响的位置使其在插入后仍能保证是小根堆4维护有效元素个数流程如下图所示代码如下图所示/** * 在堆中插入元素 * 插入到尾部然后向上调整 * param val 待插入元素 */ public void add(int val) { // 判满并扩容1.5倍 if(isFull()) { grow(); } // 尾插新元素 this.elem[this.usedSize] val; // 向上调整 siftUp(this.usedSize); this.usedSize ; }2 poll 删除堆顶元素删除逻辑如下1判空若空则抛出异常具体操作视实际场景需求而定2非空交换首尾元素维护有效元素个数交换后就执行usedSize--也就是逻辑删除尾部元素并且也利于向下调整时传递结束位置此处代码我先维护了有效元素个数是因为尾节点下标为usedSize-1故提前处理3向下调整根节点使受交换影响的树重新成为小根堆流程如下图所示代码如下所示/** * 弹出堆顶元素 * 首尾交换然后调整下标为0的树 * return int */ public int poll() { // 判空并抛出异常 if(isEmpty()) { throw new HeapEmptyException(堆为空无法执行删除操作); } // 记录堆顶元素 int oldVal this.elem[0]; // 交换首尾元素并维护有效元素个数 this.usedSize --; swap(0, this.usedSize); // 向下调整根节点 siftDown(0, this.usedSize); return oldVal; }3 获取堆顶元素获取逻辑较为简单如下1判空若空则抛出异常具体操作视实际场景需求而定2非空返回堆顶元素下标为0的值代码如下所示/** * 获取堆顶元素 * return int */ public int peek() { // 判空并抛出异常 if(isEmpty()) { throw new HeapEmptyException(堆为空无法执行获取堆顶元素操作); } return this.elem[0]; }2.5 heapify建堆我们通常使用向下调整的方式建堆流程如下1获取最后一棵子树的父节点从该节点开始逐树向下调整注最后一棵子树父节点下标 最后一个有效元素下标 - 1/ 22调整完毕后建堆完成流程如下图所示代码如下所示/** * 建堆 */ private void heapify() { // 从最后一棵子树开始逐树向下调整 for(int parent (this.usedSize - 1 - 1) / 2; parent 0; parent --) { siftDown(parent, this.usedSize); } }2.6 扩容与构造器1 构造器在本次实现中我定义了三个构造方法分别是1无参构造方法为底层数组开辟默认大小空间/** * 无参构造方法 * */ public MyHeap() { this.elem new int[DEFAULT_INITIAL_CAPACITY]; }2带有一个初始容量的构造方法若是给定的初始容量合法则开辟指定大小空间否则使用默认容量/** * 给定带有一个初始容量的构造方法 */ public MyHeap(int capacity) { // 校验capacity if(capacity 0 || capacity (Integer.MAX_VALUE - 8)) { this.elem new int[DEFAULT_INITIAL_CAPACITY]; } else { this.elem new int[capacity]; } }3带有一个初始化序列的构造方法按照给定的初始化序列建堆此处涉及开辟内存需要校验合法性。/** * 给定带有一个初始化序列的构造方法 * param initialArray 初始化序列 */ public MyHeap(int[] initialArray) { // 判空 if(initialArray null) { this.elem new int[DEFAULT_INITIAL_CAPACITY]; } else { // 校验数组 if(initialArray.length Integer.MAX_VALUE - 8) { throw new IllegalArgumentException(初始数组过大); } // 开辟内存 long cap Math.max(1, (long)(initialArray.length * 1.5)); if(cap Integer.MAX_VALUE - 8) { cap Integer.MAX_VALUE - 8; } this.elem new int[(int)cap]; // 写入数组 for(int i 0; i initialArray.length; i ) { this.elem[i] initialArray[i]; this.usedSize ; } // 建堆 heapify(); } }2 扩容使用1.5倍扩容/** * 1.5倍扩容 */ private void grow() { // 扩容时至少保证容量大于当前的usedSize int oldCap this.elem.length; int minCap this.usedSize 1; long newCapacity Math.max(minCap, (long)(oldCap * 1.5)); // 判断新容量合法性 if(newCapacity (Integer.MAX_VALUE - 8)) { if(oldCap Integer.MAX_VALUE - 8) { throw new HeapFullException(堆容量已达上限); } newCapacity Integer.MAX_VALUE - 8; } // 扩容 this.elem Arrays.copyOf(this.elem, (int)newCapacity); }二优先级队列1基于堆实现优先级队列优先级队列是一种抽象的数据类型它与普通队列先进先出的规则不同每个元素都有一个优先级出队时总是优先级最高最低的元素被取出。因为它是一种抽象的数据类型因此存在多种实现方式其中堆是实现它最经典、最常用的方式之一。堆实现优先级队列与实现堆本身的代码高度相似。为避免重复实现并保持封装不把堆的全部 public 方法暴露给使用者此处采用组合 委托的方式基于上文的小根堆实现一个最小优先的优先级队列代码如下所示/** * 基于堆实现优先级队列 * author 14993 * date 2026/10/21 */ public class MyPriorityQueue { private MyHeap heap; /** * 无参构造方法 */ public MyPriorityQueue() { heap new MyHeap(); } /** * 给定带有一个初始容量的构造方法 * param capacity 初始容量 */ public MyPriorityQueue(int capacity) { heap new MyHeap(capacity); } /** * 给定带有一个初始化序列的构造方法 * param initialArray 初始化序列 */ public MyPriorityQueue(int[] initialArray) { heap new MyHeap(initialArray); } /** * 入队 * param val 新元素 */ public void offer(int val) { heap.add(val); } /** * 出队 * return int */ public int poll() { return heap.poll(); } /** * 获取队头元素 * return int */ public int peek() { return heap.peek(); } /** * 判空 * return boolean */ public boolean isEmpty() { return heap.isEmpty(); } /** * 获取有效元素个数 * return int */ public int size() { return heap.size(); } }通过上面代码可以看出MyPriorityQueue持有一个 MyHeap成员并将 offer/poll/peek等操作委托给该成员完成。也就是说它是以组合方式复用堆这一数据结构来实现优先级队列这一抽象数据类型堆是底层实现优先级队列是对外呈现的接口。2Java集合类中的实现优先级队列在Java中提供了两种实现分别是PriorityQueue和PriorityBlockingQueuePriorityQueue是线程不安全的PriorityBlockingQueue是线程安全的。其中PriorityQueue具有以下特性默认是小根堆默认容量为11可以传递Comparator比较器并且我们可以通过修改传递比较器的比较逻辑去定义优先级。例如PriorityQueue默认小根堆传递Comparator.reverseOrder()可变为大根堆。若是没有传递Comparator比较器则必须实现Comparable接口否则无法比较并且会抛出异常扩容时旧容量小于64时约按2倍扩容new old*22否则按1.5倍扩容
阅读完成 · 觉得有帮助？
