进阶4-5 小时·算法可视化

图算法路径查找器

实现 BFS、DFS、Dijkstra、A* 等图算法的交互式可视化，支持自定义地图

algorithmsgraphpathfindingdijkstraa-star

图算法路径查找器实战案例

场景描述

通过构建一个交互式网页应用，让用户能在自定义地图上直观地观察和比较BFS、DFS、Dijkstra和A*这四种路径查找算法的工作原理、效率差异以及适用场景。

你将学到

  1. 掌握BFS、DFS、Dijkstra、A*四种核心图算法的原理与JavaScript实现
  2. 使用HTML5 Canvas进行2D网格地图的绘制与交互开发
  3. 设计算法的可视化动画与状态同步机制
  4. 理解并比较不同算法在路径查找问题上的时空复杂度特性
  5. 构建模块化、可扩展的前端应用程序架构

前置知识

在开始本案例前，请确保你已掌握以下知识：

  • JavaScript ES6+语法基础
  • HTML5 Canvas基础操作
  • 基本的数据结构知识（栈、队列、堆）
  • 事件处理与DOM操作基础

相关课程章节：

架构设计

本项目采用分层架构设计，各组件职责清晰：

+-------------------+   +---------------------+   +-------------------+
|    用户界面       | --> |    算法调度器       | --> |    画布渲染器     |
| (HTML/CSS/Controls)|   | (PathfindingWorker)|   |(CanvasRenderer) |
+-------------------+   +---------------------+   +-------------------+
        |                          |                         |
        v                          v                         v
+-------------------+   +---------------------+   +-------------------+
|    事件处理器     | <--> |    网格地图管理器   | <--> |    可视化状态     |
|  (EventHandler)  |    |   (GridManager)     |    | (VisualizationState)|
+-------------------+   +---------------------+   +-------------------+

核心组件说明：

  1. GridManager：管理网格地图数据，包括创建、修改墙壁、起点终点设置
  2. PathfindingWorker：在Web Worker中运行算法，避免阻塞UI线程
  3. CanvasRenderer：负责网格地图的绘制与动画效果
  4. EventHandler：处理用户交互事件（点击、拖拽、算法选择等）
  5. VisualizationState：管理算法执行过程中的可视化状态

实现步骤

第1步：搭建基础HTML结构与CSS样式

首先创建基础的HTML页面结构，包含控制面板、画布和状态信息区域。

<!-- index.html -->
<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>图算法路径查找器</title>
    <link rel="stylesheet" href="styles.css">
