BinaryHeap - rust-course

The BinaryHeap structure is a max-heap. This type of binary heap is used for priority queues, since the maximum value is always at the root. Popping out the max (i.e.: the root element), re-arrange the heap so a new maximum is set at the root. See Program 1 for an illustration. The property of a max-heap is that each parent must be greater than its direct children. When inserting a value, it is placed in the first available place and then moved up until to satisfy the property.

The time complexity of a max-heap is roughly as following:

Getting the max value is 𝒪(1).
Popping out the max value is 𝒪( $\log(n)$ ).
Inserting a new value is 𝒪( $\log(n)$ ).
Building a new heap from a list of unordered values is 𝒪( $n$ ).

                   ┌──┐
                   │98│
                   └──┘
                  ╱    ╲
                 ╱      ╲
             ┌──┐        ┌──┐
             │41│        │76│
             └──┘        └──┘
             ╱   ╲      ╱    ╲
         ┌──┐    ┌──┐ ┌──┐  ┌──┐
         │23│    │11│ │33│  │56│
         └──┘    └──┘ └──┘  └──┘
        ╱    ╲       ╱    ╲
    ┌──┐     ┌──┐  ┌──┐  ┌──┐
    │ 5│     │10│  │25│  │17│
    └──┘     └──┘  └──┘  └──┘

Program 1:An example of a max heap

The main methods of the BinaryHeap are presented in Table 1.

Table 1:Some methods of BinaryHeap

Method	Description
`append(&other)`	Moves the elements of another heap into this heap.
`clear()`	Removes all elements.
`is_empty()`	Returns `true` if this set contains no elements.
`into_vec()`	Consumes all the items and returns the underlying vector. Order of items is arbitrary.
`iter()`	Returns an iterator over all values. Order is undefined.
`len()`	Returns the number of elements.
`new()`	Creates a new binary heap.
`peek()`	Returns a reference to the greatest item.
`pop()`	Removes and returns the greatest item.
`push(v)`	Pushes a new value.

29.3.1Creating a new instance¶

To create a new binary heap BinaryHeap<V>, an easy way, like for the Vec type, is to let the compiler infer the type. Inserting at least one value will give the compiler the information it needs:

use std::collections::BinaryHeap;

let mut values = BinaryHeap::new();
values.push(10);
values.push(24);
values

Couldn't automatically determine type of variable `values`.
Please give it an explicit type.

Note that objects moved into the set are either copied or moved, depending on their type.

A BinaryHeap may also be created from a vector or an array:

let mut other_values = BinaryHeap::from([50, 4, 73, 87, 56, 33, 15]);
other_values

29.3.2Merging two heaps¶

Using the append() method, we can move all the items of a heap into another:

values.append(&mut other_values);
values

29.3.3Max value¶

The max value is at the root node. To look at it we use the peek() method:

values.peek()

If we remove it with pop():

values.pop()

The heap is re-arranged:

values

29.3 BinaryHeap

29.3.1Creating a new instance¶

29.3.2Merging two heaps¶

29.3.3Max value¶