AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

数据结构 101：如何在 JavaScript 中构建最小堆和最大堆

2023-03-03 725
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构 101：如何在 JavaScript 中构建最小堆和最大堆

什么是堆？

堆是一种高级的基于树的数据结构， 主要用于排序和实现优先级[队列]它们是具有以下特征的完全二叉树：

  • 除了叶节点（没有子节点的节点称为叶）之外，每个级别都被填充。
  • 每个节点最多有 2 个孩子。
  • 所有节点都尽可能靠左。这意味着每个孩子都在他父母的左边。

网络异常，图片无法展示
|

堆使用完全二叉树来避免数组中出现空洞。完全二叉树是每个结点至多有两个孩子的树，所有层的结点都是满的，除了叶子结点可以为空。堆是基于堆属性构建的，堆属性将父节点键与其子节点键进行比较。

重要的是要注意堆并不总是排序的。它们遵循的关键条件是最大或最小元素放置在根节点（顶部）上，具体取决于它是最大堆还是最小堆。堆数据结构与堆内存不同。

堆的优点和缺点

优点：

  • 垃圾收集在堆内存上运行以释放对象使用的内存。
  • 堆是灵活的，因为可以按任何顺序分配或删除内存。
  • 变量可以全局访问。
  • 它有助于找到最小和最大的数字。

缺点：

  • 与栈相比，堆需要更多的时间来执行。
  • 内存管理在堆内存中更为复杂，因为它是全局使用的。
  • 堆通常需要更多的时间来计算。

堆数据结构的应用

堆对于查找数组中的最小或最大元素非常有效，并且在顺序统计和选择算法中很有用。从堆中获取最小值/最大值的时间复杂度为O(1) ，（恒定时间复杂度）。

优先级队列是基于堆结构设计的。有效地插入 ( ) 和删除 ( ) 优先级队列中的每个元素需要O(log(n))时间。insert()``delete()

堆实现的优先级队列用于流行的算法，例如：

  • 普里姆算法
  • Dijkstra 算法
  • 堆排序算法

堆中的基本操作

以下是您在实现堆数据结构时可能使用的基本操作：

  • heapify： 重新排列堆中的元素以保持堆属性。
  • insert： 将一个项目添加到堆中，同时保持其堆属性。
  • delete： 删除堆中的项目。
  • extract： 返回一个项目的值，然后从堆中删除它。
  • isEmpty:  boolean，如果 boolean 为空则返回 true，如果有节点则返回 false。
  • size: 返回堆的大小。
  • getMax()： 返回堆中的最大值

如何构建最大堆

最大堆中的元素遵循最大堆属性。这意味着父节点的键总是大于两个子节点的键。要构建最大堆：

  • 在堆的开头（根）创建一个新节点。
  • 给它赋值。
  • 将子节点的值与父节点进行比较。
  • 如果父节点的值小于任一子节点（向左或向右）的值，则交换节点。
  • 重复直到最大元素位于根父节点（然后你可以说堆属性成立）。

将新元素插入堆时也可以遵循这些步骤。这里的关键是无论在最大堆上执行什么操作，堆属性都必须保持。

移除/删除最大堆中的根节点：

  • 删除根节点。
  • 将最后一层的最后一个子节点移动到根。
  • 将父节点与其子节点进行比较。
  • 如果父节点的值小于子节点，则交换它们，并重复直到满足堆属性。

让我们看一下这在代码中是什么样子的。在下一节中，我们将使用[JavaScript] 实现最大堆。

在 JavaScript 中实现最大堆

在我们开始构建最大堆之前，先看看我们将要实现的一些方法以及它们的作用：

  • _percolateUp()： 将堆属性从子节点恢复到根节点。
  • _maxHeapify()： 将堆属性从特定节点向下恢复到叶节点。
  • insert()： 将给定值附加到堆数组并根据元素的堆属性重新排列元素。在每次插入时，堆均匀增长，大小增加一。
  • getMax()： 返回堆（根节点）中的最大值，不修改堆。注意这里的时间复杂度是常数时间O(1)
  • removeMax()： 返回并删除堆中的最大值（想想pop()）。该函数的时间复杂度为O(log(n)) 。

如果堆大小大于一，它将最大值存储到一个变量中，将该值与最后一个叶子交换，然后从堆中删除最大值。

如果堆只有一个元素，则删除并返回该元素的值，最后一个条件是如果堆为空，则返回null。

该__percolateUp()方法在每个父节点上递归[调用] ，直到到达根节点。对于要定位在 max-heap 属性之后的每个节点，我们在该数组的每个索引处调用该__maxHeapify()方法，从堆的底部开始。

