堆的添加和弹出
我们以最小堆为例子，讲解如何添加、弹出堆中的元素
添加优先队列先进先出，所以从队尾添加：
添加到队尾
检查是否小于父节点，是则上浮直到大于等于父节点
123456789101112131415161718192021222324function minHeapAdd(array = [], element) { array.push(element); if (array.length > 1) { // 插入元素的索引 let index = array.length - 1; // 父元素索引 let parent = Math.floor((index - 1) / 2); // 直到没有父元素 while (parent >= 0) { // 如果当前元素小于父元素 if (array[index] < array[parent]) { // 交换元素位置 [array[index], array[parent]] = [ar ...
构建堆
最大堆从最后一个非叶子节点开始：
和孩子节点的最大值比较
大于 - 不需要继续下沉
小于 - 和最大值交换位置，继续和下一层孩子重复 1,2,3
12345678910111213141516171819202122232425function adjustMaxHeap(array, index, length) { // 每次循环都从从当前节点的左孩子开始 for (let i = 2 * index + 1; i < length; i = 2 * i + 1) { // 如果右孩子存在且大于左孩子，指针指向右孩子 if (i + 1 < length && array[i + 1] > array[i]) { i++; } // 如果当前节点大于等于最大的孩子节点，无需替换 if (array[index] >= [array[i]]) { break; } else { // 否则交换两节 ...
堆
简述
堆属于优先队列，先进先出
堆是一颗完全二叉树
任意节点值是其子树所有节点的最大值或最小值
完全二叉树定义：一棵深度为 k 的有 n 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为 i $(0≤i<n)$ 的结点与满二叉树中编号为 i 的结点在二叉树中的位置相同，那么它就是完全二叉树
简单来说：减去最后一层是满二叉树、并且最后一层中第一个节点和最后一个节点之间没有空节点的树，就是完全二叉树
公式索引从 0 开始计算
节点数为 n，最后一个非叶子节点索引号：$floor(\frac{n}{2}-1)$
节点索引号为 i 的孩子节点索引号：$2i+1$, $2i+2$
除根节点外，节点索引号为 i 的父节点索引号为 $floor(\frac{i-1}{2})$
节点数为 n，树高度 k 为 $\log_{2}{n}$
最大堆又称大顶堆
任意一个子树的最大值都在该树的根节点
从堆顶到底部的节点从大到小
最小堆又称小顶堆
任意一个子树的最小值都在该树的根节点
从堆顶到底部的节点从小到大
链表
每个元素存储着值和下一个元素的地址，一组这样的元素连接起来就是链表
链表特点：
查询慢，查询某个元素需要遍历
插入快，元素只需要在插入处断开重连即可
二叉树遍历
前序遍历
遍历顺序：根左右（DFS 深度优先遍历）
先访问根节点，然后遍历左子树，最后遍历右子树
结果：ABDECF
递归实现12345678var preorderTraversal = function (root, array = []) { if (root) { array.push(root.val); preorderTraversal(root.left, array); preorderTraversal(root.right, array); } return array;};
非递归实现从根节点开始遍历：
访问节点值
左孩子入栈，直到节点左孩子为空
节点出栈，以节点的右孩子为目标重复 1,2,3
123456789101112131415161718var preorderTraversal = function (root) { const result = []; const stack = []; let current = root; while (curre ...
数据结构
本目录下的文章大多参考了：awesome-coding-js
数据结构即数据元素相互之间存在的一种和多种特定的关系集合
一般我们从两个维度来理解
逻辑结构就是数据之间的关系
线性结构一个有序元素的集合，元素之间的关系是一对一；除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的
常见的：**栈、队列、链表、线性表**
非线性结构各个元素不再保持在一个线性队列中，每个元素可能与零个或多个其它数据元素关联
常见的：**二维数组、树**
存储结构存储结构是逻辑结构用计算机语言的实现
常见的：**顺序存储、链式存储、索引存储、散列存储**
顺序存储
在内存中的位置是连续的，数组就是
链式存储
链表就是典型的链式存储，在逻辑上是连续的，但在内存中不一定是连续的
散列存储
数据在顺序和逻辑上都不存在关系，但是可以通过哈希表的方法访问数据， Map 就是
二叉树
简述二叉树是一种典型的树树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作左子树和右子树
根的直接子节点数称为该树的度，二叉树的度数为 0 ~ 2
度数为 0 的节点，称作叶节点
二叉树公式层数、索引号从 0 开始计算
第 n 层的节点数最多为 $2^{n}$ 个节点
n 层二叉树最多有 $2^{n+1}-1$ 个节点
设二叉树叶节点数 n0，度为 2 的节点数 n2，则 $n_0=n_2+1$
浏览器加载、渲染
本文参考了：浏览器渲染过程与性能优化
根据链接发送 http 请求 HTML 并解析，大致步骤如下：
处理 HTML 标记数据并生成 DOM 树
处理 CSS 标记数据并生成 CSSOM 树
将 DOM 树与 CSSOM 树合并在一起生成渲染树
遍历渲染树开始布局，计算每个节点的位置信息
将每个节点绘制到屏幕
生成 DOM 树
编码：将 HTML 字节数据根据响应头数据转换为其指定编码的字符
令牌化：浏览器会根据 HTML 规范来将字符串转换成各种令牌（如 <html>,<body> 这样的标签以及标签中的字符串和属性等都会被转化为令牌，每个令牌具有特殊含义和一组规则）
令牌记录了标签的开始与结束，通过这个特性可以轻松判断一个标签是否为子标签（假设有 <html> 与 <body> 两个标签，当 <html> 标签的令牌还未遇到它的结束令牌 </html> 就遇见了 <body> 标签令牌，那么 <body> 就是 <html> 的子标签）
生成对象：接下来 ...
事件循环
浏览器中拥有很多线程，我们的 js 代码在主线程中执行，是单线程的
普通的代码都是同步代码，一行接着一行执行，需要抛给其它线程执行的代码为异步代码，所以需要一个机制来让其能处理异步代码，那就是 Event Loop(事件循环)
下面是 js 执行大致架构：
有一个调用栈来放置需要执行的代码，先进先出
执行我们代码的时候，会把每一行代码推进调用栈
接着从栈顶开始调用其执行执行上下文，从堆空间(一般是存储对象)和栈空间(一般存储非对象值以及对象引用)取数据，进而处理当前调用栈所用到的数据
遇到异步代码时，会根据异步任务类型分发给浏览器其它线程
异步任务结束时会把回调推入一个异步任务队列，主线程执行完后，会在这个队列里获取任务压入调用栈执行
异步任务分为两种，宏任务和微任务
其执行逻辑大致如下：
代码中的同步代码为一个宏任务，推入宏任务队列
取出一个宏任务执行
执行结束后判断是否有微任务
有就执行所有微任务
执行完微任务或没有微任务，浏览器更新渲染
是否有宏任务，有就回到第二步
没有就回到第三步
宏任务setTimeout,setInterval,事件回调 ...
this 的指向
本文参考了：2.6 万字 JS 干货分享，带你领略前端魅力！- 第七节
我们先看一张图，看完基本能懂：
同时要注意几点：
浏览器环境下，最外层的 this 指向 window
node 环境下，最外层的 this 指向 global
严格模式下最外层 this 指向 undefined
箭头函数
this 指向函数外最近的 this
12// 在浏览器中直接执行，this 指向外部最近的 this 也就是 window(() => console.log(this))(); // ▶ Window { ... }
无法通过 call,apply,bind 改变 this 指向
12345const fn = () => console.log(this);// 打印的依旧是 windowfn.call('str'); // ▶ Window { ... }fn.apply('str'); // ▶ Window { ... }fn.bind('st ...
