A dynamically prioritizable priority queue.

Related tags

Utilities binary-heap
Overview

bheap

ci-tests rustdoc FOSSA Status

A generic binary max heap implementation for implementing a dynamically prioritizable priority queue.

This implementation uses a vector as the underlying data-structure. Hence, there is no oppurtunity for fine grained locking. Users of this crate are request to wrap bheap::BinaryMaxHeap with the required concurrency primitive for use in multithreaded contexts.

Why is this necessary?

The binary heap implementation provided by the standard library (use std::collections::binary_heap::BinaryHeap;), assumes that the ordering of the elements in the domain is fixed. I needed a binary heap implementation which allowed for change in ordering of elements at runtime.

How does it work?

bheap::BinaryMaxHeap enforces the Ord + bheap::Uid trait bounds on the element type. The Uid trait, simply presents a method for returing a unique u64 uid for the type.

The struct maintains a Vec<T> as the underlying storage buffer and a HashMap<u64, usize> for maintaining a mapping from T::uid() to position in vector. This map is updated on every heap operation to remain consistent.

When the ordering of an element changes, its position in the heap can be looked up in the heap using the hashmap. Then, we heapify_up() or heapify_down() as required to restore heap property.

Limitations

Since, we use u64 for uniquely identitfying elements, this heap can only scale up 2^64 = 18446744073709551616 elements. This was more than enough for my purposes.

Another interesting property of this library is that it has no third party dependencies other than the standard libary.

License

bheap is licensed under the MIT License. See LICENSE for the full license text.

FOSSA Status

You might also like...
Deadliner helps you keep track of the time left for your deadline by dynamically updating the wallpaper of your desktop with the time left.
Deadliner helps you keep track of the time left for your deadline by dynamically updating the wallpaper of your desktop with the time left.

Deadliner Watch the YouTube video What's Deadliner? Deadliner is a cross-platform desktop application for setting deadline for a project and keeping t

Deadliner 34 Dec 16, 2022
Connects to Woodpecker CI and dynamically creates an agent in the cloud.

Picus Picus connects to a Woodpecker CI server and creates an agent in the cloud when there are pending jobs. The agent will be shutdown when there ar

Holger Dormann 13 Dec 17, 2022
Encode and decode dynamically constructed values of arbitrary shapes to/from SCALE bytes

scale-value · This crate provides a Value type, which is a runtime representation that is compatible with scale_info::TypeDef. It somewhat analogous t

Parity Technologies 15 Jun 24, 2023
Owned container for dynamically-sized types backed by inline memory

sized-dst This crate provides Dst, an owned container for dynamically-sized types (DSTs) that's backed by inline memory. The main use-case is owned tr

Yuhan Lin 8 Sep 6, 2024
A job queue built on sqlx and PostgreSQL.

sqlxmq A job queue built on sqlx and PostgreSQL. This library allows a CRUD application to run background jobs without complicating its deployment. Th

Diggory Blake 85 Jan 5, 2023
wait-free spsc linked-list queue with individually reusable nodes

A wait-free single-producer single-consumer linked-list queue with individually reusable nodes.

glowcoil 22 Dec 26, 2022
Beanstalk is a simple, fast work queue.

beanstalkd Simple and fast general purpose work queue.

Beanstalkd 6.3k Dec 30, 2022
disk backed wal queue

Repository Template  Queue like disk backed WAL Pronouced Quál - from the german wordrd for agony - because it is. Operations The basic concept is si

The Tremor Project 8 Jun 4, 2022
A lock-free thread-owned queue whereby tasks are taken by stealers in entirety via buffer swapping

Swap Queue A lock-free thread-owned queue whereby tasks are taken by stealers in entirety via buffer swapping. This is meant to be used [thread_local]

Thomas Sieverding 20 Sep 9, 2022
A lock-free multi-producer multi-consumer unbounded queue.

lf-queue A lock-free multi-producer multi-consumer unbounded queue. Examples [dependencies] lf-queue = "0.1" Single Producer - Single Consumer: use lf

Pierre Brouca 2 Sep 11, 2022
A better message queue built by rust

bettermq A better message queue built by rust I start this project to study Rust

Sun Junyi 13 Dec 16, 2022
A single-producer single-consumer Rust queue with smart batching

Batching Queue A library that implements smart batching between a producer and a consumer. In other words, a single-producer single-consumer queue tha

Roland Kuhn 2 Dec 21, 2021
Message/job queue based on bonsaidb, similar to sqlxmq.

Bonsaimq Simple database message queue based on bonsaidb. The project is highly influenced by sqlxmq. Warning: This project is in early alpha and shou

