Struct Heap

pub struct Heap<V>
where
    V: Cmov + Pod,
{
    pub data: CircuitORAM<HeapElement<V>>,
    pub metadata: HeapTree<Block<HeapElement<V>>>,
    pub rng: ThreadRng,
    pub max_size: usize,
    pub timestamp: K,
}

An oblivious heap. Elements are stored in an ORAM, along with information about the location of the minimum element in each subtree.

Invariants

• metadata stores the minimum element in each subtree.
• Heap elements are stored in a non-recursive ORAM.
• After insertion, the oram key (timestamp) and path for an element do not change.

Fields

data: CircuitORAM<HeapElement<V>>

The heap elements.

metadata: HeapTree<Block<HeapElement<V>>>

The metadata tree used for storing the element with minimum key in the subtree.

rng: ThreadRng

Thread local rng.

max_size: usize

maximum size of the heap.

timestamp: K

timestamp: usize,

Implementations

impl<V> Heap<V>

where V: Cmov + Pod + Debug,

pub fn new(n: usize) -> Self

Creates a Heap with maximum size of n elements.

pub fn find_min(&self) -> Block<HeapElement<V>>

Finds the minimum element in the heap.

Returns

• The minimum element in the heap. => if the heap is non-empty.
• A HeapElement<V> with pos = DUMMY => if the heap is empty.

pub fn insert(&mut self, key: K, value: V) -> (PositionType, K)

Inserts a new element value with priority key into the heap.

Returns

• the position and timestamp of the inserted element.

pub fn delete(&mut self, pos: PositionType, timestamp: K)

Deletes an element from the heap given it’s timestamp and path.

Behavior

• If the element is not in the heap, nothing happens.

pub fn extract_min(&mut self)

Find and delete the minimum element from the heap.

Trait Implementations

impl<V> Debug for Heap<V>

where V: Cmov + Pod + Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.