clrs
简介
提供基础的数据结构和算法
组件接口
deque.gs
双端队列
实现
底层基于array实现的，通过预留空间支持快速的前端插入，各种操作的均摊效率为常数时间。
| 函数原型 | 函数作用 |
|---|---|
| void push_front(Deque self, mixed item) | 在前端插入元素 |
| void push_back(Deque self, mixed item) | 在尾端插入元素 |
| mixed pop_front(Deque self) | 删除并返回队首元素 |
| mixed pop_back(Deque self) | 删除并返回队尾元素 |
| mixed front(Deque self) | 返回队首元素 |
| mixed back(Deque self) | 返回队尾元素 |
| int size(Deque self) | 获取队列元素数量 |
heap.gs
最大堆
实现
参考Python heapq，提供作用于array的堆操作函数。
| 函数原型 | 函数作用 |
|---|---|
| void heapify(array arr, function predicate = nil) | 在O(N)时间内将数组转换成堆 |
| void push(array arr, mixed item, function predicate = nil) | 将元素加入堆中，并保持堆的性质 |
| mixed pop(array arr, function predicate = nil) | 弹出并返回堆的最大值，并保持堆的性质 |
| mixed remove(array arr, int pos, function predicate = nil) | 从指定位置删除数据，并返回删除的数据 |
| void heap_sort(array arr, function predicate = nil) | 堆排序，时间复杂度为O(N * log N) |
ordered_set.gs
有序集合
- 尽管称为集合（set），但添加元素时（可选的）可以提供值，以支持映射。
- 不重复集合：当添加重复元素时，旧元素被覆盖。
- 要求元素支持良定义的比较，支持用户提供比较函数。
实现
基于AVL树实现的有序集合，集合操作的时间复杂度为O(log N)。
@ref AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.
@ref https://www.guru99.com/avl-tree.html
| 函数原型 | 函数作用 |
|---|---|
| void add(OrderedSet self, mixed key, mixed value = nil) | 向集合中添加元素，如果元素已存在集合中则覆盖之 |
| bool remove(OrderedSet self, mixed key) | 从集合中移除指定元素 |
| mixed query(OrderedSet self, mixed key) | 从集合中取出元素映射的值 |
| mixed lower_bound(OrderedSet self, mixed key) | 在集合中取出不小于key的最小元素 |
| mixed upper_bound(OrderedSet self, mixed key) | 在集合中取出大于key的最小元素 |
| mixed get_min(OrderedSet self) | 取出集合中的最小元素 |
| mixed get_max(OrderedSet self) | 取出集合中的最大元素 |
| int size(OrderedSet self) | 返回集合大小 |
| void empty(OrderedSet self) | 清空集合 |
priority_queue.gs
优先队列
要求元素支持良定义的比较，支持用户提供比较函数。
实现
基于最大堆实现的优先队列。
| 函数原型 | 函数作用 |
|---|---|
| mixed top(PriorityQueue self) | 获取队列中的最大元素，时间复杂度为O(1) |
| void push(PriorityQueue self, mixed item) | 向队列中加入元素，时间复杂度为O(log N) |
| mixed pop(PriorityQueue self) | 从队列中弹出并返回最大元素，时间复杂度为O(log N) |
| mixed remove(PriorityQueue self, int pos) | 删除并返回指定位置的数据，时间复杂度为O(log N) |
| int size(PriorityQueue self) | 返回队列大小 |
stack.gs
FILO栈
| 函数原型 | 函数作用 |
|---|---|
| mixed top(Stack self) | 获取栈顶元素 |
| void push(Stack self, mixed item) | 向栈中推入元素 |
| mixed pop(Stack self) | 弹出并返回栈顶元素 |
| int size(Stack self) | 返回栈大小 |
样例
public void sample()
{
load_static(clrs);
PriorityQueue pq = PriorityQueue.new();
pq.push(5);
pq.push(3);
pq.push(10);
// 10
printf("%d\n", pq.pop());
// 5
printf("%d\n", pq.pop());
// 3
printf("%d\n", pq.pop());
}