Learn Computer Science programming - C# and C++ Algorithms

 
Heap Sort
The heap sort is the slowest of the O(n log n) sorting algorithms. however, it doesn't require iefficient recursion or multiple arrays like merge and quick sorts. It is primarily used for large data sets. It is quite simple. It basically build a heap, removes the largest items and placing them at the end of a sorted array, reconstructs the heap and repeats. It is slower than the merge sort and quick sort.
Code
heap_sort.zip
File Size: 4198 kb
File Type: zip
Download File

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <windows.h>
using namespace std;

int Parent(int i);
int Left(int i);
int Right(int i);

int* BuildHeap(int* x, int n);
void Heapify(int* x, int n, int ArrayLength);
void Up(int* buffer, int m);

struct HeapN
{
HeapN* Left;
HeapN* right;
void* Value;
};

class Heap
{
private:
HeapN* root;
public:
Heap() 
{
root = NULL;
root->Left = NULL;
root->right = NULL;
};

HeapN* AccessHeapRoot(){return root;};
void InsertHeapN(void* v);
};

void Heap::InsertHeapN(void* v)
{
HeapN* NewHeapN = new HeapN;
if (!root); 
}

void main()
{
wcout <<  endl << "*** Heap Sort Example ***" << endl;
wcout << "*************************************************" << endl;
wcout << "Array content to sort: {5,2, 100, 1 , 60, 200}" << endl;

int a[] = {5,2, 100, 1 , 60, 200};
int n = 6;
int* b = new int[6];
b = BuildHeap(a, 6);
//Sorting

int c[6];
for (int j=0; j<6; j++)
{
c[j] = b[j];
}
for (int k = n; k > 1; k--)
{
a[k-1] = c[0];
c[0] = c[k-1];
c[k-1] = 0;
Heapify(c, 1, (k-1));

}
a[0] = c[0];
for (int j=0; j<6; j++)
{
cout << endl << a[j];
}
delete b;
cin >> a[1];
}

int* BuildHeap(int* x, int n)
{
int* buffer2 = new int[n];
for (int i = 0; i < n+1; i++)
{
if (i < n) buffer2[i] = x[i];
Up(buffer2, i);
}
return buffer2;
}

int Parent(int i)
{
return ((i/2));
}

int Left(int i)
{
return (i*2);
}

int Right(int i)
{
return (i*2+1);
}

void Heapify(int* x, int n, int ArrayLength)
{
int L = Left(n);
int R = Right(n);
int Largest = x[n-1];
int large = n-1;

if((x[L-1] > Largest) && (L <= ArrayLength))
{
Largest = x[L-1];
large = L-1;
}

if((x[R-1] > Largest) && (R <= ArrayLength))
{
Largest = x[R-1];
large= R-1;
}

if (Largest == x[n-1]) return;
else
{
int temp = x[n-1];
x[n-1] = Largest;
x[large] = temp;
}
Heapify(x, large+1, ArrayLength);
}

void Up(int* buffer, int m)
{
if (Parent(m)>0) //to avoid -1 for parent
{
if (buffer[m-1] >buffer[(Parent(m)-1)]) 
{
//Swap(buffer[i], buffer[(Parent(i))] )
int temp = buffer[m-1];
int temp2 = buffer[(Parent(m)-1)];
buffer[m-1] = buffer[(Parent(m)-1)];
buffer[(Parent(m)-1)] = temp;
Up(buffer, (Parent(m)));
}
}
return;
}