### 1 unstable release

0.1.0 | May 14, 2022 |
---|

#**977** in Data structures

**MIT**license

71KB

1.5K
SLoC

# Bi-parental heap

## Description

A priority queue implemented with a bi-parental heap.

Beap (bi-parental heap) is an
implict data structure
which allows efficient insertion and searching of elements, requiring low (*O*(1)) overhead.

Insertion and popping the largest element have *O*(sqrt(*2n*)) time complexity.
Checking the largest element is *O*(1). Converting a vector to a beap
can be done by using sorting, and has *O*(nlog(*n*)) time complexity.
Despite the insertion and popping operations that are slower compared to the classical binary heap,
the bi-parental heap has an important advantage:
searching and removing an arbitrary element, as well as finding the minimum,
have the asymptotics *O*(sqrt(*2n*),) while the binary heap has *O*(*n*).

This create presents an implementation of the bi-parental heap -

,
which has an identical interface with `Beap`

from `BinaryHeap`

,
and at the same time it has several new useful methods.`std ::`collections

# Read about bi-parental heap:

## Usage

As a library

`use` `beap``::`Beap`;`
`//` Type inference lets us omit an explicit type signature (which
`//` would be `Beap<i32>` in this example).
`let` `mut` beap `=` `Beap``::`new`(``)``;`
`//` We can use peek to look at the next item in the beap. In this case,
`//` there's no items in there yet so we get None.
`assert_eq!``(`beap`.``peek``(``)``,` `None``)``;`
`//` Let's add some scores...
beap`.``push``(``1``)``;`
beap`.``push``(``5``)``;`
beap`.``push``(``2``)``;`
`//` Now peek shows the most important item in the beap.
`assert_eq!``(`beap`.``peek``(``)``,` `Some``(``&``5``)``)``;`
`//` We can check the length of a beap.
`assert_eq!``(`beap`.``len``(``)``,` `3``)``;`
`//` We can iterate over the items in the beap, although they are returned in
`//` a random order.
`for` x `in` beap`.``iter``(``)` `{`
`println!``(``"``{}``"``,` x`)``;`
`}`
`//` If we instead pop these scores, they should come back in order.
`assert_eq!``(`beap`.``pop``(``)``,` `Some``(``5``)``)``;`
`assert_eq!``(`beap`.``pop``(``)``,` `Some``(``2``)``)``;`
`assert_eq!``(`beap`.``pop``(``)``,` `Some``(``1``)``)``;`
`assert_eq!``(`beap`.``pop``(``)``,` `None``)``;`
`//` We can clear the beap of any remaining items.
beap`.``clear``(``)``;`
`//` The beap should now be empty.
`assert!``(`beap`.``is_empty``(``)``)`

A

with a known list of items can be initialized from an array:`Beap`

`use` `beap``::`Beap`;`
`let` beap `=` `Beap``::`from`(``[``1``,` `5``,` `2``]``)``;`

## Min-heap

Either

or a custom `core ::`

`cmp`Reverse

`::``Ord`

implementation can be used to
make `Beap`

a min-heap. This makes `beap``.``pop``(``)`

return the smallest
value instead of the greatest one.`use` `beap``::`Beap`;`
`use` `std``::``cmp``::`Reverse`;`
`let` `mut` beap `=` `Beap``::`new`(``)``;`
`//` Wrap values in `Reverse`
beap`.``push``(`Reverse`(``1``)``)``;`
beap`.``push``(`Reverse`(``5``)``)``;`
beap`.``push``(`Reverse`(``2``)``)``;`
`//` If we pop these scores now, they should come back in the reverse order.
`assert_eq!``(`beap`.``pop``(``)``,` `Some``(`Reverse`(``1``)``)``)``;`
`assert_eq!``(`beap`.``pop``(``)``,` `Some``(`Reverse`(``2``)``)``)``;`
`assert_eq!``(`beap`.``pop``(``)``,` `Some``(`Reverse`(``5``)``)``)``;`
`assert_eq!``(`beap`.``pop``(``)``,` `None``)``;`

## Sorting

`use` `beap``::`Beap`;`
`let` beap `=` `Beap``::`from`(``[``5``,` `3``,` `1``,` `7``]``)``;`
`assert_eq!``(`beap`.``into_sorted_vec``(``)``,` `vec!``[``1``,` `3``,` `5``,` `7``]``)``;`

If you have any comments or suggestions, or you suddenly found an error, please start a new issue or pool request.