Heap Sort Algorithm In C++

Heap sort algorithm is a comparison based ( divide and conquer ) sorting algorithm with worst and base case complexity of O (n log n) invented by J. W. J. Williams in 1964. [1] Implementing heap sort algorithm in C++ can be divided into two phases. The first phase is to turn the original array into a binary heap structure. Each array elements ( indices ) represents the nodes of the binary heap tree. Root of tree is always the first index (0 th index) of the array. The relationship with the nodes and the indices is as following; If j is the index of current node; then

parent = floor( (j – 1) / 2)

 leftChild = (2 * j ) + 1

righChild = (2 * j ) + 2

The second phase is recursively removing the largest or smallest dependent on order by ( ascending or descending ) element from the heap ( root of the heap ) and inserting it into the array. At the end of this recursive phase original array is sorted.

Implementing Heap Sort Algorithm In C++

In this post, I will write down a heap class which takes an unsorted array pointer as a parameter or a file that has random numbers per each line.

heap.h

#ifndef HEAP_H_
#define HEAP_H_

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

class Heap
{

public:
    	
	enum order
	{
		ASCENDING, DESCENDING
	};

	Heap(std::string fileName, Heap::order type);

	Heap(int* array, int size, Heap::order type);

	void sort();

	void writeToFile(std::string fileName);
	
	void print() const;

	void setSortType(Heap::order type);

	~Heap();

protected:

	int *array;
	
	int arraySize, heapSize;
	
	Heap::order sortType;

	bool isFromFile;

	void _minHeapify(int);

	void _maxHeapify(int);

	void _buildMaxHeap();

	void _buildMinHeap();

	void _swap(int, int);
};

#endif /* HEAP_H_ */

heap.cxx

#include "heap.h"

Heap::Heap(int *array, int size, Heap::order type)
{
    this->array = array;
	this->arraySize = size - 1;
	this->heapSize = this->arraySize;
	this->sortType = type;
	this->isFromFile = false;
}

Heap::Heap(std::string fileName, Heap::order type)
{
	std::ifstream file;

	file.open(fileName.c_str());

	if(!file)
	{
		std::cerr << "File could not be opened" << std::endl;
		exit(1);
	}

	std::string temp;
	int numberOfLines = 0;

	while(getline(file, temp))
	{
		++numberOfLines;
	}

	file.clear();
	file.seekg(0, std::ios::beg);

	this->arraySize = numberOfLines;
	this->heapSize = this->arraySize;

	array = new int[this->arraySize];
	this->sortType = type;
	this->isFromFile = true;
	int c = 0;
	int number;
	while( file>>number )
	{
		this->array[c++] = number;
	}

	file.close();
}

void Heap::writeToFile(std::string fileName)
{
	std::ofstream file;
	file.open(fileName.c_str(), std::ios::out);
	
	if(file.is_open())
	{
		for(int i = 0; i < this->arraySize; i++)
		{
			file << this->array[i] << std::endl;
		}
	}
	else
	{
		std::cerr << "Unable to create file" << std::endl;
		exit(1);
	}

	file.close();
}

void Heap::print() const
{
	for (int i = 0; i < this->arraySize; i++)
	{
		if (i == 0)
		{
			std::cout << "[ " << this->array[i] << ", ";
		}
		else if (i > 0 && i < this->arraySize - 1)
		{
			std::cout << this->array[i] << ", ";
		}
		else
		{
			std::cout << this->array[i] << "]" << std::endl;
		}
	}
}

void Heap::setSortType(Heap::order type)
{
	this->sortType = type;
}

void Heap::sort()
{
	std::cout <<"Heap sort begins..." << std::endl;

	if(this->sortType == Heap::ASCENDING)
	{
		this->_buildMaxHeap();

		for(int i = this->arraySize; i>= 1; i--)
		{
			this->_swap(0, i);
			this->heapSize--;
			this->_maxHeapify(0);
		}

	}
	else if ( this->sortType == Heap::DESCENDING )
	{
		this->_buildMinHeap();

		for(int i = this->arraySize; i>= 1; i--)
		{
			this->_swap(0, i);
			this->heapSize--;
			this->_minHeapify(0);
		}
	}
}

void Heap::_buildMaxHeap()
{
	this->heapSize = this->arraySize;

	for(int i = floor(this->arraySize/2); i >= 1; i--)
	{
		this->_maxHeapify(i);
	}
}

void Heap::_buildMinHeap()
{
	this->heapSize = this->arraySize;

	for(int i = floor(this->arraySize/2); i >= 1; i--)
	{
		this->_minHeapify(i);
	}
}

