/
Inicio :: Foros

 F.A.Q.F.A.Q.                  Conéctese para revisar sus mensajesConéctese para revisar sus mensajes   

Implementación funciones para un minmax_heap

 
      Índice del Foro elrincondelc.com -> Algoritmos
Ver tema anterior :: Ver siguiente tema  
AutorMensaje
Pantalàimon_



Registrado: 17 Jul 2007
Mensajes: 961

MensajePublicado: 07/02/2011 5:00 am
Título: Implementación funciones para un minmax_heap
Buenas.

Os dejo las funciones para manipular un minmax_heap implementadas sobre un vector. Me ha parecido curiosa esta estructura de datos pues puedes crearla en un tiempo lineal. Y, una vez creada, puedes extraer el minimo o el máximo, o poner un elemento en una complejidad logaritmica en el caso peor. También puedes obtener el minimo y el máximo en tiempo constante. Y todo usando una estructura sencilla como la de un vector.

minmax_heap:
Código:
#include<cmath>
#include<algorithm>
#include<vector>

#ifndef _MINMAX_HEAP_
   #define _MINMAX_HEAP_

// n == v.size()
template< typename T >
void make_minmax_heap( std::vector<T>& v ); // o(n)
template< typename T >
void pop_min_heap( std::vector<T>& v );     // o(log n)
template< typename T >
void pop_max_heap( std::vector<T>& v );     // o(log n)
template< typename T >
void push_minmax_heap( std::vector<T>& v, const T& dat ); // o(log n)
template< typename T >
const T& get_min_heap( const std::vector<T>& v ); // o(1)
template< typename T >
const T& get_max_heap( const std::vector<T>& v ); // o(1)

namespace  // anónimo
{
   template< typename T >
   void reset( const int& pos, const typename std::vector<T>::iterator& it, const int& n );
   template< typename T >
   void sink( int i, int pos, const typename std::vector<T>::iterator& it, const int& n );
   template< typename T >
   void swim( int i, const int& pos, const typename std::vector<T>::iterator& it, const int& n );
}

template< typename T >
void make_minmax_heap( std::vector<T>& v )
{
   typename std::vector<T>::iterator it = v.begin() - 2;
   int n = v.size() + 2;

   int pos = log(n-1)/M_LN2;
   pos = 1 << pos;

   reset<T>( pos, it, n );

   int m = pos;
   pos /= 2;
   while( pos > 1 )
   {
      int i;
      reset<T>( pos, it, n );

      for( i = pos; i < m; ++i )
         sink<T>( i, pos, it, n );

      m = pos;
      pos /= 2;
   }
}

template< typename T >
void pop_min_heap( std::vector<T>& v )
{
   typename std::vector<T>::iterator it = v.begin() - 2;
   int n = v.size() + 2;

   it[2] = it[n-1];
   sink<T>( 2, 2, it, n );
   v.pop_back();
}

template< typename T >
void pop_max_heap( std::vector<T>& v )
{
   typename std::vector<T>::iterator it = v.begin() - 2;
   int n = v.size() + 2;

   it[3] = it[n-1];
   sink<T>( 3, 2, it, n );
   v.pop_back();
}

template< typename T >
void push_minmax_heap( std::vector<T>& v, const T& dat )
{
   typename std::vector<int>::iterator it = v.begin() - 2;
   int n = v.size() + 2;

   v.push_back(dat);
   int pos = log(n-1) / M_LN2;
   pos = 1 << pos;

   swim<T>( n, pos, it, n );
}

template< typename T >
inline const T& get_min_heap( const std::vector<T>& v )
{
   return v[0];
}

template< typename T >
inline const T& get_max_heap( const std::vector<T>& v )
{
   return v.size() > 1 ? v[1] : v[0];
}

namespace // anónimo
{
   template< typename T >
   void reset( const int& pos, const typename std::vector<T>::iterator& it, const int& n )
   {
      int inc = pos/2;
      int m = pos + inc;
      if( m > n ) m = n;

      for( int i = pos; i < m; ++i )
      {
         // calcular k, hermano de i
         int k = i+inc;
         if( k >= n ) k /= 2;

         // intercambiar si hace falta
         if( it[i] > it[k] ) std::swap( it[i], it[k] );
      }
   }

   template< typename T >
   void sink( int i, int pos, const typename std::vector<T>::iterator& it, const int& n )
   {
      int j = 2*i;
      int k;

      while( j < n )
      {
         k = j + 1;

         if( j & pos ) //está en el maxheap
         {
            if( k < n && it[j] < it[k] ) j++;
            if( it[i] < it[j] )
            {
               std::swap( it[i], it[j] );

               k = j - pos;
               if( it[k] > it[j] ) std::swap( it[j] , it[k] );

               // caso especial si j tiene más de 1 hermano en minheap
               int a = 2*j;
               int b = 2*k;
               if( a >= n && b < n ) k = b;
               b++;
               if( a+1 >= n && b < n && it[b] > it[k] ) k = b;

               if( it[k] > it[j] ) std::swap( it[j], it[k] );
            } 
         }
         else // está en el minheap
         {
            if( k < n && it[j] > it[k] ) j++;
            if( it[i] > it[j] )
            {
               std::swap( it[i], it[j] );

               k = j + pos;
               if( k >= n ) k /= 2;
               if( it[j] > it[k] ) std::swap( it[j], it[k] );
            }
         }

         i = j;
         j = 2*i;
         pos *= 2;
      }
   }

