免费建立网站论坛,ppt做视频模板下载网站,网络推广培训视频,网站建设服务哪家堆是什么
结构属性
堆是一棵完全二叉树#xff0c;即除最后一层外#xff0c;其他层节点均填满#xff0c;且最后一层节点从左到右连续分布。
排序属性#xff1a;
根据类型不同#xff0c;堆分为#xff1a; 最大堆#xff08;Max-Heap#xff09; #xff1a;每…堆是什么
结构属性
堆是一棵完全二叉树即除最后一层外其他层节点均填满且最后一层节点从左到右连续分布。
排序属性
根据类型不同堆分为 最大堆Max-Heap 每个节点的值大于或等于其子节点的值根节点是堆中的最大值。 最小堆Min-Heap 每个节点的值小于或等于其子节点的值根节点是堆中的最小值。
最小堆
特点
最小堆是堆的一种具体形式其特点包括
节点关系任意父节点的值均小于或等于其左右子节点的值。根节点始终为堆中的最小元素。
存储方式通常用数组实现数组索引对应完全二叉树的层序遍历结果。例如索引为i的节点其父节点索引为(i-1)/2左子节点为2i1右子节点为2i2。
核心操作
插入元素将新元素添加到数组末尾再通过 上浮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自动分配编译器管理如局部变量内存大小较大可动态扩展较小固定大小可能溢出生命周期由程序员控制需手动释放否则内存泄漏随函数调用自动创建和销毁访问速度较慢需通过指针间接访问极快直接操作栈顶指针碎片问题可能存在内存碎片无碎片典型应用存储动态数据如对象、数组存储函数参数、局部变量 关键区别总结 名称混淆 数据结构中的“堆”是树形结构而内存中的“堆”是动态内存区域两者无直接关联。数据结构中的“栈”是 LIFO 的线性结构内存中的“栈”是函数调用的内存空间。 核心差异 数据结构堆用于高效管理极值元素栈用于顺序操作如撤销功能。内存管理堆是灵活但需手动管理的动态内存栈是高效但受限的自动内存。 易错点 在 C/C 中局部变量存储在栈上函数返回后自动释放堆内存需手动释放free/delete。栈溢出Stack Overflow是程序错误堆内存泄漏Memory Leak是资源管理问题。 示例代码对比
// 内存中的栈 vs 堆
void example() {int a 10; // 栈内存自动分配int *b (int*)malloc(sizeof(int)); // 堆内存手动分配*b 20;free(b); // 必须手动释放堆内存
}应用场景
用栈的场景 函数调用保存上下文。实现撤销操作如编辑器中的 CtrlZ。 用堆的场景 动态创建对象如 Java/C 的 new。需要长期存在的数据如全局缓存。
