堆实现

相关源文件

• DIRECTORY.md
• src/main/java/com/thealgorithms/ciphers/XORCipher.java
• src/main/java/com/thealgorithms/conversions/IntegerToEnglish.java
• src/main/java/com/thealgorithms/datastructures/heaps/EmptyHeapException.java
• src/main/java/com/thealgorithms/datastructures/heaps/FibonacciHeap.java
• src/main/java/com/thealgorithms/datastructures/heaps/GenericHeap.java
• src/main/java/com/thealgorithms/datastructures/heaps/Heap.java
• src/main/java/com/thealgorithms/datastructures/heaps/HeapElement.java
• src/main/java/com/thealgorithms/datastructures/heaps/MaxHeap.java
• src/main/java/com/thealgorithms/datastructures/heaps/MinHeap.java
• src/main/java/com/thealgorithms/datastructures/heaps/MinPriorityQueue.java
• src/test/java/com/thealgorithms/ciphers/XORCipherTest.java
• src/test/java/com/thealgorithms/conversions/IntegerToEnglishTest.java
• src/test/java/com/thealgorithms/datastructures/heaps/FibonacciHeapTest.java
• src/test/java/com/thealgorithms/datastructures/heaps/GenericHeapTest.java
• src/test/java/com/thealgorithms/datastructures/heaps/HeapElementTest.java
• src/test/java/com/thealgorithms/datastructures/heaps/MaxHeapTest.java
• src/test/java/com/thealgorithms/datastructures/heaps/MinHeapTest.java
• src/test/java/com/thealgorithms/datastructures/heaps/MinPriorityQueueTest.java

本文档详细概述了此 Java 存储库中提供的堆数据结构实现。堆是满足堆属性的特化树状数据结构，通常用于优先队列操作、堆排序和图算法。

1. 堆数据结构简介

堆是满足特定排序属性的完全二叉树。存在两种主要变体：

• 最小堆：每个父节点的键小于或等于其子节点的键。
• 最大堆：每个父节点的键大于或等于其子节点的键。

常见的堆操作

操作	时间复杂度	描述
插入	O(log n)	向堆中添加新元素
删除	O(log n)	删除特定位置的元素
提取最小值/最大值	O(log n)	删除并返回最小值/最大值元素
获取最小值/最大值	O(1)	检索最小值/最大值元素而不删除它
堆化	O(n)	将无序数组转换为堆

堆结构

来源：src/main/java/com/thealgorithms/datastructures/heaps/MinHeap.java src/main/java/com/thealgorithms/datastructures/heaps/MaxHeap.java

2. 核心组件

2.1 堆接口

该存储库定义了一个通用的 Heap 接口，该接口标准化了各种堆实现的基本操作。

来源：src/main/java/com/thealgorithms/datastructures/heaps/Heap.java

2.2 HeapElement 类

该 HeapElement 类表示堆中存储的元素，并为比较和排序元素提供了基础。

该类提供：

• 接受不同数值类型的多个构造函数。
• 存储键（用于排序）和附加信息。
• 用于比较、相等性和字符串表示的方法。

来源：src/main/java/com/thealgorithms/datastructures/heaps/HeapElement.java

3. 堆实现

3.1 最小堆 (MinHeap)

MinHeap 实现了一个二叉堆，其中每个父节点的键都小于或等于其子节点的键，确保最小值始终位于根节点。

主要功能

• 完全二叉树结构。
• 根包含最小值。
• 插入和删除操作的时间复杂度为 O(log n)。
• 访问最小值的时间复杂度为 O(1)。

实现细节

• 使用 ArrayList<HeapElement> 进行存储。
• 堆操作使用 1 基索引（内部计算）。
• 提供诸如 heapifyDown、toggleUp 和 toggleDown 等辅助方法。
• 实现了 Heap 接口。

使用示例

来源：src/main/java/com/thealgorithms/datastructures/heaps/MinHeap.java

3.2 最大堆 (MaxHeap)

MaxHeap 实现了一个二叉堆，其中每个父节点的键都大于或等于其子节点的键，确保最大值始终位于根节点。

主要功能

• 完全二叉树结构。
• 根包含最大值。
• 插入和删除操作的时间复杂度为 O(log n)。
• 访问最大值的时间复杂度为 O(1)。

实现细节

• 使用 ArrayList<HeapElement> 进行存储。
• 堆操作使用 1 基索引。
• 提供与 MinHeap 类似的辅助方法，但具有相反的比较逻辑。
• 实现了 Heap 接口。

使用示例

来源：src/main/java/com/thealgorithms/datastructures/heaps/MaxHeap.java

3.3 GenericHeap

GenericHeap 是一个类型安全的实现，它可以使用任何 Comparable 类型工作，默认作为最大堆。

主要功能