class maxHeap {
    constructor() {
        this.heap = [];
        this.elements = 0;
    };
    insert(val) {
        if (this.elements >= this.heap.length) {
            this.elements = this.elements + 1;
            this.heap.push(val);
            this.__percolateUp(this.heap.length - 1);
        }
        else {
            this.heap[this.elements] = val;
            this.elements = this.elements + 1;
            this.__percolateUp(this.elements - 1);
        }
    };
    getMax() {
        if (this.elements !== 0)
            return this.heap[0];
        return null;
    };
    removeMax() {
        let max = this.heap[0];
        if (this.elements > 1) {
            this.heap[0] = this.heap[this.elements - 1];
            this.elements = this.elements - 1;
            this.__maxHeapify(0);
            return max
        } else if (this.elements === 1) {
            this.elements = this.elements - 1;
            return max;
        } else {
            return null;
        }
    };
    __percolateUp(index) {
        const parent = Math.floor((index - 1) / 2);
        if (index <= 0)
            return
        else if (this.heap[parent] < this.heap[index]) {
            let tmp = this.heap[parent];
            this.heap[parent] = this.heap[index];
            this.heap[index] = tmp;
            this.__percolateUp(parent);
        }
    };
    __maxHeapify(index) {
        let left = (index * 2) + 1;
        let right = (index * 2) + 2;
        let largest = index;
        if ((this.elements > left) && (this.heap[largest] < this.heap[left])) {
            largest = left
        }
        else if ((this.elements > right) && (this.heap[largest] < this.heap[right]))
            largest = right
        else if (largest !== index) {
            const tmp = this.heap[largest];
            this.heap[largest] = this.heap[index];
            this.heap[index] = tmp;
            this.__maxHeapify(largest);
        }
    };
    buildHeap(arr) {
        this.heap = arr;
        this.elements = this.heap.length;
        for (let i = this.heap.length - 1; i >= 0; i--) {
            this.__maxHeapify(i);
        }
    };
};
let heap = new maxHeap();
复制代码

如何构建最小堆

直观上，我们可以说最小堆中的元素遵循最小堆属性，因为这与最大堆相反。父节点的键总是小于两个子节点的键。要构建最小堆：

  • 在堆的末尾（最后一层）创建一个新的子节点。
  • 将新键添加到该节点（将其附加到数组）。
  • 向上移动子节点，直到到达根节点并且堆属性得到满足。

删除/删除最小堆中的根节点：

  • 删除根节点。
  • 将最后一个孩子的钥匙移到根。
  • 将父节点与其子节点进行比较。
  • 如果父节点的值大于子节点，则交换它们，并重复直到满足堆属性。

在 JavaScript 中实现最小堆

在我们开始构建最小堆之前，请注意它的实现类似于最大堆。minHeapify()恢复堆属性。getMin()返回堆（根节点）中的最小值而不修改堆。并removeMin()删除最小值并返回它。

class minHeap {
    constructor() {
        this.heap = []
        this.elements = 0;
    };
    insert(val) {
        if (this.elements >== this.heap.length) {
            this.elements = this.elements + 1
            this.heap.push(val);
            this.__percolateUp(this.heap.length - 1);
        }
        else {
            this.heap[this.elements] = val;
            this.elements = this.elements + 1;
            this.__percolateUp(this.elements - 1);
        }
    };
    getMin() {
        if (this.heap.length !== 0)
            return this.heap[0];
        return null;
    }
    removeMin() {
        const min = this.heap[0];
        if (this.elements > 1) {            
            this.heap[0] = this.heap[this.elements - 1];
            this.elements = this.elements - 1;
            this.__minHeapify(0);
            return min;
        } else if (this.elements == 1) {
            this.elements = this.elements - 1;
            return min;
        } else {
            return null;
        }
    };
    __percolateUp(index) {
        let parent = Math.floor((index - 1) / 2);
        if (index <= 0)
            return
        else if (this.heap[parent] > this.heap[index]) {
            let tmp = this.heap[parent];
            this.heap[parent] = this.heap[index];
            this.heap[index] = tmp;
            this.__percolateUp(parent);
        }
    };
    __minHeapify(index) {
        let left = (index * 2) + 1;
        let right = (index * 2) + 2;
        let smallest = index;
        if ((this.elements > left) && (this.heap[smallest] > this.heap[left])) {
            smallest = left;
        }
        if ((this.elements > right) && (this.heap[smallest] > this.heap[right]))
            smallest = right;
        if (smallest !== index) {
            let tmp = this.heap[smallest];
            this.heap[smallest] = this.heap[index];
            this.heap[index] = tmp;
            this.__minHeapify(smallest);
        }
    }
    buildHeap(arr) {
        this.heap = arr;
        this.elements = this.heap.length;
        for (let i = this.heap.length - 1; i >= 0; i--) {
            this.__minHeapify(i)
        }
    }
};
let heap = new minHeap();
heap.insert(12);
heap.insert(10);
heap.insert(-10);
heap.insert(100);
console.log(heap.getMin()); //you should get -10
let newheap = new minHeap();
let arr = [12, 6, 8, 3, 16, 4, 27];
newheap.buildHeap(arr) //builds this new heap with elements from the array
console.log(newheap.getMin()) //this logs 3
newheap.removeMin();
console.log(newheap.getMin())
复制代码

