Heap

Library for managing https://en.wikipedia.org/wiki/Binary_heap[binary heap] that can be used as https://en.wikipedia.org/wiki/Priority_queue[priority queue]. Heaps are represented as a tree of values where the first element (index 0) is the root, and where the node at index i is the child of the node at index (i-1)/2 and the parent of nodes at index 2i+1 and 2i+2. Each node stores an element of the heap. The structure is ordered so that each node is bigger than its parent. An immediate consequence is that the highest priority value is the one at the root. This value can be looked up in constant time (O(1)) at heap.tree[0] The structure is designed to perform the following operations with the corresponding complexities: peek (get the highest priority value): O(1) insert (insert a value): O(log(n)) pop (remove the highest priority value): O(log(n)) replace (replace the highest priority value with a new value): O(log(n)) length (get the number of elements): O(1) clear (remove all elements): O(1) IMPORTANT: This library allows for the use of custom comparator functions. Given that manipulating memory can lead to unexpected behavior. Consider verifying that the comparator does not manipulate the Heap's state directly and that it follows the Solidity memory safety rules. Available since v5.1.

Functions

peek

Lookup the root element of the heap.

function peek(Uint256Heap storage self) internal view returns (uint256);

pop

Remove (and return) the root element for the heap using the default comparator. NOTE: All inserting and removal from a heap should always be done using the same comparator. Mixing comparator during the lifecycle of a heap will result in undefined behavior.

function pop(Uint256Heap storage self) internal returns (uint256);

pop

Remove (and return) the root element for the heap using the provided comparator. NOTE: All inserting and removal from a heap should always be done using the same comparator. Mixing comparator during the lifecycle of a heap will result in undefined behavior.

function pop(Uint256Heap storage self, function(uint256, uint256) view returns (bool) comp)
    internal
    returns (uint256);

insert

Insert a new element in the heap using the default comparator. NOTE: All inserting and removal from a heap should always be done using the same comparator. Mixing comparator during the lifecycle of a heap will result in undefined behavior.

function insert(Uint256Heap storage self, uint256 value) internal;

insert

Insert a new element in the heap using the provided comparator. NOTE: All inserting and removal from a heap should always be done using the same comparator. Mixing comparator during the lifecycle of a heap will result in undefined behavior.

function insert(Uint256Heap storage self, uint256 value, function(uint256, uint256) view returns (bool) comp)
    internal;

replace

Return the root element for the heap, and replace it with a new value, using the default comparator. This is equivalent to using pop and {insert}, but requires only one rebalancing operation. NOTE: All inserting and removal from a heap should always be done using the same comparator. Mixing comparator during the lifecycle of a heap will result in undefined behavior.

function replace(Uint256Heap storage self, uint256 newValue) internal returns (uint256);

replace

Return the root element for the heap, and replace it with a new value, using the provided comparator. This is equivalent to using pop and {insert}, but requires only one rebalancing operation. NOTE: All inserting and removal from a heap should always be done using the same comparator. Mixing comparator during the lifecycle of a heap will result in undefined behavior.

function replace(Uint256Heap storage self, uint256 newValue, function(uint256, uint256) view returns (bool) comp)
    internal
    returns (uint256);

length

Returns the number of elements in the heap.

function length(Uint256Heap storage self) internal view returns (uint256);

clear

Removes all elements in the heap.

function clear(Uint256Heap storage self) internal;

_swap

Swap node i and j in the tree.

function _swap(Uint256Heap storage self, uint256 i, uint256 j) private;

_siftDown

Perform heap maintenance on self, starting at index (with the value), using comp as a comparator, and moving toward the leaves of the underlying tree. NOTE: This is a private function that is called in a trusted context with already cached parameters. size and value could be extracted from self and index, but that would require redundant storage read. These parameters are not verified. It is the caller role to make sure the parameters are correct.

function _siftDown(
    Uint256Heap storage self,
    uint256 size,
    uint256 index,
    uint256 value,
    function(uint256, uint256) view returns (bool) comp
) private;

_siftUp

Perform heap maintenance on self, starting at index (with the value), using comp as a comparator, and moving toward the root of the underlying tree. NOTE: This is a private function that is called in a trusted context with already cached parameters. value could be extracted from self and index, but that would require redundant storage read. These parameters are not verified. It is the caller role to make sure the parameters are correct.

function _siftUp(
    Uint256Heap storage self,
    uint256 index,
    uint256 value,
    function(uint256, uint256) view returns (bool) comp
) private;

Structs

Uint256Heap

Binary heap that supports values of type uint256. Each element of that structure uses one storage slot.

struct Uint256Heap {
    uint256[] tree;
}

Keyboard shortcuts