数据结构之---栈，队列，堆（堆排序）

栈 (Stack)：后进先出 (LIFO)

栈就像是一个盛放羽毛球的筒，你最后放进去的球，一定是第一个被拿出来的。

• 特点：操作受限，只允许在“栈顶”进行插入（push）和删除（pop）

应用场景

• 函数调用栈：JS 引擎追踪函数嵌套执行的逻辑。
• 括号匹配：LeetCode 经典题目，利用栈平衡左右括号。
• 浏览器的前进后退：两个栈配合实现页面跳转

队列 (Queue)：先进先出 (FIFO)

队列就像排队买奶茶，先排队的人先拿到奶茶离开。

• 特点：一头进（enqueue），另一头出（dequeue）。

应用场景

• 事件循环 (Event Loop)：宏任务队列（setTimeout）和微任务队列（Promise）。
• 广度优先搜索 (BFS)：在遍历树或图时，利用队列按层级访问节点。
• 打印机任务管理：按提交顺序处理打印文档。

堆是一种 完全二叉树

在数据结构中，堆是一种特殊的完全二叉树。虽然它是树状结构，但在内存里，我们通常用数组来存储它，因为这样最节省空间且访问效率最高。

堆的两个核心特征：

1. 结构性：必须是完全二叉树（除了最后一层，其他层全满，且最后一层靠左排列）。
2. 有序性：

       大顶堆 (Max Heap)：任意节点的值都 >=其子节点的值。堆顶（根节点）永远是最大值。

       小顶堆 (Min Heap)：任意节点的值都 <= 其子节点的值。堆顶永远是最小值

数组与树的映射关系

假设一个节点在数组中的索引为 i，那么：

• 它的左子节点索引为：2i + 1
• 它的右子节点索引为：2i + 2
• 它的父节点索引为：(i - 1) / 2（向下取整）

应用场景

• 大规模数据存储：所有复杂对象。
• 优先队列/堆排序：虽然叫“堆”，但在算法层面，我们常用数组模拟二叉堆（大顶堆/小顶堆）来解决 Top K 问题。

什么是堆排序？

堆排序是一种利用堆这种数据结构设计的排序算法。它的核心思想是：

1. 将无序数组构建成一个大顶堆。
2. 此时，堆顶（数组第一个元素）就是最大值。
3. 将堆顶与末尾元素交换，然后将剩余的 n-1 个元素重新调整为大顶堆。
4. 重复此过程，直到整个数组有序。

如何进行堆排序？

第一步：堆化 (Heapify) —— 维护堆的性质

这是最核心的函数。当某个节点破坏了堆的性质时，我们要让它“下沉”到合适的位置。

function heapify(arr, n, i) {
    let largest = i; 
    let left = 2 * i + 1;
    let right = 2 * i + 2;

    // 如果左子节点比父节点大
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 如果右子节点比当前最大的还大
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大值不是父节点，则交换并递归调整
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        // 递归调整受影响的子树
        heapify(arr, n, largest);
    }
}

第二步：整体排序流程

1. 建堆：从最后一个非叶子节点开始，自下而上进行 heapify。
2. 提取：不断把堆顶（最大值）移到数组末尾，缩小堆的范围并重新调整。

function heapSort(arr) {
    const n = arr.length;

    // 1. 构建大顶堆 (从最后一个非叶子节点开始)
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 2. 逐个提取元素
    for (let i = n - 1; i > 0; i--) {
        // 将当前堆顶（最大值）移至末尾
        [arr[0], arr[i]] = [arr[i], arr[0]];
        // 针对剩下的堆空间，重新进行大顶堆化
        heapify(arr, i, 0);
    }
    return arr;
}

为什么是 O(n log n)？

1. 循环次数：我们需要进行 n-1 次“提取冠军”的操作，这是 O(n)。
2. 调整代价：每次提取后，都需要进行一次 heapify。因为堆是一棵树，heapify 的下沉路径最长就是树的高度，即 log n。
3. 相乘：n 次操作 times log n 的复杂度，结果就是 O(n log n)

堆、栈的双重身份

既是内存管理的物理区域（底层分配），又是逻辑上的数据结构（算法逻辑）。把它们放在一起说，是因为在 JavaScript 的执行环境中，这两者是互为表里、深度耦合的

JS 的内置数据类型有哪些？

根据 ECMAScript 标准，JS 只有以下 8 种内置类型：

• 基本类型 (Primitives): Number, String, Boolean, Undefined, Null, Symbol, BigInt。
• 引用类型 (Reference Type): Object (包括子类型如 Array, Function, Date, RegExp 等)

而堆、栈、队列是数据结构（逻辑概念）或内存区域（底层实现）

栈 (Stack) & 队列 (Queue)

它们是开发者手动实现或引擎内部使用的逻辑。

• 在代码层面，我们通常用内置的 Array 类型来“扮演”栈或队列的角色。
• Array.push/pop 模拟了栈的行为；Array.push/shift 模拟了队列的行为