数据结构之堆(Java\Python双语实现)
·
一.堆(heap)的概念
在Computer Science中，堆(Heap)是一个重要的概念，主要有两层含义
1.数据结构中的堆
1.是一种特殊的二叉树
堆是一种特殊的树形结构，通常是一棵完全二叉树（满二叉树的一种特例，满二叉树是每个节点要么有2个子节点要么就没有子节点，而完全二叉树是除了最后一层，其他层都是满的，即其他层每个节点的父节点都有两个孩子，并且完全二叉树的最后一层的节点要靠左排列）
类型：
| 类型 | 特性 |
|---|---|
| 最大堆（Max Heap） | 每个节点的值都大于或等于其子节点的值，根节点是最大值 |
| 最小堆（Min Heap） | 每个节点的值都小于或等于其子节点的值，根节点是最小值 |
最大堆：
[90] <-- 最大值在根部
/ \
[50] [80]
/ \ / \
[30] [40] [70] [60]最小堆：
[30] <-- 最小值在根部
/ \
[40] [60]
/ \ / \
[50] [90] [70] [80]2.堆的存储
堆在逻辑上是树形结构，但在计算机内存中实际使用数组存储，这种巧妙的映射是堆高效的关键
核心映射关系：
假设有一个最小堆，包含元素：[10, 20, 30, 40, 50, 60, 70]
逻辑视图（从索引0开始存储数据，也可以从1开始，但是找父子关系的时候规律要稍微变化）：
索引: 0
[10]
/ \
索引: 1 / \ 索引: 2
[20] [30]
/ \ / \
索引: 3 / \4 /5 \6
[40] [50][60] [70]物理视图（数组存储）：
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ ← 索引
├─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ 10 │ 20 │ 30 │ 40 │ 50 │ 60 │ 70 │ ← 值
└─────┴─────┴─────┴─────┴─────┴─────┴─────┘索引计算公式：
对于数组中任意索引i的节点：
| 关系 | 公式 | 示例 (i=1) |
| 父节点 | (i - 1) // 2 | (1-1)//2 = 0 | // 代表下取整
| 左孩子 | 2 * i + 1 | 2×1+1 = 3 |
| 右孩子 | 2 * i + 2 | 2×1+2 = 4 |
内存布局示意：
内存地址（简化）: 0x1000 0x1004 0x1008 0x100C 0x1010 0x1014 0x1018
┌──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │ 60 │ 70 │
└──────┴──────┴──────┴──────┴──────┴──────┴──────┘
↑ ↑
堆顶 堆尾
(最小值) (最后元素)连续存储：数组在内存中是连续的，这使得缓存友好，访问速度快
3.常见应用
- 优先队列（Priority Queue）
- 堆排序算法
- 图算法中的最短路径（如Dijkstra算法）
- 任务调度系统
2.内存管理中的堆
在程序内存管理中，堆是指动态内存分配区域：
特点：
| 特性 | 说明 |
|---|---|
| 分配方式 | 程序员手动分配和释放（如C/C++中的 malloc/free、new/delete） |
| 生命周期 | 由程序员控制，不会自动释放 |
| 访问速度 | 比栈慢，但更灵活 |
| 大小限制 | 通常比栈大得多 |
与栈的区别：
┌─────────────┐
│ 栈 │ ← 自动管理，存放局部变量
│ (Stack) │
├─────────────┤
│ 堆 │ ← 手动管理，存放动态分配的对象
│ (Heap) │
└─────────────┘3.两种不同概念的堆的总结
| 方面 | 数据结构堆 | 内存管理堆 |
|---|---|---|
| 本质 | 一种树形数据结构 | 内存分配区域 |
| 用途 | 优先队列、排序等 | 动态存储数据 |
| 管理 | 算法自动维护 | 程序员手动管理 |
二.数据结构的堆(Java实现)
堆的实现
package algorithm.datastructure.heapdemo;
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
/*public class Heap<T extends Comparable<T>>
* 这是Java泛型中的类型边界语法
* 从左到右：T是泛型类型参数, extends表示类型边界(上界), Comparable<T>表示T可以和自己比较
* 这行代码的含义是：T必须是实现了Comparable<T>接口的类型
* 问题1: 什么是Comparable接口
* Comparable接口是Java用于对象比较的标准接口
* 在IDEA中鼠标移到下面的Comparable上，快捷键Ctrl+B(B代表Base)(或者Ctrl+鼠标左键单击)查看Comparable接口的声明
* public interface Comparable<T> {
* int compareTo(T other); // 这个方法返回int，表示比较结果
* }
* compareTo方法返回值是一个整数，通过正负零表示大小关系
* 返回负数，表示当前对象小于其他对象
* 返回0，表示当前对象等于其他对象
* 返回正数，表示当前对象大于其他对象
* 问题2: 什么是泛型边界
* 泛型边界是Java泛型中用于限制类型参数范围的机制，用于确保泛型类型的安全
* 没有边界，则T可以是任何类型，如:
* class Box<T> {}
* 有边界，则T必须是Number的子类，如:
* class Box<T extends Number>
而extends就是实现泛型边界上界的关键字，还有泛型边界下届super(限制T必须是某类型的子类)、多重边界&(限制T必须同时满足多个条件)
* 问题3: 为什么要用extends而不用implements来实现Comparable接口
* 理解了问题2，就很容易理解问题3
* 在泛型中，无论是类还是接口，类型边界都有extends(用于上边界)，这是Java的语法设计
* 泛型边界不能用implements
* 普通类：继承父类用extends、实现接口用implements
* 泛型类型边界：边界是类用extends、边界是接口也用extends（语法统一、语义清晰、基于历史的设计）
* 问题4: 接口可以继承吗
* 可以！接口之间用extends继承
* 问题5: 对问题3提出的问题的纠正
* <T extends Comparable<T>>中：
* T 表示Heap类的参数都是T类型，即Heap存储的元素都是T类型
* 而T extends Comparable<T>是泛型边界 表示T类型只能和同类型T进行比较*/
public class Heap<T extends Comparable<T>> {
private List<T> heap;
// List是Java集合框架中的核心接口，用于存储有序、可重复的元素集合
// 这里用List而没有用具体的类，这是面向接口编程，可以灵活换成LinkedList类等其他实现，且不依赖与具体实现类
private boolean maxHeap; // 堆类型标志，true表示最大堆，false表示最小堆
public Heap(boolean maxHeap) {
// 多态: List<T> heap = new ArrayList<>(); List是引用类型，ArrayList是heap的实际类型
// 不能这样：List<T> heap = new List<>();
// List是接口，而接口不能实例化，且接口没有构造函数，接口中的方法默认是抽象方法（接口的作用是定义实现该接口的类的规范）
this.heap = new ArrayList<> (); // 这里是Java7及之后的写法，使用菱形操作符时可以省略泛型类型，编译器会根据左侧声明的类型自动判断右侧的泛型类型(这里判断为Integer)
this.maxHeap = maxHeap;
}
private int parent(int i) { return (i - 1) / 2; }
private int leftChild(int i) { return 2 * i + 1; }
private int rightChild(int i) { return 2 * i + 2; }
// 根据maxHeap标志选择比较方向
private boolean compare(T a, T b) {
return maxHeap ? a.compareTo(b) > 0 : a.compareTo(b) < 0;
// 三元运算符
// maxHeap为条件判断
// a.compareTo(b) > 0为true时返回true，否则返回false
/*三元运算符运用简化简单的if-else逻辑
* 基本语法：条件表达式 ? 表达式1 : 表达式2
* 说明： 条件表达式是布尔类型的条件，当条件为true时执行表达式1，条件为false时执行表达式2*/
}
private void swap(int i, int j) {
T temp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, temp);
}
// 向上调整堆，维护堆的性质
// 当新元素插入到堆末尾时，可能破话堆的性质。这时候就需要将新元素“上浮”到正确位置
// 从而确保堆序性（父节点与子节点的大小关系）不被破坏
private void heapifyUp(int i) {
// i是新插入元素的索引
while (i > 0) { // 只要没到根节点（索引为0）
int p = parent(i); // 获取父节点
// 如果当前节点应该排在父节点前面，则需要交换
if (compare(heap.get(i), heap.get(p))) {
swap(i, p);
i = p; // 更新索引，继续向上检查
} else {
break; // 堆序性以满足，停止调整
}
}
}
// 向下调整堆，维护堆的性质
// 当堆顶元素被删除/替换后，可能破坏堆的性质，需要将新堆顶元素“下沉”到正确位置
private void heapifyDown(int i) {
int n = heap.size();
while (true) { // 无限循环，直到break
int target = i; // 记录当前“最优先”的节点
int left = leftChild(i); // 左孩子索引
int right = rightChild(i); // 右孩子索引
// 如果左孩子存在且应该优先与当前节点
if (left < n && compare(heap.get(left), heap.get(target))) {
target = left; // 更新target为左孩子
}
// 如果右孩子存在其应该优先与当前节点
if (right < n && compare(heap.get(right), heap.get(target))) {
target = right; // 更新target为右孩子
}
// 如果target变了，则需要交换
if (target != i) {
swap(i, target); // 交换当前节点和更优先的孩子
i = target; // 更新索引，继续向下检查
} else {
break; // 堆序性满足，停止调整
}
}
}
public void push(T val) {
heap.add(val);
heapifyUp(heap.size() - 1);
}
public void printAll() {
System.out.println(heap);
}
// 弹出并返回堆顶元素
// 删除堆顶元素之后，问题是如何保持堆的性质
// 方案1：将后续元素全部前移，时间复杂度O(n),太慢了
// 方案2：将最后一个元素放到堆顶，然后“下沉”到正确位置，时间复杂度O(log n)
public T pop() {
if (heap.isEmpty()) {
throw new NoSuchElementException("堆为空");
}
T result = heap.getFirst(); // 获取堆顶元素 等价于 T result = heap.get(0);
heap.set(0, heap.get(heap.size() - 1)); // 用堆底元素替换堆顶元素
heap.remove(heap.size() - 1); // 删除堆底元素 也可以用List的removeLast方法
if (!heap.isEmpty()) {
heapifyDown(0); // 如果堆不为空，向下调整
}
return result; // 返回堆顶元素
}
// 返回堆顶元素
public T peek() {
if (heap.isEmpty()) {
throw new NoSuchElementException("堆为空");
}
return heap.get(0);
}
public int size() {
return heap.size();
}
public boolean isEmpty() {
return heap.isEmpty();
}
}
assert断言
写一个测试类
package algorithm.datastructure.heapdemo;
public class HeapTest {
public static void main(String[] args) {
testMinHeap();
}
static void testMinHeap() {
// 最小堆
Heap<Integer> minHeap = new Heap<>(false);
assert minHeap.isEmpty() : "新堆应该为空";
}
}发现没有任何输出，这是因为Java是默认禁用assert断言功能的
要在IDE即集成开发环境（integrated development environment）中启用这个功能：
| IDE | 设置方法 |
|---|---|
| IntelliJ IDEA | Run → Edit Configurations → VM options → 添加 -ea |
| Eclipse | Run → Run Configurations → Arguments → VM arguments → 添加 -ea |
| VS Code | settings.json → 添加 "java.debug.settings.enableAssertions": true |
其实还有一个小问题，就算启用了assert功能，运行后也什么都不会输出
这是因为当断言的条件为true时，程序会继续指向，不会抛出AssertionError
断言的语法为：
assert 条件表达式 : 错误消息;
// 其中条件表达式的结果若为true，则断言通过，否则会抛出AssertionError错误
// 错误消息是可选的，它表示断言失败后会输出的消息
// 如：assert 条件表达式;不使用接口实现的最大堆：
package algorithm.datastructure.heapdemo;
public class NoInterfaceHeap {
private int[] heap;
private int size;
private int capacity;
public NoInterfaceHeap(int capacity) {
this.capacity = capacity;
this.heap = new int[capacity];
this.size = 0;
}
// default capacity
public NoInterfaceHeap() {
this(16); // 这是Java的构造方法链，用this构造同一个类的其他构造方法。这里是调用前一个构造方法，传入参数16
// 注意：this()必须是构造方法的第一行，且只能使用一次
}
// insert an element to the bottom of the heap
public void insert(int value) {
if (isFull()) {
resize(); // expand the capacity
}
heap[size] = value;
size++;
floatUp(size - 1); // adjust upwardly
}
public int pop() {
if (isEmpty()) {
throw new RuntimeException("Heap is empty");
}
int max = heap[0]; // record the max value(the top element of max heap)
heap[0] = heap[size - 1]; // exchange the elements at the top and bottom of the heap
size--;
if (size > 0) {
floatDown(0); // adjust downwardly
}
return max; // don't forget to return the top element
}
public int peek() {
if (isEmpty()) {
throw new RuntimeException("Heap is empty");
}
return heap[0];
}
// heapify 堆化
// adjust the element of the specified index "i" upwardly
private void floatUp(int childIndex) {
int child = heap[childIndex];
while (childIndex > 0) {
int parentIndex = (childIndex - 1) / 2; // Java /运算符 本身就是整除（下取整）
if (heap[parentIndex] < child) {
heap[childIndex] = heap[parentIndex];
childIndex = parentIndex; // update childIndex, because we need to check the parent node of higher level
} else {
break;
}
}
heap[childIndex] = child; // put it in the right place
}
// adjust the element of the specified index "i" downwardly
private void floatDown(int parentIndex) {
int value = heap[parentIndex];
while (true) {
int i = parentIndex;
int leftChildIndex = 2 * parentIndex + 1;
int rightChildIndex = 2 * parentIndex + 2;
if (leftChildIndex < size && heap[leftChildIndex] > heap[i]) {
i = leftChildIndex;
}
if (rightChildIndex < size && heap[rightChildIndex] > heap[i]) {
i = rightChildIndex;
}
if (i == parentIndex) {
break; // if 'i' is not changed, explaning that parent at the right place
}
heap[parentIndex] = heap[i];
parentIndex = i; // update parentIndex, because we need to check the child node of lower level
}
heap[parentIndex] = value;
}
private void resize() {
capacity *= 2;
int[] newHeap = new int[capacity];
System.arraycopy(heap, 0, newHeap, 0, size); // scr:源数组(从哪复制) scrPos:源数组开始复制的索引 dest:目标数组(复制到哪) destPos:目标数组开始存储元素的索引 length:要复制的元素的个数
heap = newHeap;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
public int size() {
return size;
}
public void buildHeap(int[] arr) {
this.heap = new int[arr.length];
this.size = arr.length;
this.capacity = arr.length;
System.arraycopy(arr, 0, heap, 0, arr.length);
// 从最后一个非叶子节点开始下沉(然后前面的非叶子节点逐个下沉)
// for (int i = (size - 1) / 2; i >= 0; i--) {
// floatDown(i);
// }
// 上面求最后一个非叶子节点的索引是错误的
// 二叉树的最后一个非叶子节点的索引是：floor((节点个数 / 2) - 1, floor()是向下取整,根节点的索引是0
for (int i = size / 2 - 1; i >= 0; i--) {
floatDown(i);
}
}
public void print() {
System.out.print("[");
for (int i = 0; i < size; i++) {
System.out.print(heap[i]);
if (i < size - 1) {
System.out.print(", ");
}
}
System.out.println("]");
}
}
测试：
package algorithm.datastructure.heapdemo;
public class HeapTest {
public static void main(String[] args) {
//testMinHeap();
testMaxHeap();
System.out.println("自动建堆：");
NoInterfaceHeap heap = new NoInterfaceHeap();
heap.buildHeap(new int[]{100,714,210,99,-7,66,12,8});
heap.print();
}
static void testMinHeap() {
// 最小堆
Heap<Integer> minHeap = new Heap<>(false);
assert minHeap.isEmpty() : "新堆应该为空";
minHeap.push(50);
assert minHeap.isEmpty() : "堆不应该为空";
}
// -ea enable assertions
static void testMaxHeap() {
// 最大堆
NoInterfaceHeap maxHeap = new NoInterfaceHeap();
int[] arr = {30, 70, 10, 40, 50};
for (int e: arr) {
maxHeap.insert(e);
}
maxHeap.print();
maxHeap.insert(8);
maxHeap.print();
maxHeap.insert(60);
maxHeap.print();
}
}
输出：
[70, 50, 10, 30, 40]
[70, 50, 10, 30, 40, 8]
[70, 50, 60, 30, 40, 8, 10]
自动建堆：
[714, 100, 210, 99, -7, 66, 12, 8]这个实现有问题，pop()方法好像不能正确删除元素
堆排序
package algorithm.datastructure.heapdemo;
public class HeapSort {
public void sort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
// 建堆：将数组构建成最大堆
buildMaxHeap(arr, n);
// 堆排序
heapSort(arr, n);
}
private void buildMaxHeap(int[] arr, int n) {
// 从最后一个非叶子节点开始开始下沉，然后前面的非叶子节点继续逐个下沉
for (int i = n / 2 - 1; i >= 0; i--) {
dive(arr, i, n);
}
}
private void dive(int[] arr, int i, int n) {
int parent = arr[i];
int max = i;
int leftChildIndex = 2 * i + 1;
int rightChildIndex = 2 * i + 2;
if (leftChildIndex < n && arr[leftChildIndex] > arr[max]) {
max = leftChildIndex;
}
if (rightChildIndex < n && arr[rightChildIndex] > arr[max]) {
max = rightChildIndex;
}
if (max == i) {
return;
}
arr[i] = arr[max];
arr[max] = parent;
dive(arr, max, n);
}
private void heapSort(int[] arr, int heapSize) {
// 把堆顶的元素（数组中最大的元素）和堆底的元素交换位置，然后将堆的大小减1，再向下调整堆使得堆保持最大堆的性质
while (heapSize > 1) { // 当堆中元素只有1个时，整个数组已经有序
int temp = arr[heapSize - 1];
arr[heapSize - 1] = arr[0];
arr[0] = temp;
heapSize--;
// 向下调整堆
dive(arr, 0, heapSize);
}
}
}
测试（都通过）
package algorithm.datastructure.heapdemo;
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
HeapSort heapsort = new HeapSort();
//heap.sort(new int[] {30, 70, 10, 40, 99, 20, 50, 3, -7});
int[] arr = new int[] {30, 70, 10, 40, 99, 20, 50, 3, -7}; // 简写：int[] arr = {30, 70, 10, 40, 99, 20, 50, 3, -7};
heapsort.sort(arr);
System.out.println(Arrays.toString(arr)); // [-7, 3, 10, 20, 30, 40, 50, 70, 99]
int[] arr1 = {};
heapsort.sort(arr1);
System.out.println(Arrays.toString(arr1)); // []
int[] arr2 = {5, 4, 3, 2, 1};
heapsort.sort(arr2);
System.out.println(Arrays.toString(arr2)); // [1, 2, 3, 4, 5]
}
}
优化：dive方法中，用迭代代替递归，避免特殊情况下出现栈溢出
public class HeapSort {
public void sort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
// 建堆：从最后一个非叶子节点开始下沉
for (int i = n / 2 - 1; i >= 0; i--) {
dive(arr, i, n);
}
// 堆排序：依次将堆顶元素与末尾元素交换
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
dive(arr, 0, i);
}
}
// 迭代版下沉操作
private void dive(int[] arr, int i, int n) {
int parent = arr[i];
while (true) {
int max = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[max]) {
max = left;
}
if (right < n && arr[right] > arr[max]) {
max = right;
}
if (max == i) {
break; // 已找到正确位置
}
arr[i] = arr[max];
arr[max] = parent;
i = max; // 继续向下
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
汇聚全球AI编程工具，助力开发者即刻编程。
更多推荐
3
0- 0
已为社区贡献1条内容
所有评论(0)