Heapsort algorithm

Advertisemen

 Apologies for the lack of comments but I don't tend to comment small personal projects.

On a high note this runs twice as fast as my mergesort which I created for my algorithms coursework - I had to resort to using STL Vectors due to memory leaks occuring... Not fun

#include <iostream>

#include <time.h>

using namespace std;

template <typename T>

class heap

{

       int maxSize;

       int curSize;

       T *data;

       int getLeft(int index) { return (index<<1)+1; }

       int getRight(int index) { return (index<<1)+2; }

       int getParent(int index) { return (index-1)>>1;}

       int getLargestChild(int index) { int l=getLeft(index), r=getRight(index); if (this->data[l] > this->data[r]) return l; else return r; }

       void swapWithParent(int index);

       void siftDown(int, int);

public:

       int getSize() const { return this->maxSize; }

       heap( int Size=100 ) { this->maxSize = Size; this->data = new T[maxSize]; curSize=0; }

       ~heap()

       {

              delete[] data;

              data = NULL;

       }

      

       //data entry/removal

       void addElement(T);

       void removeRoot();

       //sorting

       void Heapify(const T*, int);

       void Heapsort();

       //output funcs

       void printAsArray();

       void printAsTree();

};

template <typename T>

void heap<T>::Heapify(const T *arr, int size)

{

       for (int i=0;i<size;i++)

              this->addElement(arr[i]);

}

template <typename T>

void heap<T>::siftDown(int start, int end)

{

       int root = start;

       while (getLeft(root) <= end)

       {

              int child = getLeft(root);

              int swap = root;

              if (this->data[swap] < this->data[child])

                     swap = child;

              if (child+1 <= end && this->data[swap] < this->data[child+1])

                     swap = child + 1;

              if (swap != root)

              {

                     this->swapWithParent(swap);

                     root = swap;

              }

              else return;

       }

}

template <typename T>

void heap<T>::Heapsort()

{

       int pos = this->curSize-1;

       while (pos > 0)

       {

              swap(this->data[pos],this->data[0]);

              pos--;

             

              this->siftDown(0,pos);

       }

}

template <typename T>

void heap<T>::swapWithParent(int index)

{

       swap(this->data[index],this->data[getParent(index)]);

}

template <typename T>

void heap<T>::addElement(T val)

{

       if (this->curSize > 0)

       {

              int i,j;

              j=this->curSize;

              i=getParent(j);

              this->data[j] = val;

              while (this->data[j] > this->data[i] && i >= 0)

              {

                     this->swapWithParent(j);

                     j = i;

                     i = getParent(i);

              }

       }

       else this->data[0] = val;

      

       this->curSize++;

       return;

}

template <typename T>

void heap<T>::removeRoot()

{

       this->data[0] = this->data[curSize---1]; //set the root to the last node and reduce the heap size

       int i=0;

       while (1)

       {

              int index = this->getLargestChild(i);

              if (this->data[i] < this->data[index])

              {

                     this->swapWithParent(index);

                     i = index;

              }

              else return;

       }

}

template <typename T>

void heap<T>::printAsArray()

{

       cout << " { ";

       for (int i=0;i<this->maxSize-1;i++)

              cout << this->data[i] << " , ";

       cout << this->data[this->maxSize-1] << " } \n";

}

template <typename T>

void heap<T>::printAsTree() //modified from http://xoax.net/comp/sci/algorithms/Lesson9.php

{

        // Find the largest power of two, That is the depth

       int iDepth = 0;

       int iCopy = this->curSize;

       while (iCopy > 0) {

              iCopy >>= 1;

              ++iDepth;

       }

       int iMaxWidth = (1 << iDepth);

       int iCharWidth = 4*iMaxWidth;

       int iEntry = 0;

       for (int i = 0; i < iDepth; ++i) {

              int iPowerOf2 = (1 << i);

              for (int j = 0; j < iPowerOf2; ++j) {

                     int iSpacesBefore = ((iCharWidth/(1 << (i + 1))) - 1);

                      // Spaces before number

                     for (int k = 0; k < iSpacesBefore; ++k) {

                           cout << " ";

                     }

                      // Output an extra space if the number is less than 10

                     if (this->data[iEntry] < 10) {

                           cout << " ";

                     }

                      // Output the entry and the spaces after it

                     cout << this->data[iEntry];

                     ++iEntry;

                     if (iEntry >= this->curSize) {

                           cout << endl;

                           return;

                     }

                     for (int k = 0; k < iSpacesBefore; ++k) {

                           cout << " ";

                     }

              }

              cout << endl << endl;

       }

}

void printArray(int *a, int s)

{

       cout << " { ";

       for (int i=0;i<s-1;i++)

              cout << a[i] << " , ";

       cout << a[s-1] << " } \n";

}

int main() {

       int size = 1000000;

       srand(time(NULL));

       heap<float> Heap(size);

       float *arr = new float[size];

      

       for (int i=0;i<size;i++)

              arr[i] = rand()%100000/5474;

      

       int s = clock();

       Heap.Heapify(arr,size);

       Heap.Heapsort();

       cout << clock()-s<<endl;

       delete[] arr;

       Heap.~heap();

    return 0;

}

Advertisemen