Aleph-w  1.9
General library for algorithms and data structures
Public Types | Public Member Functions | Protected Member Functions | Static Protected Member Functions | Protected Attributes | List of all members
Aleph::BinHeap< Key, Compare > Struct Template Reference
Trees

#include <tpl_binHeap.H>

+ Inheritance diagram for Aleph::BinHeap< Key, Compare >:
+ Collaboration diagram for Aleph::BinHeap< Key, Compare >:

Public Types

using Node = BinHeapNode< Key >
 El tipo de nodo del heap.
 

Public Member Functions

Compare & key_comp () noexcept
 
Compare & get_compare () noexcept
 
void swap (GenBinHeap &h) noexcept
 
Node * getRoot () noexcept
 
Node * getRoot () const noexcept
 
bool preorder_traverse (Operation op) const noexcept(noexcept(op))
 
void for_each_in_preorder (Operation &operation) const
 
void for_each_in_preorder (Operation &&operation=Operation()) const
 
void for_each_in_inorder (Operation &operation) const
 
void for_each_in_inorder (Operation &&operation=Operation()) const
 
bool level_traverse (Op operation=Op()) const
 
Node * insert (Node *p) noexcept
 
Node * getMin_ne () noexcept
 
Node * getMin ()
 
Node * getMax ()
 
void update (Node *p) noexcept
 
Node * remove (Node *node)
 
void remove_all_and_delete () noexcept
 
Node * top ()
 
const size_t & size () const noexcept
 Retorna la cardinalidad del heap.
 
bool is_empty () const noexcept
 Retorna true si el heap está vacío.
 
bool verify_heap () const
 

Protected Member Functions

virtual bool verify_heap (Node *p) const
 

Static Protected Member Functions

static Node * advance_left (Node *p) noexcept
 
static Node * advance_right (Node *p) noexcept
 

Protected Attributes

Compare cmp
 

Detailed Description

template<class Key, typename Compare = Aleph::less<Key>>
struct Aleph::BinHeap< Key, Compare >

Heap de nodos sin destructor virtual.

La clase BinHeap instrumenta un heap de nodos. Este heap no está implementado mediante un arreglo, sino con un árbol binario. Esto proporciona la gran ventaja de ser altamente dinámico. La memoria empleada es pues proporcional a la cantidad de nodos del heap.

Parameters
Keyla clave que guarda cada nodo.
Compareel criterio de comparación entre las claves de los nodos; por omisión es la relación "menor que".
See also
BinHeapVtl DynBinHeap

Member Function Documentation

◆ getMax()

Node* Aleph::GenBinHeap< BinHeapNode , Key, Compare >::getMax ( )
inlineinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ getMin()

Node* Aleph::GenBinHeap< BinHeapNode , Key, Compare >::getMin ( )
inlineinherited

Elimina del heap el nodo de menor prioridad.

getMIn() extrae del heap this el nodo que contenga el menor valor de prioridad según el criterio de comparación definido en la declaración.

Returns
puntero al nodo eliminado.
Exceptions
underflow_errorsi el heap está vacío.

◆ insert()

Node* Aleph::GenBinHeap< BinHeapNode , Key, Compare >::insert ( Node *  p)
inlinenoexceptinherited

Inserta un nodo en un heap.

insert(p) inserta en el heap this el nodo p.

Parameters
[in]pel nodo a insertar.
Returns
puntero al nodo insertado.

◆ remove()

Node* Aleph::GenBinHeap< BinHeapNode , Key, Compare >::remove ( Node *  node)
inlineinherited

Elimina del heap el nodo node.

remove(node) elimina del heap el nodo node.

Parameters
[in]nodepuntero al nodo a eliminar.
Exceptions
underflow_errorsi el heap está vacío
Returns
puntero al nodo eliminado
Note
No se verifica si node pertenece al heap.

◆ remove_all_and_delete()

void Aleph::GenBinHeap< BinHeapNode , Key, Compare >::remove_all_and_delete ( )
inlinenoexceptinherited

Borra todos los nodos del heap, invoca a los destructores de los nodos eliminados y libera toda la memoria

◆ top()

Node* Aleph::GenBinHeap< BinHeapNode , Key, Compare >::top ( )
inlineinherited

Retorna el nodo con menor prioridad según el criterio de comparación especificado en la declaración.

◆ update()

void Aleph::GenBinHeap< BinHeapNode , Key, Compare >::update ( Node *  p)
inlinenoexceptinherited

Actualiza prioridad de un nodo contenido en el heap.

update(p) toma un nodo del heap cuya prioridad haya sido modificada y actualiza su prioridad dentro del heap. La idea es que si por alguna razón una prioridad debe ser modificada, entonces el orden de extracción pueda actualizarse.

Parameters
[in]ppuntero al nodo que se desea actualizar
See also
insert()
The documentation for this struct was generated from the following file:
Leandro Rabindranath León