Heapsort.cpp

#include <stdexcept>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <sys/time.h>
using namespace std;

#define izquierda(nodo) (nodo+nodo+1)
#define derecha(nodo) (nodo+nodo+2)
#define padre(nodo) ((nodo-1)>>1)

class NodoInexistenteException : public std::logic_error {
    public:
    NodoInexistenteException() : logic_error("No existe tal nodo.") {}
};

class HeapLlenoException : public std::logic_error {
    public:
    HeapLlenoException() : logic_error("Este heap esta lleno, no se le pueden agregar elementos.") {}
};

template <typename T> class Heap {
    protected:
        T* nodos;
        unsigned int tamanioMaximo;
        unsigned int tamanioActual;
        
        void swap(const unsigned int lugar1, const unsigned int lugar2) {
            T temp = nodos[lugar1];
            nodos[lugar1] = nodos[lugar2];
            nodos[lugar2] = temp;
        }
        
        void heapify(const unsigned int posicion) {
            unsigned int posicionACambiar;
            
            if(izquierda(posicion) <= tamanioActual) {
                if(derecha(posicion) <= tamanioActual) {
                    posicionACambiar = nodos[derecha(posicion)] > nodos[izquierda(posicion)] ? derecha(posicion) : izquierda(posicion);
                } else {
                    posicionACambiar = izquierda(posicion);
                }
            } else {
                return; // soy una hoja, porque no puedo tener derecho sin izquierdo
            }
            
            // ya cumplo la propiedad de heap?
            if(nodos[posicion] >= nodos[posicionACambiar]) {
                return;
            }
            
            swap(posicion, posicionACambiar);
            // quizás le rompí la propiedad al que cambié 
            // (el caso 1 -> 40 -> 30 => 40 -> 1 -> 30) entonces arreglo eso
            heapify(posicionACambiar);
       }
        
        void heapifyUp(const unsigned int posicion) {
            unsigned int posicionACambiar = padre(posicion);
            
            // mientras no llegué a la cima, y mi padre tiene un valor mayor que el mío,
            // cambio mi valor por el de mi padre, y checkeo otra vez
            /*while(posicion != 0 && nodos[posicion] > nodos[posicionACambiar]) {
                swap(posicion, posicionACambiar);
                posicion = posicionACambiar;
                posicionACambiar = padre(posicion);
            }*/
            
            
            // con recursión
            
            // estamos en el root, o ya cumplimos la propiedad de heap?
            if(posicion == 0 || nodos[posicion] < nodos[posicionACambiar]) {
                return;
            }
            swap(posicion, posicionACambiar);
            heapifyUp(posicionACambiar);
            
        }
        
    public:
        
        explicit Heap() : nodos(NULL), tamanioMaximo((2<<4)-1), tamanioActual(0) {
            nodos = new T[tamanioMaximo];
        }
        
        explicit Heap(const T* arreglo, unsigned int cantidadElementos) : nodos(new T[cantidadElementos]), tamanioMaximo(cantidadElementos), tamanioActual(cantidadElementos) {
            // hago una copia de, no referencia a, arreglo
            memcpy(nodos, arreglo, cantidadElementos * sizeof(T));
            unsigned int i;
            unsigned int ultimaRama = padre(cantidadElementos);
            for(i = ultimaRama; i <= ultimaRama; i--) { // cuando overflowée, va a ser INT_MAX > ultimaRama
                heapify(i);
            }
        }
        
        explicit Heap(const Heap& heap) : nodos(new T[heap.tamanioMaximo]), tamanioMaximo(heap.tamanioMaximo), tamanioActual(heap.tamanioActual) {
            memcpy(nodos, heap.nodos, tamanioMaximo * sizeof(T));
        }
        
        Heap& operator=(const Heap& heap) {
            if(this != &heap) {
                T* nodos = new T[tamanioMaximo];
                memcpy(nodos, heap.nodos, tamanioMaximo * sizeof(T));
                delete heap.nodos;
            }
            return *this;
        }
        
        void insertar(const T valor) {
            if(tamanioActual >= tamanioMaximo) {
                throw HeapLlenoException();
            }
            // lo inserto en el próximo nodo,
            // y voy cambiándolo con su padre
            // hasta que encaje
            nodos[tamanioActual] = valor;
            heapifyUp(tamanioActual);
            tamanioActual++;
        };
        
        T maximo() {
            return nodos[0]; // O(1) :)
        };
        
        T quitarMaximo() {
            if(tamanioActual == 0) {
                throw NodoInexistenteException();
            }
            T max = nodos[0];
            nodos[0] = nodos[tamanioActual-1];
            tamanioActual--;
            
            heapify(0);
            return max;
        }
        
        void sort() {
            unsigned int tamanioOriginal = tamanioActual;
            // altera el orden de los elementos,
            // manteniendo la propiedad de heap.
            // de esta manera, los indices 0-tamanioActual
            // contienen a los elementos en orden. El arbol,
            // entonces, se lee de izquierda a derecha,
            // de arriba a abajo.
            unsigned int i = tamanioActual - 1;
            while(i > 0) {
                tamanioActual = i-1;
                swap(0, i);
                heapify(0);
                i--;
            }
            tamanioActual = tamanioOriginal;        
        }
        
        static void sort(T*& arreglo, const unsigned int size) {
            cout << "Construyendo el heap..." << endl;
            Heap<T> heap(arreglo, size);
            cout << "Empezando a ordenar." << endl;
            heap.sort();
            unsigned int i;
            for(i = 0; i < size; i++) {
                arreglo[i] = heap.elementAt(i);
            }
        }
        
        // dump en formato graphviz
        void dump(unsigned int nodo = 0) {
            if(nodo == 0) {
                cout << "digraph g {" << endl;
                cout << "node [shape = record,height=.1];" << endl;
            }
            
            cout << "node" << nodo << "[ label = \"<f0> | <f1> " << nodos[nodo] << " | <f2>\"];" << endl;

            if(izquierda(nodo) < tamanioActual) {
                cout << "\"node" << nodo << "\":f0 -> \"node"<<izquierda(nodo)<<"\":f1" << endl;
                dump(izquierda(nodo));
            }

            if(derecha(nodo) < tamanioActual) {
                cout << "\"node" << nodo << "\":f2 -> \"node"<<derecha(nodo)<<"\":f1" << endl;
                dump(derecha(nodo));
            }
            
            if(nodo == 0) {
                cout << "}" << endl;
            }
        };
        
        T elementAt(const unsigned int i) {
            if(i >= tamanioActual) {
                throw NodoInexistenteException();
            }
            return nodos[i];
        }
        
        ~Heap() {
            delete nodos;
        }
};

int main() {
    
    /*
    Heap<int> heap;
    heap.insertar(5);
    heap.insertar(3);
    heap.insertar(8);
    heap.insertar(9);
    heap.insertar(5);
    heap.insertar(32);
    heap.insertar(5);
    heap.insertar(15);
    cout << "Max: " << heap.quitarMaximo() << endl;

    */
    
    srand ( time(NULL) );
    unsigned int cuantos = 10000000;
    unsigned int i;
    cout << "Alocando memoria..." << endl;
    int* elementos = new int[cuantos];
    cout << "Llenando con datos..." << endl;
    for(i = 0; i < cuantos; i++) {
        elementos[i] = rand();
    }
    struct timeval start, end;
    long mtime, seconds, useconds;
    cout << "Empezando..." << endl;

    gettimeofday(&start, NULL);
    Heap<int>::sort(elementos, cuantos);
    gettimeofday(&end, NULL);
    
    seconds  = end.tv_sec  - start.tv_sec;
    useconds = end.tv_usec - start.tv_usec;

    mtime = (long) (((seconds) * 1000 + useconds/1000.0) + 0.5);


    cout << "Ordenados " << cuantos << " enteros en " << mtime << " milisegundos." << endl;

    
    return 0;
}