堆挑战：将最大堆转换为最小堆

让我们通过动手挑战来进一步学习。我们的目标是将最大堆转换为最小堆。跟随我们的代码解决方案，看看它是如何完成的。

问题陈述： 实现一个函数convertMax(maxHeap)，将二进制最大堆转换为二进制最小堆，其中maxHeap是格式中的数组maxHeap（即父项大于其子项）。您的输出应该是一个转换后的数组。

示例输入：

maxHeap = [9,4,7,1,-2,6,5]
复制代码

示例输出：

result = [-2,1,5,9,4,6,7]
复制代码

网络异常，图片无法展示
|

问题：

function convertMax(maxHeap) {
    return maxHeap
}
复制代码

解决方案：

function minHeapify(heap, index) {
    var left = index * 2;
    var right = (index * 2) + 1;
    var smallest = index;
    if ((heap.length > left) && (heap[smallest] > heap[left])) {
        smallest = left
    }
    if ((heap.length > right) && (heap[smallest] > heap[right]))
        smallest = right
    if (smallest != index) {
        var tmp = heap[smallest]
        heap[smallest] = heap[index]
        heap[index] = tmp
        minHeapify(heap, smallest)
    }
    return heap;
}
function convertMax(maxHeap) {
    for (var i = Math.floor((maxHeap.length) / 2); i > -1; i--)
        maxHeap = minHeapify(maxHeap, i)
    return maxHeap
}
复制代码

****可以运行上面的代码解决方案。 我们可以将 given 视为maxHeap一个规则的元素数组并对其重新排序，以便它准确地表示一个最小堆。该函数通过在每个节点上convertMax()调用函数从最低父节点恢复所有节点上的堆属性。minHeapify()

构建堆的时间复杂度是O(n) 。这个问题也是如此。

function minHeapify(heap, index) {
    var left = index * 2;
    var right = (index * 2) + 1;
    var smallest = index;
    if ((heap.length > left) && (heap[smallest] > heap[left])) {
        smallest = left
    }
    if ((heap.length > right) && (heap[smallest] > heap[right]))
        smallest = right
    if (smallest != index) {
        var tmp = heap[smallest]
        heap[smallest] = heap[index]
        heap[index] = tmp
        minHeapify(heap, smallest)
    }
    return heap;
}
function convertMax(maxHeap) {
    for (var i = Math.floor((maxHeap.length) / 2); i > -1; i--)
        maxHeap = minHeapify(maxHeap, i)
    return maxHeap
}
var maxHeap = [9,4,7,1,-2,6,5]
console.log(convertMax(maxHeap))
-->
[ -2, 1, 4, 5, 7, 6, 9 ]


