Shell脚本如何实现优先队列堆

wen 实用脚本 2026-07-06 16

Shell脚本实现优先队列堆：从原理到实践的全解析

📖 目录导读

优先队列与堆的核心概念
Shell脚本实现堆的技术挑战
完整实现方案：数组模拟二叉堆
实战示例：任务优先级调度
性能优化与边界处理
常见问题问答

优先队列与堆的核心概念

优先队列（Priority Queue）是一种数据结构，其中每个元素都拥有一个优先级，高优先级的元素总是先被取出，堆（Heap）是实现优先队列最常用的数据结构，分为最大堆（父节点值≥子节点）和最小堆（父节点值≤子节点）。

Shell脚本如何实现优先队列堆

在Shell脚本中,由于缺乏原生数据结构和指针，我们需要通过数组模拟来实现完全二叉树，关键操作包括：

siftUp（上浮）：插入新元素时向上调整，保持堆性质。
siftDown（下沉）：删除堆顶时向下调整。

Shell脚本实现堆的技术挑战

Shell的数组是稀疏索引的，操作效率较低，实现堆时需注意：

使用declare -a显式声明数组。
堆索引从1开始,避免0索引的复杂计算。
由于Shell不支持复杂对象,需通过键值对存储优先级与数据。

对比其他语言：Python有heapq，C++有priority_queue，而Shell需要手写所有堆操作函数。

完整实现方案：数组模拟二叉堆

以下是支持最小堆的Shell实现（可轻松改为最大堆）：

#!/bin/bash
# 初始化堆数组，索引从1开始
heap=()
heap_size=0
# 插入元素：参数为 优先级 数据
enqueue() {
    local priority=$1
    local data=$2
    local i=$((++heap_size))
    # 存储：用关联数组模拟，但简单起见用两个平行数组
    heap_priority[$i]=$priority
    heap_data[$i]=$data
    # 上浮调整
    while [ $i -gt 1 ]; do
        local parent=$((i/2))
        # 最小堆：如果子节点小于父节点则交换
        if [ ${heap_priority[$i]} -lt ${heap_priority[$parent]} ]; then
            # 交换优先级
            local tmp=${heap_priority[$i]}
            heap_priority[$i]=${heap_priority[$parent]}
            heap_priority[$parent]=$tmp
            # 交换数据
            tmp=${heap_data[$i]}
            heap_data[$i]=${heap_data[$parent]}
            heap_data[$parent]=$tmp
            i=$parent
        else
            break
        fi
    done
}

出队函数（获取最小值）：

dequeue() {
    if [ $heap_size -eq 0 ]; then
        echo "Heap empty"
        return 1
    fi
    # 返回堆顶
    local priority=${heap_priority[1]}
    local data=${heap_data[1]}
    # 将最后一个元素移到堆顶
    heap_priority[1]=${heap_priority[$heap_size]}
    heap_data[1]=${heap_data[$heap_size]}
    unset heap_priority[$heap_size]
    unset heap_data[$heap_size]
    ((heap_size--))
    # 下沉调整
    local i=1
    while [ $((i*2)) -le $heap_size ]; do
        local child=$((i*2))
        # 选择较小的子节点
        if [ $((child+1)) -le $heap_size ] && [ ${heap_priority[$((child+1))]} -lt ${heap_priority[$child]} ]; then
            child=$((child+1))
        fi
        if [ ${heap_priority[$child]} -lt ${heap_priority[$i]} ]; then
            tmp=${heap_priority[$i]}
            heap_priority[$i]=${heap_priority[$child]}
            heap_priority[$child]=$tmp
            tmp=${heap_data[$i]}
            heap_data[$i]=${heap_data[$child]}
            heap_data[$child]=$tmp
            i=$child
        else
            break
        fi
    done
    echo "$data (priority: $priority)"
}

实战示例：任务优先级调度

假设有多个任务,每个任务有优先级（数值越小优先级越高）：

# 添加任务
enqueue 3 "发送邮件"
enqueue 1 "处理支付"
enqueue 2 "生成报告"
enqueue 5 "清理缓存"
echo "处理顺序："
dequeue   # 输出：处理支付 (priority: 1)
dequeue   # 输出：生成报告 (priority: 2)
dequeue   # 输出：发送邮件 (priority: 3)
dequeue   # 输出：清理缓存 (priority: 5)

注意：Shell数组若未声明为局部变量，需用local或declare -g修饰函数内部变量，避免污染全局空间。