Anonymous user
Priority queue: Difference between revisions
→{{header|XLISP}}
Line 5,374:
()</lang>
=={{header|Zig}}==
Zig's standard library has a built-in implementation of the Priority Queue data structure.
Save the following code as <code>priority_queue.zig</code>, and run the tests using <code>zig test priority_queue.zig</code>.
<lang Zig>
const std = @import("std");
const PriorityQueue = std.PriorityQueue;
const Allocator = std.mem.Allocator;
const testing = std.testing;
/// wrapper for the task - stores task priority
/// along with the task name
const Task = struct {
const Self = @This();
priority: i32,
name: []const u8,
pub fn init(priority: i32, name: []const u8) Self {
return Self{
.priority = priority,
.name = name,
};
}
};
/// Simple wrapper for the comparator function.
/// Each comparator function has the following signature:
///
/// fn(T, T) bool
const Comparator = struct {
fn maxCompare(a: Task, b: Task) bool {
return a.priority > b.priority;
}
fn minCompare(a: Task, b: Task) bool {
return a.priority < b.priority;
}
};
test "priority queue (max heap)" {
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit();
var allocator = &arena.allocator;
var pq = PriorityQueue(Task).init(allocator, Comparator.maxCompare);
defer pq.deinit();
try pq.add(Task.init(3, "Clear drains"));
try pq.add(Task.init(4, "Feed Cat"));
try pq.add(Task.init(5, "Make tea"));
try pq.add(Task.init(1, "Solve RC tasks"));
try pq.add(Task.init(2, "Tax returns"));
testing.expectEqual(pq.count(), 5);
std.debug.print("\n", .{});
// execute the tasks in decreasing order of priority
while (pq.count() != 0) {
const task = pq.remove();
std.debug.print("Executing: {} (priority {})\n", .{ task.name, task.priority });
}
std.debug.print("\n", .{});
}
test "priority queue (min heap)" {
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit();
var allocator = &arena.allocator;
var pq = PriorityQueue(Task).init(allocator, Comparator.minCompare);
defer pq.deinit();
try pq.add(Task.init(3, "Clear drains"));
try pq.add(Task.init(4, "Feed Cat"));
try pq.add(Task.init(5, "Make tea"));
try pq.add(Task.init(1, "Solve RC tasks"));
try pq.add(Task.init(2, "Tax returns"));
testing.expectEqual(pq.count(), 5);
std.debug.print("\n", .{});
// execute the tasks in increasing order of priority
while (pq.count() != 0) {
const task = pq.remove();
std.debug.print("Executing: {} (priority {})\n", .{ task.name, task.priority });
}
std.debug.print("\n", .{});
}
</lang>
Sample output:
<lang Zig>
$ zig test priority_queue.zig
Test [1/2] test "priority queue (max heap)"...
Executing: Make tea (priority 5)
Executing: Feed Cat (priority 4)
Executing: Clear drains (priority 3)
Executing: Tax returns (priority 2)
Executing: Solve RC tasks (priority 1)
Test [2/2] test "priority queue (min heap)"...
Executing: Solve RC tasks (priority 1)
Executing: Tax returns (priority 2)
Executing: Clear drains (priority 3)
Executing: Feed Cat (priority 4)
Executing: Make tea (priority 5)
All 2 tests passed.
</lang>
=={{header|zkl}}==
| |||