Home / Rust / Data structures

min-max-heap - An efficient, double-ended priority queue

min-max-heap: a double-ended priority queue A min-max-heap is like a binary heap, but it allows extracting both the minimum and maximum value efficien
Information
Category: Rust / Data structures
Watchers: 2
Star: 34
Fork: 9
Last update: Dec 1, 2023
Resource links
http://docs.rs/min-max-heap/
https://github.com/tov/min-max-heap-rs

min-max-heap: a double-ended priority queue

Build Status Crates.io License: MIT License: Apache 2.0

A min-max-heap is like a binary heap, but it allows extracting both the minimum and maximum value efficiently. In particular, finding either the minimum or maximum element is O(1). A removal of either extremum, or an insertion, is O(log n).

Usage

It’s on crates.io, so add this to your Cargo.toml:

[dependencies]
min-max-heap = "1.3.0"

This crate supports Rust version 1.32.0 and later.

References

My reference for a min-max heap is here. Much of this code is also based on BinaryHeap from the standard library.

1 Open More issues
Closed

Simplify push_pop_{max, min} and replace_{max, min} implementations

  • Use peek_{max, min}_mut() in push_pop_{max, min}() and replace_{max, min}() to reduce code duplication. Comparing the generated assembly, this seems to have a few performance effects (but I haven't benchmarked them):
    • push_pop_{max, min}() avoid swapping element to the heap if it is equal to max/min
    • push_pop_max() and replace_max() each avoid 2 bounds checks
    • push_pop_min() avoids a branch instruction
    • replace_{max, min}() avoid bubbling up the inserted value if the heap is empty
    • replace_max() swaps the min with element in a register instead of swapping two indices in the heap
    • The Peek{Max, Min}Mut struct is spilled to the stack
  • Avoid sifting a Peek{Max, Min}Mut if it was never mutably dereferenced (copied from Rust's BinaryHeap: https://github.com/rust-lang/rust/pull/75974).
  • Also fixes an overflow when dropping PeekMaxMut on a 1-element heap (which the quickcheck tests were now able to discover). Added a test for this.
opened Sep 4, 2020 by calebsander 5
Closed

Improve documentation for replace_min/max and push_pop_min/max

Resolve #9

This is mostly a copy-paste of your comment, with added links for clarity. Please double check that I did not made any mistake when copy-pasting between minimum/maximum and push/pop.

opened Sep 12, 2020 by robinmoussu 4
Closed

peek_*_mut

I'm using this library to implement k-way merge of multiple iterators. Essentially I push a tuple of each iterator and the next element it will yield into the heap, then the process of merging is to pull the max element off the heap, replace its current next element with its next next element, and return the previously-current one. In master this requires both a pop and a push, and correction of the heap after each. Neither replace_max nor push_pop_max quite get me what I want, because I'm going to be pushing the same element back onto the heap that I'm getting out, so I don't have it yet when I want to call replace.

The std::collections BinaryHeap has peek_mut which gets at this: you can get a mutable reference to the max item in the heap, and after that reference is dropped, the tree is re-heapified to account for any mutations that might change the item's rank. This PR ports that functionality to this library, as peek_min_mut and peek_max_mut.

opened Sep 2, 2019 by apendleton 4
Closed

Optimize is_min_level() function

This adds a couple of simple push/pop_min/pop_max benchmarks and applies a minor optimization to the is_min_level() function. Benchmarks before/after:

Before:
test pop_max_seq ... bench:      53,099 ns/iter (+/- 2,666)
test pop_min_seq ... bench:      77,194 ns/iter (+/- 3,006)
test push_seq    ... bench:      13,041 ns/iter (+/- 326)

After:
test pop_max_seq ... bench:      50,055 ns/iter (+/- 2,839)
test pop_min_seq ... bench:      74,374 ns/iter (+/- 3,805)
test push_seq    ... bench:      10,139 ns/iter (+/- 237)
opened May 3, 2018 by nikic 4
Closed

Check that `PeekMaxMut` has a parent before reading it

Fixes #16.

opened Apr 22, 2021 by cuviper 3
Closed

Avoid panics in all heap functions

Allows the compiler to infer that the core heap methods can't panic due to bounds checks. (push_pop_{max, min}() and replace_{max, min}() still need to be replaced with versions using peek_{min, max}_mut() to avoid bounds checks. I implemented this in my previous PR: #8.) This significantly improves performance, as the compiler avoids branch instructions, outputs less code, and is able to inline the functions completely.

Before:

test pop_max_seq ... bench:      69,594 ns/iter (+/- 9,316)
test pop_min_seq ... bench:      86,875 ns/iter (+/- 2,483)
test push_seq    ... bench:      22,185 ns/iter (+/- 1,641)

After:

test pop_max_seq ... bench:      64,055 ns/iter (+/- 5,473)
test pop_min_seq ... bench:      86,439 ns/iter (+/- 2,132)
test push_seq    ... bench:      15,420 ns/iter (+/- 2,914)
opened Sep 11, 2020 by calebsander 3
Open

Consider adding maintainers

Hey @tov,

Thank you for your work on this crate. It's a very useful data structure.

There are a few long-standing PRs from contributors which I believe would really improve things toward making it "production ready". I understand maintaining an open-source project is not an easy task and that's why I'm proposing you consider making a call for maintainers.

I know @calebsander made good improvements already. I've been considering using it myself for a while now so I might be able to review PRs too.

Thanks again!

opened Dec 17, 2021 by fbernier 3

Contents

    skarupke Looking into the performance of heaps, starting with the Min-Max Heap
    phoe A heap-based priority queue whose first and foremost priority is speed.
    limen Queue, Stack and Priority Queue built on Redis.
    zmitton Priority Queue on Ethereum
    mourner A very fast and simple JavaScript priority queue
    garro95 A priority queue for Rust with efficient change function.
    makasim Use php-fpm as a simple built-in async queue
    zzggbb a script that outputs randomly colored and sized blocks.
    Cycling74 Materials for the ADC 2021 workshop "Getting Max Out of Max with gen~"
    luciopaiva The fastest JavaScript priority queue out there. Zero dependencies.
    cmseaton42 A simple, customizable, and lightweight priority queue for promises.
    okready scratchpad - Stack-like memory allocator with double-ended allocation support
    taskflow A fast work-stealing queue template in C++
    rr RR is a test double framework that features a rich selection of double techniques and a terse syntax. ⛺
    seiflotfy Go implementation of Count-Min-Log
    joyeecheung Port of the automatic leak detection in Memory Analyzer for V8 heap snapshots
    remeh Diago is a visualization tool for CPU profiles and heap snapshots generated with `pprof`.
    Automattic Kue is a priority job queue backed by redis, built for node.js.
    davecom A Generic Priority Queue in Pure Swift
    jshvarts Sample Offline-First MVVM app that uses Android Priority Job Queue, Room, Retrofit2, LiveData, LifecycleObserver, RxJava2, Dagger Android
    zfq559 priority queue use ring buffer for c++, fixed length
    Share this repo

    Related Repos


    Data structures
    265
    A minimal `syn` syntax tree pretty-printer
    dtolnay prettyplease::unparse A minimal syn syntax tree pretty-printer. Overview This is a pretty-printer to turn a syn syntax tree into a String of well-form
     
    Data structures
    4
    A memory efficient syntax tree for language developers
    udoprog syntree A memory efficient syntax tree. This crate provides a tree structure which always is contiguously stored and manipulated in memory. It provide
     
    Data structures
    8
    Rust library providing fast language model queries in compressed space
    kampersanda tongrams-rs: Tons of N-grams in Rust This is a Rust port of tongrams to index and query large language models in compressed space, in which the data s
     
    Data structures
    5
    Traversal of tree-sitter Trees and any arbitrary tree with a TreeCursor-like interface
    skmendez tree-sitter-traversal Traversal of tree-sitter Trees and any arbitrary tree with a TreeCursor-like interface. Using cursors, iteration over the tree c
     
    Data structures
    3
    A tiny rusty Xmas tree without bells and whistles
    lmammino xmas A tiny rusty Xmas tree without bells and whistles Run Just clone this repo and run: cargo run (Requires to have Rust installed) Contributing Ever
     
    Data structures
    33
    A LED Christmas Tree controlled by Rust. Contribute your own renderers!
    AngelOnFira Rusty Christmas Tree This is code that draws on the LED Christmas Tree made by @aidancrowther. You can see his 3D design files and Pi Pico setup code
     
    Data structures
    3
    A syntax highlighter for Node powered by Tree Sitter. Written in Rust.
    devongovett tree-sitter-highlight A syntax highlighter for Node.js powered by Tree Sitter. Usage The following will output HTML: const treeSitter = require('tree-
     
    Data structures
    229
    Tree command, improved.
    dduan tre A modern alternative to the tree command that: lists directory structure in a tree-like diagram, like the classics. skips ignored files in git rep
     
    Data structures
    12
    Serialize & deserialize device tree binary using serde
    luojia65 serde_device_tree Use serde framework to deserialize Device Tree Blob binary files; no_std compatible. Use this library Run example: cargo run --examp
     
    Data structures
    10
    StdFuzzer is the reference implementation of a generic bit-level fuzzer with LibAFL
    AFLplusplus StdFuzzer StdFuzzer is the reference implementation of a generic bit-level fuzzer with LibAFL Building Build with $ cargo build --release Compiling a
     
    Data structures
    9
    Rasterization using compute shaders
    pudnax gpu_compute_rasterizer This is a basic implementation of a rasterizer using compute shaders and wgpu. Based on: https://github.com/OmarShehata/webgpu-
     
    Data structures
    3
    A "cursed" container with opaque keys, usable as a static variable
    u1f408 cursedcontainer Please, for the love of all things good in the world, do not use this crate unless you've read the code thoroughly and understand the
     
    Data structures
    3
    Voluntarily contributed solutions for the first practical exercise for the Compilerbau lec...
    Yandrik Solutions for the first practical exercise Compilerbau lecture WiSe 2021/2022 - Ulm University Contributing Want to add your solution? Great! Just add
     
    Data structures
    12
    Common data structures and algorithms for competitive programming in Rust
    utilForever algorithm-rs algorithm-rs is common data structures and algorithms for competitive programming in Rust. Contents TBA How To Contribute Contributions a
     
    Data structures
    1.4k
    Rust implementations of algorithms and data structures useful for bioinformatics.
    rust-bio This library provides implementations of many algorithms and data structures that are useful for bioinformatics. All provided implementations are rigorously tested via continuous integration.