clrs
简介
提供基础的数据结构和算法
组件接口
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) |
类
Deque
双端队列
成员变量
| 变量名 | 类型 | 初始值 | 须初始化 | 描述 |
|---|
成员方法
| 函数原型 | 函数作用 |
|---|---|
| void push_front(mixed item) | 在前端插入元素 |
| void push_back(mixed item) | 在尾端插入元素 |
| mixed pop_front() | 删除并返回队首元素 |
| mixed pop_back() | 删除并返回队尾元素 |
| mixed front() | 返回队首元素 |
| mixed back() | 返回队尾元素 |
| int size() | 获取队列元素数量 |
MinStack
最小栈
成员变量
| 变量名 | 类型 | 初始值 | 须初始化 | 描述 |
|---|
成员方法
| 函数原型 | 函数作用 |
|---|---|
| mixed top() | 获取栈顶元素 |
| void push(mixed item) | 向栈中添加元素 |
| void pop() | 弹出栈顶元素 |
| mixed get_min() | 获取最小元素 |
| int size() | 获取栈大小 |
OrderedSet
有序集合
成员变量
| 变量名 | 类型 | 初始值 | 须初始化 | 描述 |
|---|
成员方法
| 函数原型 | 函数作用 |
|---|---|
| void add(mixed key, mixed value = nil) | 向集合中添加元素，如果元素已存在集合中则覆盖之 |
| bool remove(mixed key) | 从集合中移除指定元素 |
| mixed query(mixed key) | 从集合中取出元素映射的值 |
| mixed lower_bound(mixed key) | 在集合中取出不小于key的最小元素 |
| mixed upper_bound(mixed key) | 在集合中取出大于key的最小元素 |
| mixed get_min() | 取出集合中的最小元素 |
| mixed get_max() | 取出集合中的最大元素 |
| int size() | 返回集合大小 |
| void empty() | 清空集合 |
PriorityQueue
优先队列
成员变量
| 变量名 | 类型 | 初始值 | 须初始化 | 描述 |
|---|
成员方法
| 函数原型 | 函数作用 |
|---|---|
| mixed top() | 获取队列中的最大元素，时间复杂度为O(1) |
| void push(mixed item) | 向队列中加入元素，时间复杂度为O(log N) |
| mixed pop() | 从队列中弹出并返回最大元素，时间复杂度为O(log N) |
| mixed remove(int pos) | 删除并返回指定位置的数据，时间复杂度为O(log N) |
| mixed remove_by_func(function f) | 删除符合条件的元素 |
| int size() | 返回队列大小 |
Stack
栈(先进后出)
成员变量
| 变量名 | 类型 | 初始值 | 须初始化 | 描述 |
|---|
成员方法
| 函数原型 | 函数作用 |
|---|---|
| mixed top() | 获取栈顶元素 |
| void push(mixed item) | 向栈中推入元素 |
| mixed pop() | 弹出并返回栈顶元素 |
| int size() | 返回栈大小 |
样例
public void sample()
{
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());
}