盒子
盒子
文章目录
  1. Nim 每日早茶
    1. heapqueue 简介
    2. 实现优先队列
    3. 每日库推荐

如何使用 Nim 语言实现优先队列

Nim 每日早茶

Nim 语言实现优先队列

https://tea.nim-cn.com/archives/

heapqueue 简介

heapqueue 是一种名为堆的数据结构。
在 Nim 语言中 heapqueue 为小顶堆,意思是说第一个元素为堆中最小的元素。
支持 push, pop 等操作,push 函数用于向堆中添加元素,pop 函数用于从堆中删除最小的元素,并返回这个元素。

实现优先队列

首先,我们构造优先队列中的元素对象,因为 heapqueue 模块要求包含的对象是可以比较大小的,所以我们还需要重载小于操作符。priority 参数是该元素的优先级,由用户提供。idx 表示的是元素被添加到堆中的顺序,而 item 参数表示添加的元素。我们通过 priorityidx 元素的值来比较对象的大小。

1
2
3
4
5
6
7
8
type
PriorityItem*[T] = tuple
priority: float
idx: int
item: T

proc `<`*[T](self, other: PriorityItem[T]): bool =
return (self.priority, self.idx) < (other.priority, other.idx)

接下来构造优先队列的数据结构。由于PriorityQueue对象是 ref 类型,所以初始化的时候需要用到 new 关键字。添加元素的时候,我们使用 -priority ,这样 pop 得到的元素就是优先级最大的那个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import heapqueue

type
PriorityQueue*[T] = ref object
data*: HeapQueue[PriorityItem[T]]
idx: int
maxQueue: bool

proc newPriorityQueue*[T](maxQueue:bool=true): PriorityQueue[T] =
PriorityQueue[T](maxQueue: maxQueue)

proc push*[T](p: PriorityQueue[T], item: T, priority: float) =
if likely(p.maxQueue):
p.data.push((-priority, p.idx, item))
else:
p.data.push((priority, p.idx, item))
p.idx += 1

proc pop*[T](p: PriorityQueue[T]): T =
p.data.pop()[2]

proc `$`*[T](q: PriorityQueue[T]): string =
$q.data

最后,简单地测试一下函数的功能

1
2
3
4
5
6
7
8
9
10
11
12
when isMainModule:
type
Student* = object
id: int
name: string
var s = newPriorityQueue[Student]()
s.push(Student(id: 12, name: "小张"), 3)
s.push(Student(id: 12, name: "小李"), 4)
s.push(Student(id: 12, name: "小王"), 5)
s.push(Student(id: 12, name: "小周"), 1)
echo s.pop
echo s.pop

输出:

1
2
(id: 12, name: "小王")
(id: 12, name: "小李")

每日库推荐

Rod 是 Nim 实现的跨平台2d和3d游戏引擎。

https://github.com/yglukhov/rod