The Complete Rust Programming Reference Guide

Heaps

Since binary trees are the most basic forms of trees, there are several variations designed for a specific purpose. Where the red-black tree is an advanced version of the initial tree, the binary heap is a version of the binary tree that does not facilitate search.

In fact, it has a specified purpose: finding the maximum or minimum value of a node. These heaps (min-heap or max-heap) are built in a way that the root node is always the value with the desired property (min or max) so it can be retrieved in constant time—that is, it always takes the same number of operations to fetch. Once fetched, the tree is restored in a way that the next operation works the same. How is this done though?

Heaps work, irrespective of whether they are ...