0

Mi pregunta es, cómo realizar la implementación de inserción y eliminación de un elemento en un montículo (heap) maximo. (Para la estructura del mismo seria de la siguiente manera)

[Archivo cabecera]

    #ifndef HEAP_H_
    #define HEAP_H_
    #include "node.h"

    class heap { // Implementacion de un heap max (monticulo maximo), mediante un arbol binario.
    public:
        node *root;
        heap();
        virtual ~heap();
        bool empty();
    private:
        struct node{
            node *L, *R;
            node(){
                this->L = NULL;
                this->R = NULL;
            }
        };

    };

#endif /* HEAP_H_ */

[Implementación]

#include "heap.h"

heap::heap() { // Método constructor.
    this->root = NULL;
}

heap::~heap() { // Método destructor.
    delete (this->root);
}

bool heap::empty() { // Verifica si el montículo esta vacio.
    if (root == NULL) {
        return true;
    } else {
        return false;
    }
}
4
  • El motivo por el que dudo en si responderte o no es que esa parte que pides es uno de los núcleos importantes de la práctica... y si te lo doy resuelto no vas a aprender nada al respecto. Otra cosa es que tuvieses una implementación incorrecta y pidieses ayuda para arreglarlo.
    – eferion
    el 18 may. 2017 a las 6:46
  • Hago esta petición porque no tengo material donde guiarme, cualquier respuesta que lleve un enlace con la implementación la tomaría como correcta. el 18 may. 2017 a las 9:15
  • Si la respuesta es las pautas o lo que hay que considerar en el algoritmo, me ayude a construirlo me ayudaria de igual forma. el 18 may. 2017 a las 9:17
  • Entiendo lo que me quieres decir hermano. el 18 may. 2017 a las 9:18

1 respuesta 1

1
template <class T>
class node {
public:
    virtual ~node();
};

Si la clase no va a ser heredable no tiene sentido que el destructor sea virtual. ¿Importa eso? En parte sí. Definir métodos virtuales obliga al compilador a crear una tabla virtual (conocida como vtable) y esto tiene el siguiente impacto:

  • Cada instancia del objeto tendrá un puntero a dicha tabla. El puntero será implícito y tu no tendrás que definirlo... lo hará el compilador por tí. Esto hace que las clases sean un poco más grandes (el tamaño de un puntero) y hay que tener mucho cuidado si se intenta serializar el objeto al estilo C (apuntando al objeto con un puntero de tipo char).
  • Al invocar a una llamada virtual la misma no podrá ser llamada de forma directa sino que habrá que acudir a la vtable, lo que añade un nivel de indirección y su correspondiente coste (que puede ser despreciable o no).
  • Al crear la vtable se habilitan los mecanismos RTTI para esta clase (por ejemplo dynamic_cast). Que estos mecanismos permanezcan deshabilitados para clases no heredables ayuda a evitar que la gente meta la pata con las conversiones (se produce un error de compilación).

Por otro lado, si todos los miembros de la clase son públicos queda más limpi y bonito definir una estructura (cuya visibilidad por defecto es public):

template <class T>
struct node {
    node<T> *L, *R;
    T date;
    node(T date);
    ~node();
};

Seguimos:

template <class T>
node<T>::~node() {
    delete (this->L);
    delete (this->R);
}

La clase node pretende ser el eslabon base de una lista doblemente enlazada. Supongamos entonces que tenemos 2 elementos en dicha lista, A y B, tal que:

NULL <-- A <--> B --> NULL

¿Qué sucede si destruimos A? Viendo el destructor, A invocará al destructor de B... ¿Y qué hace el destructor de B? Intentará destruir A... nuevamente. Doble delete = error en tiempo de ejecución.

Este error lo puedes tratar de varias formas y cada una tiene sus implicaciones. Quizás lo más sencillo sea que cada nodo se preocupe únicamente de sí mismo y se olvide de sus vecinos... para eso ya tienes la clase max_heap:

template <class T>
node<T>::~node() {
}

Más cosas:

template <class T>
node<T>::node(T date) {

Esta parte es un poco de traca... estás creando una plantilla para almacenar cualquier elemento en la misma... ¿y la variable que almacena dicho valor se llama date? Y si lo que quiero almacenar son enteros. ¿tiene sentido que tenga que hacer int valor = nodo->date? te dejo a ti responder a la pregunta.

Una vez visto esto, ¿Cómo añadir un elemento a la lista?

void insert(T date)
{
}

Bueno, lo primero que habría que comprobar es si la lista está vacía, es decir, si root==0. Si es así la operativa es sencilla: Crear un nuevo nodo en root:

node<T>* nuevo = new node<T>(date); // en serio, cambia el nombre de esta 
if( root == 0 )
  root = nuevo;
else
{
}

Si root no es nulo entonces hay que buscar un sitio donde añadir el nuevo elemento. ¿Cual es su sitio? Dependerá de la naturaleza de la lista:

  • Si la lista no es ordenada lo normal es añadir el nuevo elemento al final de la lista... aunque también podría ser al principio
  • Si la lista es ordenada habrá que recorrer la lista para encontrar la posición a añadir el elemento en base a una función de comparación.

Voy a asumir que el elemento se añade al final de la lista:

node<T>* prev = root;
while( prev->R ) prev = prev->R;

prev->R = nuevo;
nuevo->P = prev;

¿Y para sacar un elemento de la lista? El proceso es similar. Primero tienes que buscar el elemento y después hacer que el nodo anterior y siguiente se apunten entre sí:

for( nodo<T>* nodo = root; nodo != 0; nodo=nodo->R )
{
  if( nodo->date == date )
  {
    if( nodo == root )
      root = nodo->P;

    if( nodo->R )
      nodo->R->P = nodo->P;
    if( nodo->P )
      nodo->P->R = nodo->R;

    delete nodo;
    break;
  }
}
2
  • Gracias por la explicacion tan específica que me diste del tema, pero hermano disculpa por no ser específico, la estructura a la cual me refiero es esta: tutorialspoint.com/data_structures_algorithms/… el 18 may. 2017 a las 20:08
  • Agradezco el tiempo que tomaste, tus comentarios de mi código los considerare. el 18 may. 2017 a las 20:12

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.