=============

PriorityQueue

.. image:: https://img.shields.io/crates/v/priority-queue.svg :target: https://crates.io/crates/priority-queue .. image:: https://travis-ci.org/garro95/priority-queue.svg?branch=master :target: https://travis-ci.org/garro95/priority-queue

This crate implements a Priority Queue with a function to change the priority of an object. Priority and items are stored in an IndexMap and the queue is implemented as a Heap of indexes.

Please read the API documentation here__

__ https://docs.rs/priority-queue/

Usage

To use this crate, simply add the following string to your Cargo.toml:

  priority-queue = "0.5.2"

Notice that a change in the last digit (patch number) means that the interface is backward and forward compatible and contains other type of fixes, like bug fixes or documentation updates. A change in the middle digit (minor) means that the interface is backward compatible but includes something new, so that the previous version may be not forward compatible. A change in the first, left digit may means a breacking change in the interface, that will not be backward compatible anymore. Version 1.0.0 may be an exception to this and may means just that the API is stable and is considered production ready.

Then use the data structure inside your Rust source code as in the following Example.

Remember that, if you need serde support, you should compile using --features serde.

Example

.. code:: rust

  extern crate priority_queue;

  use priority_queue::PriorityQueue;

  fn main() {
      let mut pq = PriorityQueue::new();

      assert!(pq.is_empty());
      pq.push("Apples", 5);
      pq.push("Bananas", 8);
      pq.push("Strawberries", 23);

      assert_eq!(pq.peek(), Some((&"Strawberries", &23)));

      for (item, _) in pq.into_sorted_iter() {
          println!("{}", item);
      }
  }

Note: in recent versions of Rust (edition 2018) the extern crate priority_queue is not necessary anymore!

Speeding up

You can use custom BuildHasher for the underlying IndexMap and therefore achieve better performance. For example you can create the queue with the speedy FxHash_ hasher:

.. code:: rust

  use hashbrown::hash_map::DefaultHashBuilder;

  let mut pq = PriorityQueue::<_, _, DefaultHashBuilder>::with_default_hasher();

.. _FxHash: https://github.com/Amanieu/hashbrown

Benchmarks

Some benchmarks have been run to compare the performances of this priority queue to the standard BinaryHeap, also using the FxHash hasher. The benchmarks produced the following results: :: test benchmarks::pushandpop ... bench: 80 ns/iter (+/- 6) test benchmarks::pushandpopfx ... bench: 49 ns/iter (+/- 5) test benchmarks::pushandpoponlargequeue ... bench: 296 ns/iter (+/- 25) test benchmarks::pushandpoponlargequeuefx ... bench: 259 ns/iter (+/- 41) test benchmarks::pushandpoponlargequeuestd ... bench: 75 ns/iter (+/- 6) test benchmarks::pushandpop_std ... bench: 11 ns/iter (+/- 1)

Contributing

Feel free to contribute to this project with pull requests and/or issues. All contribution should be under a license compatible with the GNU LGPL.

Changes