Class: DHeap::Map

Inherits:

DHeap

• Object
• DHeap
• DHeap::Map

Defined in:

lib/d_heap.rb,
ext/d_heap/d_heap.c

Overview

Unlike DHeap, an object can only be added into a Map once. Any subsequent addition simply rescores the already existing member. Objects are identified by their #hash value, just like with Hash.

Instance Method Summary

• #[](object) ⇒ Float, ... (also: #score)

  Retrieves the score that has been assigned to a heap member.

• #[]=(object, score) ⇒ Float, Integer (also: #rescore, #update)

  Assign a score to an object, adding it to the heap or updating as necessary.

• #initialize(d: DEFAULT_D, capacity: DEFAULT_CAPA) ⇒ Map constructor

  Initialize a d-ary min-heap which can map objects to scores.

Constructor Details

#initialize(d: DEFAULT_D, capacity: DEFAULT_CAPA) ⇒ Map

Initialize a d-ary min-heap which can map objects to scores.

Parameters:

• d (Integer) (defaults to: DEFAULT_D) —

  Number of children for each parent node. Higher values generally speed up push but slow down pop. If all pushes are popped, the default is probably best.

• capacity (Integer) (defaults to: DEFAULT_CAPA) —

  initial capacity of the heap.

# File 'lib/d_heap.rb', line 127

def initialize(d: DEFAULT_D, capacity: DEFAULT_CAPA) # rubocop:disable Naming/MethodParameterName
  __init_without_kw__(d, capacity, true)
end

Instance Method Details

#[](object) ⇒ Float, ... Also known as: score

Retrieves the score that has been assigned to a heap member.

Time complexity: O(1)

Parameters:

• object (Object) —

  an object to lookup

Returns:

• (Float, Integer, nil) —

  the score associated with the object, or nil if the object isn’t a member

# File 'ext/d_heap/d_heap.c', line 998

static VALUE
dheapmap_aref(VALUE self, VALUE object)
{
    dheap_t *heap   = get_dheap_struct(self);
    VALUE    idxval = rb_hash_lookup2(heap->indexes, object, Qfalse);
    if (idxval) {
        size_t index = NUM2ULONG(idxval);
        return SCORE2NUM(DHEAP_SCORE(heap, index));
    }
    return Qnil;
}

#[]=(object, score) ⇒ Float, Integer Also known as: rescore, update

Assign a score to an object, adding it to the heap or updating as necessary.

Time complexity: O(log n) (score decrease will be faster than score increase)

Parameters:

• object (Object) —

  an object to lookup

• score (Integer, #to_f) —

  the score to set

Returns:

• (Float, Integer) —

  the score

# File 'ext/d_heap/d_heap.c', line 1020

static VALUE
dheapmap_aset(VALUE self, VALUE object, VALUE score)
{
    dheapmap_insert(self, score, object);
    return score;
}