75 artiklar, 15 användare, 188002 besök, 36420 unika

Startsida
WEBmaster
Guide
Sök blogg
Sök Bilder
Sök användare
Taggar
Slumpad blogg
Slumpad sida
Slumpad bild
Dagens Nyheter
Den Senaste
Chatt
Senaste bilderna
Mest visade
Topplista

Kategorier:
Filmer
Gambling
Musik
Skolarbeten
Spel
Skolarbeten/Datastrukturer
Admin /  Skapad: 20:11 - Tisdagen den 19 Februari 2008 / Bloggnummer: 504 / Visad 9731 gånger
Senast uppdaterad: 20:11 - Tisdagen den 19 Februari 2008 / Kommentararer är avstängda

Heap

#ifndef HEAP_H
#define HEAP_H
#include <iostream>
using namespace std;
template <class T>
class Heap
{
private:
    int nrOfElements;
    int capacity;
    T * elements;
    int increment;
public:
    Heap();
    Heap(int size);
    ~Heap();
    void insert(T element);
    void remove();
    T front();
    int size();
    void print();
    void sizeUp(int newSize);
    bool inHeap(T element);
};
template <class T>
Heap<T>::Heap()
{
    nrOfElements = 0;
    increment = 10000;
    capacity = increment;
    elements = new T[capacity];
}
template <class T>
Heap<T>::Heap(int size)
{
    nrOfElements = 0;
    increment = 10000;
    capacity = size;
    elements = new T[size];
}
template <class T>
Heap<T>::~Heap()
{
    delete [] elements;
}
template <class T>
void Heap<T>::insert(T element)
{
    if(capacity <= nrOfElements)
        sizeUp(capacity+increment);

    if(nrOfElements == 0)
        elements[0] = element;
    else
    {
        elements[nrOfElements] = element;
        int temp = (nrOfElements-1)/2;//Föräldern
        int posHolder = nrOfElements; //Barnet
        while(elements[temp] < element)
        {
            T temp2 = elements[temp];
            elements[temp] = elements[posHolder];
            elements[posHolder] = temp2;
            posHolder = temp;
            temp = (temp-1)/2;
        }
    }
    nrOfElements++;
}
template <class T>
void Heap<T>::remove()
{
    nrOfElements--;
    int currentPos = 0;
    elements[currentPos] = elements[nrOfElements];
    int biggestChildPos = 0;
    while(currentPos*2+2 < nrOfElements)
    {
        if(elements[currentPos*2+1] > elements[currentPos*2+2])
            biggestChildPos = currentPos*2+1;
        else
            biggestChildPos = currentPos*2+2;
        if(elements[biggestChildPos] > elements[currentPos])
        {
            T temp = elements[currentPos];
            elements[currentPos] = elements[biggestChildPos];
            elements[biggestChildPos] = temp;
            currentPos = biggestChildPos;
        }
        else currentPos = nrOfElements;
    }
}
template <class T>
T Heap<T>::front()
{
    if(nrOfElements > 0)
        return elements[0];
    else return T();
}
template <class T>
int Heap<T>::size()
{
    return nrOfElements;
}
template <class T>
void Heap<T>::print()
{
    for(int i = 0;i<nrOfElements;i++)
        cout << elements[i] << endl;
    cout << endl;
}
template <class T>
void Heap<T>::sizeUp(int newSize)
{
    int inc = newSize-capacity;
    capacity = newSize;
    T * temp = new T[capacity];
    for(int i = 0;i<capacity-inc;i++)
        temp[i] = elements[i];
    delete [] elements;
    elements = temp;
}
template <class T>
bool Heap<T>::inHeap(T element)
{
    if(nrOfElements == 0)
        return false;
    else
    {
        for(int i = 0;i<nrOfElements;i++)
            if(element == elements[i])   
                return true;
    }
    return false;
}
#endif



 
     
Design/kodning/planering - Jonatan Jönsson