</head>
<body>
    <div class="container">
        <header>
            <h1>图算法路径查找器</h1>
            <p class="subtitle">交互式可视化学习平台</p>
        </header>
        
        <div class="main-content">
            <!-- 控制面板 -->
            <aside class="control-panel">
                <div class="panel-section">
                    <h3>地图控制</h3>
                    <button id="clear-map">清除地图</button>
                    <button id="generate-maze">生成迷宫</button>
                    <button id="clear-path">清除路径</button>
                </div>
                
                <div class="panel-section">
                    <h3>绘制模式</h3>
                    <div class="mode-buttons">
                        <button class="mode-btn active" data-mode="wall">墙壁</button>
                        <button class="mode-btn" data-mode="start">起点</button>
                        <button class="mode-btn" data-mode="end">终点</button>
                    </div>
                </div>
                
                <div class="panel-section">
                    <h3>算法选择</h3>
                    <select id="algorithm-select">
                        <option value="bfs">广度优先搜索 (BFS)</option>
                        <option value="dfs">深度优先搜索 (DFS)</option>
                        <option value="dijkstra">Dijkstra算法</option>
                        <option value="astar">A*算法</option>
                    </select>
                </div>
                
                <div class="panel-section">
                    <h3>动画控制</h3>
                    <div class="speed-control">
                        <label>动画速度：</label>
                        <input type="range" id="animation-speed" min="1" max="100" value="50">
                        <span id="speed-value">50</span>
                    </div>
                    <div class="button-group">
                        <button id="start-btn">开始搜索</button>
                        <button id="stop-btn">停止搜索</button>
                    </div>
                </div>
                
                <div class="panel-section stats">
                    <h3>算法统计</h3>
                    <div id="stats-container">
                        <div class="stat-item">
                            <span class="stat-label">探索节点：</span>
                            <span id="nodes-explored">0</span>
                        </div>
                        <div class="stat-item">
                            <span class="stat-label">路径长度：</span>
                            <span id="path-length">0</span>
                        </div>
                        <div class="stat-item">
                            <span class="stat-label">执行时间：</span>
                            <span id="execution-time">0ms</span>
                        </div>
                    </div>
                </div>
            </aside>
            
            <!-- 主画布区域 -->
            <main class="canvas-container">
                <div class="canvas-wrapper">
                    <canvas id="pathfinding-canvas"></canvas>
                    <div class="canvas-info">
                        <span>画布大小：<span id="canvas-size">30x20</span></span>
                        <span>格子大小：<span id="cell-size">20px</span></span>
                    </div>
                </div>
                
                <!-- 算法说明 -->
                <div class="algorithm-info" id="algorithm-info">
                    <h3 id="algo-title">广度优先搜索 (BFS)</h3>
                    <p id="algo-description">BFS是一种盲目搜索算法，它会系统地探索图的每一个节点。从起点开始，首先访问所有相邻节点，然后再访问这些节点的相邻节点，依此类推。</p>
                    <div class="complexity-info">
                        <span>时间复杂度：<span id="time-complexity">O(V + E)</span></span>
                        <span>空间复杂度：<span id="space-complexity">O(V)</span></span>
                    </div>
                </div>
            </main>
        </div>
        
        <!-- 图例说明 -->
        <footer class="legend">
            <div class="legend-item">
                <div class="legend-color start"></div>
                <span>起点</span>
            </div>
            <div class="legend-item">
                <div class="legend-color end"></div>
                <span>终点</span>
            </div>
            <div class="legend-item">
                <div class="legend-color wall"></div>
                <span>墙壁</span>
            </div>
            <div class="legend-item">
                <div class="legend-color visited"></div>
                <span>已访问</span>
            </div>
            <div class="legend-item">
                <div class="legend-color frontier"></div>
                <span>待探索</span>
            </div>
            <div class="legend-item">
                <div class="legend-color path"></div>
                <span>最终路径</span>
            </div>
        </footer>
    </div>

    <!-- JavaScript模块 -->
    <script src="js/GridManager.js"></script>
    <script src="js/PathfindingWorker.js"></script>
    <script src="js/CanvasRenderer.js"></script>
    <script src="js/EventHandler.js"></script>
    <script src="js/main.js"></script>
</body>
</html>

/* styles.css */
:root {
    --primary-color: #4a6fa5;
    --secondary-color: #6c8fc4;
    --success-color: #4caf50;
    --warning-color: #ff9800;
    --danger-color: #f44336;
    --dark-color: #2c3e50;
    --light-color: #ecf0f1;
}

* {
    margin: 0;
    padding: 0;
    box-sizing: border-box;
}

body {
    font-family: 'Segoe UI', Tahoma, Geneva, Verdana, sans-serif;
    background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
    min-height: 100vh;
    padding: 20px;
}

.container {
    max-width: 1400px;
    margin: 0 auto;
    background: white;
    border-radius: 15px;
    box-shadow: 0 10px 30px rgba(0, 0, 0, 0.2);
    overflow: hidden;
}

header {
    background: var(--primary-color);
    color: white;
    padding: 20px 30px;
    text-align: center;
}

.subtitle {
    opacity: 0.8;
    margin-top: 5px;
}

.main-content {
    display: flex;
    min-height: 70vh;
}

.control-panel {
    width: 300px;
    background: var(--light-color);
    padding: 20px;
    border-right: 1px solid #ddd;
    overflow-y: auto;
}

.canvas-container {
    flex: 1;
    padding: 20px;
    display: flex;
    flex-direction: column;
}

.canvas-wrapper {
    position: relative;
    margin-bottom: 20px;
}

canvas {
    border: 2px solid var(--dark-color);
    background: white;
    cursor: crosshair;
}

.canvas-info {
    display: flex;
    justify-content: space-between;
    margin-top: 10px;
    font-size: 14px;
    color: #666;
}

.panel-section {
    background: white;
    padding: 15px;
    margin-bottom: 15px;
    border-radius: 8px;
    box-shadow: 0 2px 5px rgba(0, 0, 0, 0.1);
}

.panel-section h3 {
    color: var(--dark-color);
    margin-bottom: 12px;
    font-size: 16px;
    border-bottom: 2px solid var(--primary-color);
    padding-bottom: 5px;
}

button {
    background: var(--primary-color);
    color: white;
    border: none;
    padding: 10px 15px;
    margin: 5px;
    border-radius: 5px;
    cursor: pointer;
    transition: background 0.3s;
}

button:hover {
    background: var(--secondary-color);
}