Flix 6 Nov 8, 2022
A scalable message queue powered by a segmented, partitioned, replicated and immutable log.
A scalable message queue powered by a segmented, partitioned, replicated and immutable log.

A scalable message queue powered by a segmented, partitioned, replicated and immutable log. This is currently a work in progress. laminarmq is intende

Arindam Das 20 Dec 16, 2022
A rocksdb.rs wrapper bringing stack and queue functionalities

RocksDB_sq (Stack & Queue) A Rust crate that adds stack and queue functionality to RocksDB. This crate provide a wrapper around a RocksDB database and

Nathan GD 5 May 16, 2023
Simple and flexible queue implementation for Rust with support for multiple backends (Redis, RabbitMQ, SQS, etc.)

Omniqueue Omniqueue is an abstraction layer over queue backends for Rust. It includes support for RabbitMQ, Redis streams, and SQS out of the box. The

Svix 8 May 26, 2023
A naive buffered/sync channel implementation in Rust, using the queue data structure

buffered-queue-rs Introduction This is my attempt at a simple and very naive buffered/synced queue implementation in Rust. The base thread-safe queue

Dhruv 4 Jul 22, 2023
A lightweight distributed message queue. Like AWS SQS and RSMQ but on Postgres.

Postgres Message Queue (PGMQ) A lightweight distributed message queue. Like AWS SQS and RSMQ but on Postgres. Features Lightweight - Built with Rust a

Tembo 15 Jul 25, 2023
RocksDB-based queue with python bindings

RocksQ An inproc RocksDB-based queue with Python bindings. It is implemented in Rust. Features: max capacity limit in number of elements; size calcula

In-Sight 4 Oct 17, 2023
Comments
Releases(v0.1.0)

  • v0.1.0(Oct 11, 2021)

    Initial release.

    • Basic heap interface implemented.
      • Priority queue operations supported.
      • Dynamic re-ordering supported.
    • Added comprehensive tests to ensure the correctness of all invariants.
    Source code(tar.gz)
    Source code(zip)
Owner
Arindam Das
Specializes in Deep Learning model serving and AI SaaS at scale.
Arindam Das
GitHub https://arindas.github.io/bheap/bheap/index.html
This crate allows you to safely initialize Dynamically Sized Types (DST) using only safe Rust.

This crate allows you to safely initialize Dynamically Sized Types (DST) using only safe Rust.

Christofer Nolander 11 Dec 22, 2022
A naive buffered/sync channel implementation in Rust, using the queue data structure

buffered-queue-rs Introduction This is my attempt at a simple and very naive buffered/synced queue implementation in Rust. The base thread-safe queue

Dhruv 4 Jul 22, 2023
A lightweight distributed message queue. Like AWS SQS and RSMQ but on Postgres.

Postgres Message Queue (PGMQ) A lightweight distributed message queue. Like AWS SQS and RSMQ but on Postgres. Features Lightweight - Built with Rust a

Tembo 15 Jul 25, 2023
A priority queue for Rust with efficient change function.

PriorityQueue This crate implements a Priority Queue with a function to change the priority of an object. Priority and items are stored in an IndexMap

null 139 Dec 30, 2022
A simple thread schedule and priority library for rust

thread-priority A simple library to control thread schedule policies and thread priority. If your operating system isn't yet supported, please, create

Victor Polevoy 62 Dec 5, 2022
A rusty dynamically typed scripting language

dyon A rusty dynamically typed scripting language Tutorial Dyon-Interactive Dyon Snippets /r/dyon Dyon script files end with .dyon. To run Dyon script

PistonDevelopers 1.5k Dec 27, 2022
Dynamically get the suggested clusters in the data for unsupervised learning.

Python implementation of the Gap Statistic Purpose Dynamically identify the suggested number of clusters in a data-set using the gap statistic. Full e

Miles Granger 163 Dec 9, 2022
A dynamically typed, interpreted, stack-based language.

Stacc A dynamically typed, interpreted, stack-based language. How does it work? Each call-frame/scope has its own variables and stack, so you can get/

null 8 Nov 12, 2021
Dynamically invoke arbitrary unmanaged code.

DInvoke_rs Rust port of Dinvoke. DInvoke_rs may be used for many purposes such as PE parsing, dynamic exported functions resolution, dynamically loadi

Kurosh Dabbagh Escalante 149 Dec 24, 2022
This crate allows you to safely initialize Dynamically Sized Types (DST) using only safe Rust.

This crate allows you to safely initialize Dynamically Sized Types (DST) using only safe Rust.

Christofer Nolander 11 Dec 22, 2022