# C++ Heap implementation

I'm on my way of understanding basic data structures and sorting algorithms through implementing them in c++. Post is followed of my implementation of Vector. I decided to weld the heap behaviour right into Vector class, although I'm not sure if it's a good solution/practice. The heapSort method is not yet implemented. I'm not figuring out how I can build it based on already existing methods. As at my office heavily criticising is an accepted practice, I'm asking for
rather hard, destructive critics and review.

#include "Vector.hpp"

Vector::Vector(int size):size(size) {
array = new int[size]();
}

Vector::Vector(int vector[], int sizeT) {
this->array = new int[sizeT]();
this->size = sizeT;
for(int i = 0; i < sizeT; ++i) {
this->array[i] = vector[i];
}
}

Vector::Vector(Vector* v1) {
this->array = v1->array;
this->size = v1->size;
}

Vector::~Vector() {
delete[] array;
}

int Vector::length() {
return this->size;
}

int Vector::getAt(int idx) {
if(idx >= this->size) {
throw "out of range";
}
return this->array[idx];
}

int& Vector::operator[](const int index){
if(index >= this->size) {
throw "out of range";
}

return this->array[index];
}

void Vector::deteleAt(int idx) {
for(int i = idx; i < this->length() - 1; ++i) {
this->array[i] = this->array[i+1];
}
--this->size;
}

//HEAP--------PRIORITY QUEUE
int Vector::parent(int idx) {
if(idx >= 0 && idx <= 2) {
return this->array;
}

return this->array[idx/2];
}

bool Vector::hasLeftChild(int idx) {
return this->leftChild(idx) < this->size;
}

bool Vector::hasRightChild(int idx) {
return this->rightChild(idx) < this->size;
}

void Vector::buildMaxHeap() {
for(int i = this->size / 2; i >= 0; i--) {
this->maxHeapify(i);
}
}

void Vector::maxHeapify(int idx) {
if(!this->hasRightChild(idx) && !this->hasLeftChild(idx)) {
return;
}

int l = this->leftChild(idx), r = this->rightChild(idx);
int largest = idx;

if(l < this->size && this->array[l] > this->array[idx]) {
largest = l;
}

if(r < this->size && this->array[r] > this->array[largest]) {
largest = r;
}

if(largest != idx) {
this->swap(idx, largest);
this->maxHeapify(largest);
}
}

void Vector::heapSort() {
for(int i = this->heapSize; i >= 1; i--) {
this->swap(0, i);
this->heapSize--;
this->maxHeapify(0);
}
}

void Vector::swap(int firstIdx, int secondIdx) {
int rotator = this->array[firstIdx];
this->array[firstIdx] = this->array[secondIdx];
this->array[secondIdx] = rotator;
}

int Vector::leftChild(int idx) {
idx = idx * 2;
return idx;
}

int Vector::rightChild(int idx) {
idx = (idx * 2) + 1;

return idx;
}

void Vector::print(){
for(int i = 0; i < this->size; ++i) {
std::cout<<this->array[i]<<" ";
}
std::cout<<"\n";
}

int Vector::popFront(){
int firstElem = this->array;
this->deteleAt(0);
return firstElem;
}

• Not the standard separates the two. We have standard vector as a container. Then we there are a set of heap creation/manipulation functions make_heap push_heap and pop_heap – Martin York Nov 16 '16 at 16:56
• I'm not a C++ guru but adding the heapSort algorithm to your vector container breaks the SRP of solid principle. – Tolani Nov 16 '16 at 16:56
• @TolaniJaiye-Tikolo: What is SRP? Is this like the "Separation of Concerns"? – Martin York Nov 16 '16 at 22:39
• Is Single responsibility principle meant under SRP? – vatevr Nov 16 '16 at 22:42
• @LokiAstari it means Single Responsibility . A container should only be responsible for container related information. It's an OOP design principle name for separation of concerns. see scotch.io/bar-talk/… for more information – Tolani Nov 16 '16 at 22:57

## 1 Answer

I'm asking for rather hard, destructive critics and review.

Sure.

### Interface.

I don't see the interface (ie class definition). So it becomes harder to review.

### Things I don't see

I don't see any move semantics for your class.

Normally (since C++11) I would expect containers to implement move semantics. i.e. I would expect to see the following methods:

 Vector(Vector&& move) nothrow
Vector& operator=(Vector&& move) nothrow
void swap(Vector& other) nothrow


Also I don't see your code implementing the rule of three. This means that your objects will not work correctly if there are any copies made (and C++ makes copies all the time).

To implement the rule of three you need to implement the following three methods:

Vector(Vector const&);
Vector& operator=(Vector const&);
~Vector();


### Code Review

This is a dangerous interface. you are asking the user of your class to know and manually set the size. An important thing in C++ is to try and define interfaces that can not be used incorrectly.

