堆、栈、最小堆

堆是什么

结构属性

堆是一棵完全二叉树，即除最后一层外，其他层节点均填满，且最后一层节点从左到右连续分布。

排序属性：

根据类型不同，堆分为：
最大堆（Max-Heap） ：每个节点的值大于或等于其子节点的值，根节点是堆中的最大值。
最小堆（Min-Heap） ：每个节点的值小于或等于其子节点的值，根节点是堆中的最小值。

最小堆

特点

最小堆是堆的一种具体形式，其特点包括：

节点关系：任意父节点的值均小于或等于其左右子节点的值。根节点始终为堆中的最小元素。

存储方式：通常用数组实现，数组索引对应完全二叉树的层序遍历结果。例如，索引为i的节点，其父节点索引为(i-1)/2，左子节点为2i+1，右子节点为2i+2。

核心操作

插入元素：将新元素添加到数组末尾，再通过 上浮（Sift Up） 调整，即与父节点比较并交换，直至满足堆性质。时间复杂度为O(log n)。

删除根节点：移除根节点（即数组首元素）后，将末尾元素移至根位置，再通过 下沉（Sift Down） 调整，即与较小的子节点交换，直至满足堆性质。时间复杂度为O(log n)。

构建堆：从最后一个非叶子节点开始，依次向前调整每个子树为堆结构。时间复杂度为O(n)。

实现一个最小堆

class MinHeap {// 构造函数，初始化一个空数组来存储堆元素constructor() {this.heap = [];}// 获取父节点的索引getParentIndex(index) {return Math.floor((index - 1) / 2);}// 获取左子节点的索引getLeftChildIndex(index) {return index * 2 + 1;}// 获取右子节点的索引getRightChildIndex(index) {return index * 2 + 2;}// 向上调整堆，保持堆的性质up(index) {if (index === 0) return;  // 如果已经是根节点，就不再调整const parentIndex = this.getParentIndex(index);  // 获取父节点的索引// 如果当前节点小于父节点，交换两者if (this.heap[parentIndex] > this.heap[index]) {[this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];this.up(parentIndex);  // 递归向上调整}}// 向下调整堆，保持堆的性质down(index) {const leftIndex = this.getLeftChildIndex(index);  // 左子节点的索引const rightIndex = this.getRightChildIndex(index);  // 右子节点的索引let smallest = index;  // 假设当前节点最小// 如果左子节点存在且小于当前节点，更新最小值索引if (leftIndex < this.heap.length && this.heap[leftIndex] < this.heap[smallest]) {smallest = leftIndex;}// 如果右子节点存在且小于当前节点（或左子节点），更新最小值索引if (rightIndex < this.heap.length && this.heap[rightIndex] < this.heap[smallest]) {smallest = rightIndex;}// 如果最小值不是当前节点，交换并继续向下调整if (smallest !== index) {[this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];this.down(smallest);  // 递归向下调整}}// 查看堆顶元素（即最小值）peek() {return this.heap[0];}// 获取堆的大小（即堆中元素的个数）size() {return this.heap.length;}// 向堆中插入一个新元素insert(value) {this.heap.push(value);  // 将新元素添加到堆的末尾this.up(this.heap.length - 1);  // 调用向上调整方法保持堆的性质}// 移除堆顶元素（即最小值），并调整堆pop() {this.heap[0] = this.heap.pop();  // 将堆顶元素与堆末尾元素交换并移除堆顶this.down(0);  // 调用向下调整方法保持堆的性质}}// 使用示例
let arr = new MinHeap();arr.insert(5);  // 插入元素 5
arr.insert(4);  // 插入元素 4
arr.insert(6);  // 插入元素 6
arr.insert(1);  // 插入元素 1// arr.pop();  // 移除堆顶元素（最小值）console.log(arr);  // 输出当前堆的内容
console.log(arr.size());  // 输出堆的大小
console.log(arr.peek());  // 输出堆顶元素（最小值）

堆和栈的区别

1. 数据结构中的堆 vs 栈

特性	堆（Heap）	栈（Stack）
数据结构类型	完全二叉树（最大堆/最小堆）	线性结构（LIFO：后进先出）
核心操作	插入、删除极值元素（如最小堆的根节点）	压栈（push）、弹栈（pop）
时间复杂度	插入和删除为 O(log n)	插入和删除为 O(1)
典型应用	优先队列、堆排序、Top K 问题	函数调用栈、表达式求值、括号匹配
示例	任务调度中快速获取优先级最高的任务	递归调用时保存局部变量和返回地址

---

2. 内存管理中的堆 vs 栈

特性	堆（Heap）	栈（Stack）
内存分配方式	动态分配（程序员手动管理，如 malloc）	自动分配（编译器管理，如局部变量）
内存大小	较大，可动态扩展	较小，固定大小（可能溢出）
生命周期	由程序员控制（需手动释放，否则内存泄漏）	随函数调用自动创建和销毁
访问速度	较慢（需通过指针间接访问）	极快（直接操作栈顶指针）
碎片问题	可能存在内存碎片	无碎片
典型应用	存储动态数据（如对象、数组）	存储函数参数、局部变量

---

关键区别总结

1. 名称混淆：

   • 数据结构中的“堆”是树形结构，而内存中的“堆”是动态内存区域，两者无直接关联。
   • 数据结构中的“栈”是 LIFO 的线性结构，内存中的“栈”是函数调用的内存空间。

2. 核心差异：

   • 数据结构：堆用于高效管理极值元素，栈用于顺序操作（如撤销功能）。
   • 内存管理：堆是灵活但需手动管理的动态内存，栈是高效但受限的自动内存。

3. 易错点：

   • 在 C/C++ 中，局部变量存储在栈上，函数返回后自动释放；堆内存需手动释放（free/delete）。
   • 栈溢出（Stack Overflow）是程序错误，堆内存泄漏（Memory Leak）是资源管理问题。

---

示例代码对比

// 内存中的栈 vs 堆
void example() {int a = 10;          // 栈内存（自动分配）int *b = (int*)malloc(sizeof(int));  // 堆内存（手动分配）*b = 20;free(b);             // 必须手动释放堆内存
}

---

应用场景

• 用栈的场景：
  • 函数调用（保存上下文）。
  • 实现撤销操作（如编辑器中的 Ctrl+Z）。
• 用堆的场景：
  • 动态创建对象（如 Java/C++ 的 new）。
  • 需要长期存在的数据（如全局缓存）。