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 worst-case O(1) time. A removal of either extreme, or an insertion, is worst-case O(log n) time.

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.46 and later.

• M. D. Atkinson, J.-R. Sack, N. Santoro, and T. Strothot. Ian Munro (ed.). “Min-Max Heaps and Generalized Priority Queues.” In Communications of the ACM. 29(10): 996–1000, June 1996. [pdf]

• The Rust Standard Library’s BinaryHeap API and implementation. [src]