• 可与任何实现 Comparable 的类型配合使用。
• 使用哈希映射进行高效的元素查找。
• 支持元素的优先级更新。
• 通过上溯堆化 (upheapify) 和下溯堆化 (downheapify) 操作维护堆属性。

实现细节

• 使用 ArrayList<T> 作为主要堆存储。
• 使用 HashMap<T, Integer> 来跟踪元素位置。
• 通过维护位置映射，提供更高效的元素更新。

使用示例

来源：src/main/java/com/thealgorithms/datastructures/heaps/GenericHeap.java

3.4 FibonacciHeap

FibonacciHeap 是一种高级堆实现，它为多个操作提供了更优越的理论时间复杂度。

主要功能

• 插入和减少键 (decrease-key) 操作的摊销时间为 O(1)。
• 删除和删除最小值 (delete-min) 操作的摊销时间为 O(log n)。
• 高效的合并 (melding) 操作（组合堆）时间为 O(1)。
• 维护满足最小堆属性的树集合。

实现细节

• 使用循环链表结构组织树。
• 包含用于树节点的内部类 HeapNode。
• 实现诸如合并 (meld)、剪切 (cut) 和级联剪切 (cascadingCuts) 等操作。
• 维护 totalLinks 和 totalCuts 等统计信息。
• 使用黄金比例进行内部计算。

使用示例

来源：src/main/java/com/thealgorithms/datastructures/heaps/FibonacciHeap.java

3.5 MinPriorityQueue

MinPriorityQueue 是一种专用数据结构，它维护最小堆属性，其中最小元素具有最高优先级。

主要功能

• 基于数组的实现，具有固定容量。
• 插入和删除操作的时间复杂度为 O(log n)。
• 访问最小值的时间复杂度为 O(1)。
• 包含堆排序功能。

实现细节

• 使用整数数组进行存储。
• 堆操作使用 1 基索引。
• 提供插入、删除和查看 (peeking) 的方法。

使用示例

来源：src/main/java/com/thealgorithms/datastructures/heaps/MinPriorityQueue.java

4. 常用堆操作

4.1 插入

插入过程包括：

1. 将元素添加到堆的末尾。
2. 执行“上溯堆化”或“toggleUp”以维护堆属性。

来源：src/main/java/com/thealgorithms/datastructures/heaps/MinHeap.java210-217 src/main/java/com/thealgorithms/datastructures/heaps/MaxHeap.java187-194

4.2 删除

删除过程包括：

1. 用最后一个元素替换要删除的元素。
2. 删除最后一个位置。
3. 执行“下溯堆化”或“toggleDown”以维护堆属性。

来源：src/main/java/com/thealgorithms/datastructures/heaps/MinHeap.java222-244 src/main/java/com/thealgorithms/datastructures/heaps/MaxHeap.java199-221

4.3 提取最小值/最大值

此操作：

1. 检索根元素（最小值或最大值）。
2. 删除根元素。
3. 重构堆以维护堆属性。

来源：src/main/java/com/thealgorithms/datastructures/heaps/MinHeap.java198-205 src/main/java/com/thealgorithms/datastructures/heaps/MaxHeap.java175-182

5. 附加工具

5.1 EmptyHeapException

当尝试在空堆上执行操作时抛出的自定义异常。

来源：src/main/java/com/thealgorithms/datastructures/heaps/EmptyHeapException.java

6. 应用

本存储库中的堆实现用于：

1. 优先队列操作：根据优先级管理元素。
2. 堆排序：高效的排序算法，时间复杂度为 O(n log n)。
3. 图算法：Dijkstra 算法、Prim 算法等的组成部分。
4. 选择问题：查找第 k 小/第 k 大元素。

有关使用这些堆的特定算法的信息，请参阅 搜索和排序。

7. 实现比较

堆类型	最佳使用场景	插入	提取最小值/最大值	减少键 (Decrease Key)	合并 (Meld)
MinHeap/MaxHeap	简单的优先队列。	O(log n)	O(log n)	O(log n)	O(n)
GenericHeap	类型安全的⭑操作。	O(log n)	O(log n)	O(log n)	不适用
FibonacciHeap	频繁插入和减少键。	O(1)*	O(log n)*	O(1)*	O(1)
MinPriorityQueue	固定容量的应用。	O(log n)	O(log n)	不适用	不适用

*摊销时间复杂度。

来源：src/main/java/com/thealgorithms/datastructures/heaps/MinHeap.java src/main/java/com/thealgorithms/datastructures/heaps/MaxHeap.java src/main/java/com/thealgorithms/datastructures/heaps/GenericHeap.java src/main/java/com/thealgorithms/datastructures/heaps/FibonacciHeap.java src/main/java/com/thealgorithms/datastructures/heaps/MinPriorityQueue.java