button:disabled {
    background: #ccc;
    cursor: not-allowed;
}

.mode-buttons {
    display: flex;
    gap: 5px;
    margin-top: 10px;
}

.mode-btn {
    flex: 1;
    padding: 8px;
    font-size: 12px;
}

.mode-btn.active {
    background: var(--success-color);
}

select {
    width: 100%;
    padding: 10px;
    border: 1px solid #ddd;
    border-radius: 5px;
    margin-top: 10px;
}

.speed-control {
    margin: 15px 0;
}

.speed-control input[type="range"] {
    width: 100%;
    margin: 10px 0;
}

.button-group {
    display: flex;
    gap: 10px;
    margin-top: 15px;
}

.button-group button {
    flex: 1;
}

.stats {
    background: white;
}

.stat-item {
    display: flex;
    justify-content: space-between;
    padding: 8px 0;
    border-bottom: 1px solid #eee;
}

.stat-label {
    font-weight: bold;
    color: var(--dark-color);
}

.algorithm-info {
    background: var(--light-color);
    padding: 20px;
    border-radius: 8px;
    margin-top: auto;
}

.algorithm-info h3 {
    color: var(--primary-color);
    margin-bottom: 10px;
}

.algorithm-info p {
    color: #555;
    line-height: 1.6;
}

.complexity-info {
    display: flex;
    gap: 20px;
    margin-top: 15px;
    padding-top: 15px;
    border-top: 1px solid #ddd;
}

.legend {
    display: flex;
    justify-content: center;
    gap: 30px;
    padding: 20px;
    background: var(--light-color);
    border-top: 1px solid #ddd;
}

.legend-item {
    display: flex;
    align-items: center;
    gap: 8px;
}

.legend-color {
    width: 20px;
    height: 20px;
    border-radius: 4px;
}