void Heap::_minHeapify(int i)
{
	int left, right, smallest;

	left = 2 * i + 1;
	right = 2 * i + 2;

	if((left <= this->heapSize) && (this->array[left] < this->array[i]))
	{
		smallest = left;
	}
	else
	{
		smallest = i;
	}

	if((right <= this->heapSize) && (this->array[right] < this->array[smallest]))
	{
		smallest = right;
	}

	if(smallest != i)
	{
		this->_swap(i, smallest);
		this->_minHeapify(smallest);
	}
}

void Heap::_maxHeapify(int i)
{
	int left, right, biggest;

	left = 2 * i + 1;
	right = 2 * i + 2;

	if((left <= this->heapSize) && (this->array[left] > this->array[i]))
	{
		biggest = left;
	}
	else
	{
		biggest = i;
	}

	if((right <= this->heapSize) && (this->array[right] > this->array[biggest]))
	{
		biggest = right;
	}

	if(biggest != i)
	{
		this->_swap(i, biggest);
		this->_maxHeapify(biggest);
	}
}

void Heap::_swap(int a, int b)
{
	int temp;
	temp = this->array[a];
	this->array[a] = this->array[b];
	this->array[b] = temp;
}

Heap::~Heap()
{
	if (this->array && this->isFromFile )
	{
		delete this->array;
		this->array = NULL;
	}

	std::cout << "Heap is destructed" << std::endl;
}

main.cxx

#include "heap.h"

#include <fstream>
#include <iostream>
#include <ctime>
#include <stdlib.h>

#include "boost/random.hpp"
#include "boost/generator_iterator.hpp"

void constructRandomFile(int numberOfLines, int min, int max)
{
    typedef boost::mt19937 RNGType;
	RNGType rng(time(NULL));

	boost::uniform_int<> range( min, max);
	boost::variate_generator< RNGType, boost::uniform_int<> > random(rng, range);

	std::ofstream file;
	file.open("sample-data.txt", std::ios::out);
	
	if(file.is_open())
	{
		for(int i = 0; i < numberOfLines; i++)
		{
			file << random() << std::endl;
		}
	}
	else
	{
		std::cerr << "Unable to create file" << std::endl;
		exit(1);
	}

	file.close();
}

int main(int argc, char **argv)
{
	if ( argc != 5 )
	{
		std::cerr << "Sample Usage : " << argv[0] << " numberOfLines min max order(ascending or descending)" << std::endl;
		return -1;
	}

	int numberOfLines = atoi(argv[1]);
	int min = atoi(argv[2]);
	int max = atoi(argv[3]);
	std::string sortType = argv[4];

	constructRandomFile(numberOfLines, min, max);

	double sort_start_clk, sort_end_clk;

	Heap *heap = NULL;

	if(strcmp(sortType.c_str(), "ascending") == 0 || strcmp(sortType.c_str(), "ASCENDING") == 0)
	{
		heap = new Heap("./sample-data.txt", Heap::ASCENDING);
	}
	else if(strcmp(sortType.c_str(), "descending") == 0 || strcmp(sortType.c_str(), "DESCENDING") == 0)
	{
		heap = new Heap("./sample-data.txt", Heap::DESCENDING);
	}
	else
	{
		std::cerr << "Invalid Sort Type. Accepted values are (ascending, descending, ASCENDING, DESCENDING)" << std::endl;
		return -1;
	}

	sort_start_clk = clock();
	heap->sort();
	sort_end_clk = clock();

	double sort_time = (double) (sort_end_clk - sort_start_clk) * 1000 / CLOCKS_PER_SEC;
	
	std::cout <<"Heap Sort Time: " << sort_time << " miliseconds" << std::endl;

	std::cout << "Writing to file..." << std::endl;
	heap->writeToFile("./sorted.txt");
	std::cout << "Writing done." << std::endl;
	
	delete heap;

	return 0;
}



makefile

CC=g++
CFLAGS=-O3 -Wall -c -fmessage-length=0

all: heap

heap: main.o heap.o
    $(CC) main.o heap.o -o heap

main.o: main.cxx
	$(CC) $(CFLAGS) main.cxx

heap.o: heap.cxx
	$(CC) $(CFLAGS) heap.cxx

clean:
	rm -r heap *.o

To access the source code click the following link : http://www.chasank.com/uploads/heapsort-in-cpp-blog-chasank-com.tar.gz

To be able to compile the source code boost library should be present on the current system. To install boost library install the following libraries on console.

yum -y install boost boost-devel

For those who does not want to install boost library I have uploaded a sample data which contains unsorted ten millions lines between 1 and 10000000 ( ten millions) To download sample data click the following link; http://www.chasank.com/uploads/sample-data.tar.gz

Just remove the constructRandomFile function and boost headers from the main.cxx. Make the necessary changes to feed the heap class with sample data.

References

1. “Heapsort”, Wikipedia, Retrieved On 24.05.2015 from http://en.wikipedia.org/wiki/Heapsort