了解传奇算法，先从优先队列开始

萧山财神

优先队列是一种数据结构，其中每个元素都有一个优先级，元素按照优先级进行排序。优先队列常用于任务调度、路径搜索算法（如A*算法）等场景。下面是一个用 Lua 实现的优先队列示例，使用二叉堆（Binary Heap）作为底层数据结构。

优先队列实现

-- 定义优先队列类
PriorityQueue = {}
PriorityQueue.__index = PriorityQueue

function PriorityQueue:new()
    local pq = {
        heap = {}
    }
    setmetatable(pq, PriorityQueue)
    return pq
end

-- 插入元素
function PriorityQueue:insert(element, priority)
    local node = {element = element, priority = priority}
    table.insert(self.heap, node)
    self:_heapifyUp(#self.heap)
end

-- 提取具有最高优先级的元素
function PriorityQueue:extractMax()
    if #self.heap == 0 then
        return nil
    end

    local maxNode = self.heap[1]
    self.heap[1] = self.heap[#self.heap]
    table.remove(self.heap)
    self:_heapifyDown(1)

    return maxNode.element
end

-- 获取具有最高优先级的元素
function PriorityQueue:peek()
    if #self.heap == 0 then
        return nil
    end
    return self.heap[1].element
end

-- 上浮操作
function PriorityQueue:_heapifyUp(index)
    while index > 1 do
        local parentIndex = math.floor(index / 2)
        if self.heap[index].priority <= self.heap[parentIndex].priority then
            break
        end
        self.heap[index], self.heap[parentIndex] = self.heap[parentIndex], self.heap[index]
        index = parentIndex
    end
end

-- 下沉操作
function PriorityQueue:_heapifyDown(index)
    local leftChild, rightChild, largest
    while true do
        leftChild = 2 * index
        rightChild = 2 * index + 1
        largest = index

        if leftChild <= #self.heap and self.heap[leftChild].priority > self.heap[largest].priority then
            largest = leftChild
        end

        if rightChild <= #self.heap and self.heap[rightChild].priority > self.heap[largest].priority then
            largest = rightChild
        end

        if largest == index then
            break
        end

        self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]
        index = largest
    end
end

-- 测试优先队列
local pq = PriorityQueue:new()

pq:insert("task1", 1)
pq:insert("task2", 5)
pq:insert("task3", 3)
pq:insert("task4", 4)
pq:insert("task5", 2)

print("提取具有最高优先级的元素:")
print(pq:extractMax())  -- 输出: task2
print(pq:extractMax())  -- 输出: task4
print(pq:extractMax())  -- 输出: task3
print(pq:extractMax())  -- 输出: task5
print(pq:extractMax())  -- 输出: task1

解释

1. PriorityQueue类：定义了优先队列类，包含一个堆数组 heap。

   • new 方法：创建一个新的优先队列实例。
   • insert 方法：插入一个元素及其优先级，并进行上浮操作以维护堆的性质。
   • extractMax 方法：提取具有最高优先级的元素，并进行下沉操作以维护堆的性质。
   • peek 方法：获取具有最高优先级的元素，但不移除它。
   • _heapifyUp 方法：上浮操作，用于在插入元素后维护堆的性质。
   • _heapifyDown 方法：下沉操作，用于在提取元素后维护堆的性质。

2. 测试代码：创建一个优先队列实例，插入一些任务及其优先级，并提取具有最高优先级的任务。

输出

运行上述代码将输出以下内容：

提取具有最高优先级的元素:
task2
task4
task3
task5
task1

这个简单的优先队列实现可以根据实际需求进行调整，例如支持不同的优先级比较函数、处理更多的操作等。通过合理的优先队列算法，可以有效管理任务调度、路径搜索等场景中的优先级问题。

a159909252a

阿灵戈的启示：奋斗不息，梦想成真 New

IP属地：山东省