文章标签：
JavaScript
前端开发
索引
算法
存储
关键词：
JavaScript构建
数据结构堆
数据结构构建
JavaScript堆
数据结构javascript
饱饱巴士
目录
相关文章
想飞的雪糕
|
30天前
|
前端开发 机器人 API
前端大模型入门（一）：用 js+langchain 构建基于 LLM 的应用
本文介绍了大语言模型（LLM）的HTTP API流式调用机制及其在前端的实现方法。通过流式调用，服务器可以逐步发送生成的文本内容，前端则实时处理并展示这些数据块，从而提升用户体验和实时性。文章详细讲解了如何使用`fetch`发起流式请求、处理响应流数据、逐步更新界面、处理中断和错误，以及优化用户交互。流式调用特别适用于聊天机器人、搜索建议等应用场景，能够显著减少用户的等待时间，增强交互性。
想飞的雪糕
232 2
进步`于辰
|
11天前
|
存储 算法 Java
散列表的数据结构以及对象在JVM堆中的存储过程
本文介绍了散列表的基本概念及其在JVM中的应用，详细讲解了散列表的结构、对象存储过程、Hashtable的扩容机制及与HashMap的区别。通过实例和图解，帮助读者理解散列表的工作原理和优化策略。
进步`于辰
25 1
散列表的数据结构以及对象在JVM堆中的存储过程
Star时光
|
30天前
|
存储 JavaScript 前端开发
使用JavaScript构建动态交互式网页：从基础到实践
【10月更文挑战第12天】使用JavaScript构建动态交互式网页：从基础到实践
Star时光
69 1
ephemerals__
|
13天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
56 16
游客sjjs6jgz4gp7m1
|
14天前
|
JavaScript 中间件 关系型数据库
构建高效的后端服务：Node.js 与 Express 的实践指南
在后端开发领域，Node.js 与 Express 的组合因其轻量级和高效性而广受欢迎。本文将深入探讨如何利用这一组合构建高性能的后端服务。我们将从 Node.js 的事件驱动和非阻塞 I/O 模型出发，解释其如何优化网络请求处理。接着，通过 Express 框架的简洁 API，展示如何快速搭建 RESTful API。文章还将涉及中间件的使用，以及如何结合 MySQL 数据库进行数据操作。最后，我们将讨论性能优化技巧，包括异步编程模式和缓存策略，以确保服务的稳定性和扩展性。
游客sjjs6jgz4gp7m1
44 17
我不是游客20240119
|
3天前
|
JSON JavaScript API
深入浅出Node.js：从零开始构建RESTful API
【10月更文挑战第39天】 在数字化时代的浪潮中，API（应用程序编程接口）已成为连接不同软件应用的桥梁。本文将带领读者从零基础出发，逐步深入Node.js的世界，最终实现一个功能完备的RESTful API。通过实践，我们将探索如何利用Node.js的异步特性和强大的生态系统来构建高效、可扩展的服务。准备好迎接代码和概念的碰撞，一起解锁后端开发的新篇章。
我不是游客20240119
10 1
技术混子
|
17天前
|
资源调度 前端开发 数据可视化
构建高效的数据可视化仪表板：D3.js与React的融合之道
【10月更文挑战第25天】在数据驱动的时代，将复杂的数据集转换为直观、互动式的可视化表示已成为一项至关重要的技能。本文深入探讨了如何结合D3.js的强大可视化功能和React框架的响应式特性来构建高效、动态的数据可视化仪表板。文章首先介绍了D3.js和React的基础知识，然后通过一个实际的项目案例，详细阐述了如何将两者结合使用，并提供了实用的代码示例。无论你是数据科学家、前端开发者还是可视化爱好者，这篇文章都将为你提供宝贵的洞见和实用技能。
技术混子
39 5
龙大吉
|
20天前
|
JavaScript 前端开发 持续交付
构建现代Web应用：Vue.js与Node.js的完美结合
【10月更文挑战第22天】随着互联网技术的快速发展，Web应用已经成为了人们日常生活和工作的重要组成部分。前端技术和后端技术的不断创新，为Web应用的构建提供了更多可能。在本篇文章中，我们将探讨Vue.js和Node.js这两大热门技术如何完美结合，构建现代Web应用。
龙大吉
19 4
mrq4nk6ni2neg
|
21天前
|
Web App开发 JavaScript 中间件
构建高效后端服务：Node.js与Express框架的完美结合
【10月更文挑战第21天】本文将引导你走进Node.js和Express框架的世界，探索它们如何共同打造一个高效、可扩展的后端服务。通过深入浅出的解释和实际代码示例，我们将一起理解这一组合的魅力所在，并学习如何利用它们来构建现代Web应用。
mrq4nk6ni2neg
41 1
历年考试不作弊
|
7天前
|
JavaScript 前端开发 NoSQL
深入浅出：使用Node.js构建RESTful API
【10月更文挑战第35天】在数字时代的浪潮中，后端技术如同海洋中稳固的灯塔，为前端应用提供数据和逻辑支撑。本文旨在通过浅显易懂的方式，带领读者了解如何利用Node.js这一强大的后端平台，搭建一个高效、可靠的RESTful API。我们将从基础概念入手，逐步深入到代码实践，最终实现一个简单的API示例。这不仅是对技术的探索，也是对知识传递方式的一次创新尝试。让我们一起启航，探索Node.js的奥秘，解锁后端开发的无限可能。
历年考试不作弊
6 0