   template< typename T >
   void swim( int i, const int& pos, const typename std::vector<T>::iterator& it, const int& n )
   {
      bool b;
      int j;
      int inc = pos/2;
      if( b = (i & inc) ) // está en maxheap
      {
         j = i - inc;
         if( it[j] > it[i] )
         {
            std::swap( it[j], it[i] );
            i = j;
            b = false;
         }
      }
      else //está en minheap
      {
         j = i + inc;
         if( j >= n ) j /= 2;
         if( it[i] > it[j] )
         {
            std::swap( it[j], it[i] );
            i = j;
            b = true;
         }
      }

      j = i/2;
      if( b )
      {
         while( j > 1 && it[j] < it[i] )
         {
            std::swap( it[j], it[i] );
            i = j;
            j /= 2;
         }
      }
      else
      {
         while( j > 1 && it[j] > it[i] )
         {
            std::swap( it[j], it[i] );
            i = j;
            j /= 2;
         }
      }
   }

}

#endif


Y para testear:
Código:
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<vector>
#include"minmax_heap"

std::vector<int> create_random_vector(const int& n, const int& max);
template< typename T >
std::ostream& operator<<(std::ostream&, const std::vector<T>&);

int main()
{
   int n = 27;
   std::vector<int> v = create_random_vector( n, 50 );

   std::cout << "Antes:" << std::endl;
   std::cout << v << std::endl;

   make_minmax_heap ( v );

   std::cout << "Despues:" << std::endl;
   std::cout << v << std::endl;

   std::cout << "Quitando min:" << std::endl;
   pop_min_heap( v );
   std::cout << v << std::endl;

   std::cout << "Quitando max:" << std::endl;
   pop_max_heap( v );
   std::cout << v << std::endl;

   int num = 1 + std::rand() % 30;
   std::cout << "Poniendo " << num << std::endl;
   push_minmax_heap( v, num );
   std::cout << v << std::endl;

   std::cout << "Actualmente el minimo es " << get_min_heap(v) << " y el maximo es " << get_max_heap(v) << std::endl;

   return 0;
}

std::vector<int> create_random_vector(const int& n, const int& max)
{
   std::vector<int> v(n);
   std::srand( std::time( NULL ) );

   for( int i = 0; i < n; i++ ) v[i] = 1 + std::rand() % max;
   return v;
}


template< typename T >
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v)
{
   int space2 = log( v.size() - 1 )/M_LN2;
   space2 = (1 << space2) - 1;
   int space1 = space2 / 2;

   typename std::vector<T>::const_iterator it = v.begin();
   int nums = 2;

   while( space2 > 0 )
   {
      int i;
      for( i = 0; i < 2*space1; ++i) os.put(' ');

      for( int j = 0; j < (nums - 1); ++j )
      {
         if( it < v.end() )
         {
            os.width(2);
            os << *it;
            ++it;
            for( i = 0; i < 2*space2; ++i ) os.put(' ');
         }
      }
      if( it < v.end() )
      {
         os.width(2);
         os << *it;
         ++it;
      }
      os << std::endl;

      space1 /= 2;
      space2 /= 2;
      nums *= 2;
     
   }

   return os;
}


A poder ser, me gustaría que opinarais sobre si tengo "buenas maneras" en la escritura del código. Pues no quiero coger ningún mal vicio. Por ejemplo, en un hilo reciente tenía dudas sobre que prototipo debía utilizar para las funciones. Pues veía que en las librerias estándar lo hacen de un modo que no he sabido aplicar en este caso. Al final he optado por pasar como argumento a las funciones el mismo vector.

Un saludo y gracias por la ayuda.
Volver arriba
      Índice del Foro elrincondelc.com -> Algoritmos
Página 1 de 1Todas las horas están en GMT - 8 Horas

 
No puede crear mensajes
No puede responder temas
No puede editar sus mensajes
No puede borrar sus mensajes
No puede votar en encuestas
Noticias
Enlaces
Cursos
Código fuente
Articulos
FOROS
Tutor online
Curso de C
Curso de C en PDF
¿Necesitas ayuda con tus trabajos?
Contacto
Boletín Novedades
¿Qué es esto?
Qué se cuece por aquí

(c) ElRincondelC.com

Un proyecto de UrlanHeat.com