堆(Heap)数据结构详解

什么是堆?

堆是一种特殊的完全二叉树,在前端开发中经常用于实现优先队列、任务调度等场景。它主要有两种类型:

• 大顶堆(Max Heap): 父节点值始终 ≥ 子节点值
• 小顶堆(Min Heap): 父节点值始终 ≤ 子节点值

堆的应用场景

1. 前端任务优先级队列
2. 事件调度系统
3. 前端性能监控中的TopN统计
4. 网络请求的并发控制

堆的核心操作

1. 元素入堆(push)

/* 元素入堆 */
push(val) {
    this.#maxHeap.push(val);         // 1. 将元素添加到堆底
    this.#siftUp(this.size() - 1);   // 2. 执行"上浮"操作维护堆的特性
}

2. 元素出堆(pop)

/* 元素出堆 */
pop() {
    if (this.isEmpty()) throw new Error('堆为空');
    this.#swap(0, this.size() - 1);  // 1. 交换堆顶和堆底元素
    const val = this.#maxHeap.pop();  // 2. 删除堆底元素(原堆顶)
    this.#siftDown(0);               // 3. 执行"下沉"操作维护堆的特性
    return val;
}

3. 堆的构建

/* 构建堆 */
constructor(nums) {
    // 方法一: 自底向上构建
    this.#maxHeap = nums === undefined ? [] : [...nums];
    // 从最后一个非叶节点开始,依次执行下沉操作
    for (let i = this.#parent(this.size() - 1); i >= 0; i--) {
        this.#siftDown(i);
    }
}

实际应用示例

1. 实现一个简单的任务调度器

class TaskScheduler {
    constructor() {
        this.taskHeap = new MaxHeap(); // 使用大顶堆实现优先级队列
    }
    
    addTask(priority, task) {
        this.taskHeap.push({priority, task});
    }
    
    executeNextTask() {
        if(this.taskHeap.isEmpty()) return null;
        const {priority, task} = this.taskHeap.pop();
        task();
    }
}

// 使用示例
const scheduler = new TaskScheduler();
scheduler.addTask(1, () => console.log("低优先级任务"));
scheduler.addTask(3, () => console.log("高优先级任务"));

2. 实现并发请求控制

class RequestController {
    constructor(maxConcurrent) {
        this.requestQueue = new MinHeap(); // 使用小顶堆管理请求
        this.maxConcurrent = maxConcurrent;
        this.currentRequests = 0;
    }
    
    async request(url, priority) {
        // 实现细节省略...
    }
}

性能分析

• 时间复杂度:
  • 插入: O(log n)
  • 删除: O(log n)
  • 获取堆顶: O(1)
  • 建堆: O(n)

注意事项

1. JavaScript中没有原生的堆实现,需要自己实现
2. 在处理大量数据时要注意内存消耗
3. 合理使用堆可以优化很多算法的性能

扩展阅读

• MDN - 数据结构