企业官网建设流程全解析

一，堆

1，概念

1.1 堆的概念

堆是一种特殊的完全二叉树，它保证每个父节点的值都不大于（或不小于）其子节点的值，因此堆顶永远是最大（或最小）的元素。其具有以下性质：

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

堆又分为大根堆和小根堆，父节点比子节点大的是大根堆，反之则是小根堆。

1.2 堆的存储

因为堆是一棵完全二叉树，所以能以按层序（从上到下、从左到右）的顺序存储在数组中（根节点为下标0）。存储结构如下图所示：

注：
在二叉树章节我们曾提及：二叉树分为链式存储和线性存储。但若使用数组存储非完全二叉树，其会存在大量空节点，造成空间上的浪费；而完全二叉树则可以按照层序遍历顺序进行存储，不会浪费空间，因此一般的：

完全二叉树 ==> 使用线性存储

非完全二叉树 ==> 使用链式存储

并且在调整堆时，我们可以使用到以下性质获取节点下标：

简单来说就是

• 由父得子：左孩子下标 = （父 * 2） + 1；右孩子下标 = （父 * 2） + 2
• 由子得父：父节点下标 = （子 - 1）/ 2

2，实现及重要方法讲解

接下来将以小根堆为例进行讲解，代码中所有抛出的异常都是自定义异常类。

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) { // 当child<=0时则说明已调整完整棵树 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 = child，child = （child * 2）+ 1继续向下调整（因为交换后修改了以child为父节点的树，故向下调整即是调整受影响的树）

4.2子节点值 >= 父节点值：父节点小于等于子节点，是小根堆，无需调整，直接返回即可（默认整棵树是小根堆，因此当目前子树是小根堆时即无需再调整）

5，循环结束则说明整棵树调整完毕

注：

使用len确定向下调整的结束位置，其本质是判断当前节点是否还有左右子树。若是child>=len，则说明左右子树不存在，没有受影响的子树，整颗树调整完毕。

调整流程如下图所示：

代码如下所示：

/** * 向下调整 * @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 / peek

<1> 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）/ 2

2，调整完毕后建堆完成

流程如下图所示：

代码如下所示：

/** * 建堆 */ 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等操作委托给该成员完成。也就是说，它是以组合方式复用堆这一数据结构，来实现优先级队列这一抽象数据类型；堆是底层实现，优先级队列是对外呈现的接口。

2，Java集合类中的实现

优先级队列在Java中提供了两种实现，分别是PriorityQueue和PriorityBlockingQueue，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的。

其中PriorityQueue具有以下特性：

1. 默认是小根堆
2. 默认容量为11，可以传递Comparator比较器，并且我们可以通过修改传递比较器的比较逻辑去定义优先级。例如PriorityQueue默认小根堆，传递Comparator.reverseOrder()可变为大根堆。
3. 若是没有传递Comparator比较器，则必须实现Comparable接口，否则无法比较并且会抛出异常
4. 扩容时，旧容量小于64时约按2倍扩容（new = old*2+2），否则按1.5倍扩容