.start { background: #4CAF50; }
.end { background: #f44336; }
.wall { background: #333; }
.visited { background: #2196F3; opacity: 0.6; }
.frontier { background: #FF9800; }
.path { background: #FFEB3B; }

@media (max-width: 1024px) {
    .main-content {
        flex-direction: column;
    }
    
    .control-panel {
        width: 100%;
        border-right: none;
        border-bottom: 1px solid #ddd;
    }
}

第2步：实现网格地图管理器

创建GridManager.js，负责管理网格地图的状态。

// js/GridManager.js
class GridManager {
    constructor(rows = 30, cols = 20) {
        this.rows = rows;
        this.cols = cols;
        this.grid = [];
        this.startNode = null;
        this.endNode = null;
        this.isMouseDown = false;
        this.currentMode = 'wall';
        
        this.initializeGrid();
    }
    
    // 初始化网格
    initializeGrid() {
        this.grid = [];
        for (let row = 0; row < this.rows; row++) {
            this.grid[row] = [];
            for (let col = 0; col < this.cols; col++) {
                this.grid[row][col] = {
                    row,
                    col,
                    isWall: false,
                    isStart: false,
                    isEnd: false,
                    isVisited: false,
                    isInPath: false,
                    distance: Infinity,
                    totalDistance: Infinity, // 对于Dijkstra和A*算法
                    heuristic: 0, // 对于A*算法
                    parent: null,
                    fScore: Infinity, // A*算法的f(n) = g(n) + h(n)
                    gScore: Infinity, // A*算法的g(n)
                };
            }
        }
        
        // 设置默认起点和终点
        this.startNode = this.grid[Math.floor(this.rows / 2)][5];
        this.startNode.isStart = true;
        
        this.endNode = this.grid[Math.floor(this.rows / 2)][this.cols - 6];
        this.endNode.isEnd = true;
    }
    
    // 设置墙壁
    setWall(row, col, isWall) {
        if (this.isValidPosition(row, col)) {
            const node = this.grid[row][col];
            if (!node.isStart && !node.isEnd) {
                node.isWall = isWall;
                return true;
            }
        }
        return false;
    }
    
    // 设置起点
    setStart(row, col) {
        if (this.isValidPosition(row, col)) {
            const node = this.grid[row][col];
            if (!node.isWall && !node.isEnd) {
                // 清除旧起点
                if (this.startNode) {
                    this.startNode.isStart = false;
                }
                
                // 设置新起点
                node.isStart = true;
                this.startNode = node;
                return true;
            }
        }
        return false;
    }
    
    // 设置终点
    setEnd(row, col) {
        if (this.isValidPosition(row, col)) {
            const node = this.grid[row][col];
            if (!node.isWall && !node.isStart) {
                // 清除旧终点
                if (this.endNode) {
                    this.endNode.isEnd = false;
                }
                
                // 设置新终点
                node.isEnd = true;
                this.endNode = node;
                return true;
            }
        }
        return false;
    }
    
    // 验证位置是否有效
    isValidPosition(row, col) {
        return row >= 0 && row < this.rows && col >= 0 && col < this.cols;
    }
    
    // 获取邻居节点（上下左右四个方向）
    getNeighbors(node) {
        const neighbors = [];
        const directions = [
            { row: -1, col: 0 }, // 上
            { row: 1, col: 0 },  // 下
            { row: 0, col: -1 }, // 左
            { row: 0, col: 1 },  // 右
        ];
        
        for (const dir of directions) {
            const newRow = node.row + dir.row;
            const newCol = node.col + dir.col;
            
            if (this.isValidPosition(newRow, newCol)) {
                const neighbor = this.grid[newRow][newCol];
                if (!neighbor.isWall) {
                    neighbors.push(neighbor);
                }
            }
        }
        
        return neighbors;
    }
    
    // 获取对角线邻居（用于支持对角线移动）
    getDiagonalNeighbors(node) {
        const neighbors = this.getNeighbors(node);
        const diagonalDirections = [
            { row: -1, col: -1 }, // 左上
            { row: -1, col: 1 },  // 右上
            { row: 1, col: -1 },  // 左下
            { row: 1, col: 1 },   // 右下
        ];
        
        for (const dir of diagonalDirections) {
            const newRow = node.row + dir.row;
            const newCol = node.col + dir.col;
            
            if (this.isValidPosition(newRow, newCol)) {
                const neighbor = this.grid[newRow][newCol];
                if (!neighbor.isWall) {
                    neighbors.push(neighbor);
                }
            }
        }
        
        return neighbors;
    }
    
    // 清除所有路径标记
    clearPath() {
        for (let row = 0; row < this.rows; row++) {
            for (let col = 0; col < this.cols; col++) {
                const node = this.grid[row][col];
                node.isVisited = false;
                node.isInPath = false;
                node.distance = Infinity;
                node.totalDistance = Infinity;
                node.heuristic = 0;
                node.parent = null;
                node.fScore = Infinity;
                node.gScore = Infinity;
            }
        }
    }
    
    // 清除整个地图
    clearMap() {
        this.initializeGrid();
    }
    
    // 生成简单迷宫
    generateMaze() {
        this.clearMap();
        
        // 使用递归回溯算法生成迷宫
        for (let row = 0; row < this.rows; row++) {
            for (let col = 0; col < this.cols; col++) {
                // 随机生成墙壁（30%概率）
                if (Math.random() < 0.3) {
                    this.setWall(row, col, true);
                }
            }
        }
        
        // 确保起点和终点不是墙壁
        this.setWall(this.startNode.row, this.startNode.col, false);
        this.setWall(this.endNode.row, this.endNode.col, false);
        
        return this.grid;
    }
    
    // 获取网格的副本（用于算法计算）
    getGridCopy() {
        return this.grid.map(row => row.map(node => ({...node})));
    }
    
    // 从副本恢复状态
    restoreFromCopy(gridCopy) {
        this.grid = gridCopy;
        this.startNode = this.grid.find(row => row.find(node => node.isStart)).find(node => node.isStart);
        this.endNode = this.grid.find(row => row.find(node => node.isEnd)).find(node => node.isEnd);
    }
    
    // 根据行列获取画布坐标
    getCanvasPosition(row, col, cellSize) {
        return {
            x: col * cellSize,
            y: row * cellSize
        };
    }
    
    // 根据画布坐标获取行列
    getGridPosition(x, y, cellSize) {
        return {
            row: Math.floor(y / cellSize),
            col: Math.floor(x / cellSize)
        };
    }
}

// 导出GridManager类供其他模块使用
window.GridManager = GridManager;

第3步：实现路径查找算法

创建PathfindingWorker.js，包含四种算法的实现。

// js/PathfindingWorker.js
class PathfindingWorker {
    constructor() {
        this.algorithms = {
            bfs: this.bfs.bind(this),
            dfs: this.dfs.bind(this),
            dijkstra: this.dijkstra.bind(this),
            astar: this.astar.bind(this)
        };
    }
    
    // 广度优先搜索算法
    bfs(grid, startNode, endNode) {
        const gridCopy = this.getGridCopy(grid);
        const start = gridCopy[startNode.row][startNode.col];
        const end = gridCopy[endNode.row][endNode.col];
        
        const queue = [start];
        const visited = new Set();
        visited.add(`${start.row},${start.col}`);
        
        let nodesExplored = 0;
        
        while (queue.length > 0) {
            const currentNode = queue.shift();
            nodesExplored++;
            
            // 找到终点
            if (currentNode.row === end.row && currentNode.col === end.col) {
                return this.reconstructPath(currentNode, nodesExplored);
            }
            
            // 获取邻居节点
            const neighbors = this.getNeighbors(gridCopy, currentNode);
            
            for (const neighbor of neighbors) {
                const key = `${neighbor.row},${neighbor.col}`;
                if (!visited.has(key)) {
                    visited.add(key);
                    neighbor.parent = currentNode;
                    queue.push(neighbor);
                }
            }
        }
        
        return { path: [], nodesExplored, success: false };
    }
    
    // 深度优先搜索算法
    dfs(grid, startNode, endNode) {
        const gridCopy = this.getGridCopy(grid);
        const start = gridCopy[startNode.row][startNode.col];
        const end = gridCopy[endNode.row][endNode.col];
        
        const stack = [start];
        const visited = new Set();
        visited.add(`${start.row},${start.col}`);
        
        let nodesExplored = 0;
        
        while (stack.length > 0) {
            const currentNode = stack.pop();
            nodesExplored++;
            
            // 找到终点
            if (currentNode.row === end.row && currentNode.col === end.col) {
                return this.reconstructPath(currentNode, nodesExplored);
            }
            
            // 获取邻居节点
            const neighbors = this.getNeighbors(gridCopy, currentNode);
            
            for (const neighbor of neighbors) {
                const key = `${neighbor.row},${neighbor.col}`;
                if (!visited.has(key)) {
                    visited.add(key);
                    neighbor.parent = currentNode;
                    stack.push(neighbor);
                }
            }
        }
        
        return { path: [], nodesExplored, success: false };
    }
    
    // Dijkstra算法
    dijkstra(grid, startNode, endNode) {
        const gridCopy = this.getGridCopy(grid);
        const start = gridCopy[startNode.row][startNode.col];
        const end = gridCopy[endNode.row][endNode.col];
        
        // 初始化距离
        start.distance = 0;
        
        // 使用优先队列（最小堆）来优化
        const priorityQueue = new MinHeap();
        priorityQueue.enqueue(start, 0);
        
        let nodesExplored = 0;
        
        while (!priorityQueue.isEmpty()) {
            const currentNode = priorityQueue.dequeue().node;
            nodesExplored++;
            
            // 跳过已处理的节点
            if (currentNode.isProcessed) continue;
            currentNode.isProcessed = true;
            
            // 找到终点
            if (currentNode.row === end.row && currentNode.col === end.col) {
                return this.reconstructPath(currentNode, nodesExplored);
            }
            
            // 获取邻居节点
            const neighbors = this.getNeighbors(gridCopy, currentNode);
            
            for (const neighbor of neighbors) {
                const tentativeDistance = currentNode.distance + 1; // 假设每步距离为1
                
                if (tentativeDistance < neighbor.distance) {
                    neighbor.distance = tentativeDistance;
                    neighbor.parent = currentNode;
                    priorityQueue.enqueue(neighbor, tentativeDistance);
                }
            }
        }
        
        return { path: [], nodesExplored, success: false };
    }
    
    // A*算法
    astar(grid, startNode, endNode, heuristic = 'manhattan') {
        const gridCopy = this.getGridCopy(grid);
        const start = gridCopy[startNode.row][startNode.col];
        const end = gridCopy[endNode.row][endNode.col];
        
        // 初始化距离
        start.gScore = 0;
        start.fScore = this.calculateHeuristic(start, end, heuristic);
        
        // 使用优先队列（最小堆）
        const openSet = new MinHeap();
        openSet.enqueue(start, start.fScore);
        
        const closedSet = new Set();
        let nodesExplored = 0;
        
        while (!openSet.isEmpty()) {
            const currentNode = openSet.dequeue().node;
            nodesExplored++;
            
            // 找到终点
            if (currentNode.row === end.row && currentNode.col === end.col) {
                return this.reconstructPath(currentNode, nodesExplored);
            }
            
            closedSet.add(`${currentNode.row},${currentNode.col}`);
            
            // 获取邻居节点
            const neighbors = this.getNeighbors(gridCopy, currentNode);
            
            for (const neighbor of neighbors) {
                const neighborKey = `${neighbor.row},${neighbor.col}`;
                
                if (closedSet.has(neighborKey)) continue;
                
                const tentativeGScore = currentNode.gScore + 1; // 假设每步距离为1
                
                if (tentativeGScore < neighbor.gScore) {
                    neighbor.parent = currentNode;
                    neighbor.gScore = tentativeGScore;
                    neighbor.fScore = tentativeGScore + this.calculateHeuristic(neighbor, end, heuristic);
                    
                    if (!openSet.contains(neighbor)) {
                        openSet.enqueue(neighbor, neighbor.fScore);
                    }
                }
            }
        }
        
        return { path: [], nodesExplored, success: false };
    }
    
    // 计算启发式函数
    calculateHeuristic(node, endNode, type = 'manhattan') {
        const dx = Math.abs(node.col - endNode.col);
        const dy = Math.abs(node.row - endNode.row);
        
        switch (type) {
            case 'manhattan': // 曼哈顿距离
                return dx + dy;
            case 'euclidean': // 欧几里得距离
                return Math.sqrt(dx * dx + dy * dy);
            case 'diagonal': // 对角线距离
                return Math.max(dx, dy);
            default:
                return dx + dy;
        }
    }
    
    // 重建路径
    reconstructPath(endNode, nodesExplored) {
        const path = [];
        let currentNode = endNode;
        
        while (currentNode) {
            path.unshift({
                row: currentNode.row,
                col: currentNode.col
            });
            currentNode = currentNode.parent;
        }
        
        return {
            path,
            nodesExplored,
            success: true,
            pathLength: path.length
        };
    }
    
    // 获取网格副本
    getGridCopy(grid) {
        return grid.map(row => row.map(node => ({
            ...node,
            isProcessed: false,
            parent: null
        })));
    }
    
    // 获取邻居节点
    getNeighbors(grid, node) {
        const neighbors = [];
        const directions = [
            { row: -1, col: 0 }, // 上
            { row: 1, col: 0 },  // 下
            { row: 0, col: -1 }, // 左
            { row: 0, col: 1 },  // 右
        ];
        
        for (const dir of directions) {
            const newRow = node.row + dir.row;
            const newCol = node.col + dir.col;
            
            if (newRow >= 0 && newRow < grid.length && 
                newCol >= 0 && newCol < grid[0].length) {
                const neighbor = grid[newRow][newCol];
                if (!neighbor.isWall) {
                    neighbors.push(neighbor);
                }
            }
        }
        
        return neighbors;
    }
    
    // 执行指定算法
    execute(algorithmName, grid, startNode, endNode) {
        const algorithm = this.algorithms[algorithmName];
        if (!algorithm) {
            throw new Error(`不支持的算法: ${algorithmName}`);
        }
        
        return algorithm(grid, startNode, endNode);
    }
}

// 最小堆实现（优先队列）
class MinHeap {
    constructor() {
        this.heap = [];
    }
    
    enqueue(node, priority) {
        this.heap.push({ node, priority });
        this.bubbleUp(this.heap.length - 1);
    }
    
    dequeue() {
        if (this.isEmpty()) return null;
        
        const min = this.heap[0];
        const end = this.heap.pop();
        
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.sinkDown(0);
        }
        
        return min;
    }
    
    contains(node) {
        return this.heap.some(item => 
            item.node.row === node.row && item.node.col === node.col
        );
    }
    
    isEmpty() {
        return this.heap.length === 0;
    }
    
    bubbleUp(index) {
        const element = this.heap[index];
        
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            const parent = this.heap[parentIndex];
            
            if (element.priority >= parent.priority) break;
            
            this.heap[parentIndex] = element;
            this.heap[index] = parent;
            index = parentIndex;
        }
    }
    
    sinkDown(index) {
        const length = this.heap.length;
        const element = this.heap[index];
        
        while (true) {
            let leftChildIdx = 2 * index + 1;
            let rightChildIdx = 2 * index + 2;
            let leftChild, rightChild;
            let swap = null;
            
            if (leftChildIdx < length) {
                leftChild = this.heap[leftChildIdx];
                if (leftChild.priority < element.priority) {
                    swap = leftChildIdx;
                }
            }
            
            if (rightChildIdx < length) {
                rightChild = this.heap[rightChildIdx];
                if ((swap === null && rightChild.priority < element.priority) ||
                    (swap !== null && rightChild.priority < leftChild.priority)) {
                    swap = rightChildIdx;
                }
            }
← 排序算法可视化器数据结构标准库实现 →