File pairing_queue.hpp

Defines

nullval

max_P

namespace pairing_queue

template <typename P>
class pairing_queuepairing_queue

#include <pairing_queue.hpp>

A priority queue based on a pairing heap, with fixed memory footprint and support for a decrease-key operation.

Subclassed by pairing_queue::pairing_queue_fast_reset< P >

Public Types

typedef P pairing_queue::pairing_queuevalue_type

Public Functions

pairing_queue::pairing_queuepairing_queue(int n)

void pairing_queue::pairing_queuereset_fill(const P &v)

Reset the queue and fill the values with a default.

bool pairing_queue::pairing_queuehas(int index) const

void pairing_queue::pairing_queuereset()

Reset the queue and set the default to the maximum value.

bool pairing_queue::pairing_queuedelete_min()

Remove the minimum value return true if any change is made.

bool pairing_queue::pairing_queuepop_min(int &key, P &value)

Remove and return (in args) the minimum key, value pair.

void pairing_queue::pairing_queuedecrease_value(int k, const P &v)

Decrease the value of k to v NOTE: Assumes that v is lower than the current value of k.

bool pairing_queue::pairing_queuecheck_decrease_value(int k, const P &v)

Decrease the value of k to v Does nothing if v isn’t actually a decrease.

void pairing_queue::pairing_queueset_value(int k, const P &v)

void pairing_queue::pairing_queueset_value_unsafe(int k, const P &v)

P pairing_queue::pairing_queuemin_value() const

int pairing_queue::pairing_queuemin_key() const

bool pairing_queue::pairing_queueempty(void) const

bool pairing_queue::pairing_queueempty(int k) const

P pairing_queue::pairing_queuevalue(int k) const

Protected Functions

int pairing_queue::pairing_queuemerge_roots(int a, int b)

int pairing_queue::pairing_queuemerge_roots_unsafe(int a, int b)

int pairing_queue::pairing_queuemerge_roots_unchecked(int a, int b)

int pairing_queue::pairing_queuemerge_pairs(int a)

void pairing_queue::pairing_queueremove(int a)

void pairing_queue::pairing_queuedecrease(int a)

Protected Attributes

vector<P> pairing_queue::pairing_queueval

vector<int> pairing_queue::pairing_queuenext

vector<int> pairing_queue::pairing_queuedesc

vector<int> pairing_queue::pairing_queueprev

int pairing_queue::pairing_queueroot

template <typename P>
class pairing_queuepairing_queue_fast_reset : public pairing_queue::pairing_queue<P>

#include <pairing_queue.hpp>

This is a specialization of the pairing_queue that has a constant time reset method, at the expense of an extra check when values are set or updated.

Public Functions

pairing_queue::pairing_queue_fast_resetpairing_queue_fast_reset(int n)

void pairing_queue::pairing_queue_fast_resetreset()

void pairing_queue::pairing_queue_fast_resetset_value_unsafe(int k, const P &v)

void pairing_queue::pairing_queue_fast_resetset_value(int k, const P &v)

bool pairing_queue::pairing_queue_fast_resetcheck_decrease_value(int k, const P &v)

P pairing_queue::pairing_queue_fast_resetget_value(int k) const

Private Types

template<>
using pairing_queue::pairing_queue_fast_reset<P>super = pairing_queue<P>

Private Functions

bool pairing_queue::pairing_queue_fast_resetcurrent(int k)

Private Members

vector<int> pairing_queue::pairing_queue_fast_resettime

int pairing_queue::pairing_queue_fast_resetnow