Vector::Vector(int vector[], int sizeT) {


I prefer the iterator version of the interface. Yes it is still just as dangerous but the utility functions add in C++14 will help you correctly identify the dangers and potentially generate compiler errors.

template<typename T>
Vector::Vector(I begin, I end) {


Now when you use it.

int data;
Vector   v(std::begin(data), std::end(data)); // will correctly size the vector
// even if the size is changed.

void test(int* data, std::size_t s)
{
Vector v(data, data + s); // still works (you just need to add).
}

int*     data = new data;
Vector   v(std::begin(data), std::end(data));  // will fail to compile
// For the dangerous
// situations it fails to compile.
// which makes you look.


### Use of this-> is discouraged

I consider the use of this-> dangerous as it hides errors. It also shows that you are being lazy in naming your local/member variables.

I know you are going to ask "how does it hide errors?".

The only reason that you need to use this-> is when you have shadowed member variables. You then use this-> to differentiate the member variables from the local variables. But it requires that everybody correctly identify the member/local variable. Any mistake will still silently compile. So this type of error can not be detected by the compiler.

On the other hand if you don't allow shadowed variables (and you can make the compiler detect shadowed variables and fail your compilation) now you have no situation where dropping the this-> (or forgetting) it will NOT cause an error. Since it does not matter whether the this-> is there or not why not just drop it.

### This is a funny Constructor.

Not even sure why you would have this interface.

Vector::Vector(Vector* v1) {


You normally have a copy constructor which looks like this:

Vector::Vector(Vector const& v1) {


But an interface that takes pointers is very rare (and for this type of situation is practically never done). You are leaking ownership information. Who ownes the pointer you pass? (Ownership semantics is very important in C++ as the owner of the object is the person responsible for deleting it. A pointer has no ownership information).

### Error:

Additionally this interface is broken.

Vector::Vector(Vector* v1) {
this->array = v1->array;
this->size = v1->size;
}


Consider this situation:

{
Vector   a(5);
Vector   b(&a);   // This is your copy (but the same would apply if
// you naively converted it to a standard copy
// constructor)
}


In the above case both object point at the same dynamically created object. Not a problem in itself. BUT they both think they own the object and thus will both delete it in there destructor this is illegal.

### Const methods

A method that does not change the state of the object should be marked as const.

int Vector::length() {
return this->size;
}


This is both an indication to the compiler and also allows the object to be used in a context where you only have a const reference (quite common).

### Exceptions

Yes you can throw anything. But normally you would throw an exception object that is derived from std::runtime_error.

In your code you are throwing an object of type char const*.

int Vector::getAt(int idx) {
if(idx >= this->size) {
throw "out of range";
}
return this->array[idx];
}


I would do it like this:

int Vector::getAt(int idx) {
if(idx >= this->size) {
throw std::out_of_range("Vector::at()");
}
return this->array[idx];
}


### Don't do checks for the user.

Don't do uneeded checks for the user. Rather provide methods so that users can perform their own checks to validate there calls. You can provide a checked version of the interface as well.

The std::vector has two techniques for access elemements (just like you). operator[]() and at(). The only difference between the two is that at() validates the index and operator[]() does not.

int& Vector::operator[](const int index){

// Would not expect this check.
if(index >= this->size) {
throw "Vector::out of range";
}

return this->array[index];
}


The reason is that in most use cases you don't need to validate the range because you have already validated that your index is within the required range:

for(int loop = 0;loop < v.size(); ++loop) {
// No need to check the range of loop
// You have guranteed it is correct by the context it is used in.
// Thus we use the unchecked range operator.
std::cout << v[loop] << "\n";
}


### Do check the range where it is important.

Here I would check the range.

void Vector::deteleAt(int idx) {
for(int i = idx; i < this->length() - 1; ++i) {
this->array[i] = this->array[i+1];
}
--this->size;
}


The line --this->size; is unchecked. If I delete a non existent element then it still reduces the size. Probably not what you want.

### Looks Fishy

This is a very standard pattern for parent and children in a heap.

//HEAP--------PRIORITY QUEUE
int Vector::parent(int idx) {
if(idx >= 0 && idx <= 2) {
return this->array;
}

return this->array[idx/2];
}


The fact that you are special casing 1 and 2 makes me suspicious that there is underlying error you are trying to correct for.

Should not the parent be:

parent = (child-1)/2    //   0   1   2
leftC  = parent*2 + 1   //   1   3   5
rightC = parent*2 + 2   //   2   4   6


### Use standard algorithms where you can

void Vector::swap(int firstIdx, int secondIdx) {
int rotator = this->array[firstIdx];
this->array[firstIdx] = this->array[secondIdx];
this->array[secondIdx] = rotator;
}


There is a std::swap() this will swap two elements in the most efficient way possible. For integers your swap is probably the most efficient. But if you change what is held by your vector to some other complex object this may no longer be the most efficient technique (think move semantics).

### Printing

When having a printing function, what you are actually doing is writing to a stream. So why not provide the opportunity to use different streams. So add a parameter that allows you to specify the stream (this can default to std::cout.

void Vector::print(){
for(int i = 0; i < this->size; ++i) {
std::cout<<this->array[i]<<" ";
}
std::cout<<"\n";
}


Also the default way of printing something in C++ is to use the output operator operator<< so you may as welll write that so that it uses your print function.

std::ostream& operator<<(std::ostream& s, Vector const& output)
{
output.print(s);
return s;
}