Heap.h

gistfile1.cpp

#ifndef HEAP_H
#define HEAP_H

#include <iostream>
using namespace std;

template <typename T>
class Heap {

    private:

        class Node {
			public:
				T value;
				Node(T value) {
					this->value = value;
				}
				~Node() {}
		};

        Node** heap;
        int capacity;

        int lastPos;

        void swap(Node* &a, Node* &b);
        void resize(int newSize);
    public:
        Heap(int capacity = 15);
        ~Heap();

        void insertLast(T value);
        T removeFirst();

        void printAll() const;
};



template <typename T>
Heap<T>::Heap(int capacity) {
    this->capacity = capacity;
    this->heap = new Node*[this->capacity];
    this->lastPos = 0;

    for (int i = 0; i < capacity; i++) {
        this->heap[i] = NULL;
    }
}

template <typename T>
Heap<T>::~Heap() {
    for (int i = 0; i < this->capacity; i++) {
        if (this->heap[i] != NULL) {
            delete this->heap[i];
        }
    }
    delete[] this->heap;
}

template <typename T>
void Heap<T>::swap(Node* &a, Node* &b) {
    Node* tmp = a;
    a = b;
    b = tmp;
    cout << "Swapping " << a->value << " with " << b->value << endl;
}

template <typename T>
void Heap<T>::resize(int newSize) {
	Node** tmp = new Node*[newSize];
	for (int i = 0; i < newSize; i++) {

		if (i < this->capacity && this->heap[i] != NULL) {
			tmp[i] = this->heap[i];
		} else {
            tmp[i] = NULL;
		}
	}

	if (this->heap != NULL) {
		delete[] this->heap;
		this->heap = NULL;
	}

	this->heap = tmp;
	cout << "Resized from " << this->capacity << " to " << newSize << endl;
	this->capacity = newSize;
}

template <typename T>
void Heap<T>::insertLast(T value) {

    if (this->lastPos+2 > this->capacity) {
        this->resize(this->capacity+5);
    }

    Node* node = new Node(value);
    int k = this->lastPos+1;

    this->heap[k] = node;
    this->lastPos++;
    cout << "Inserting " << node->value << endl;
    this->printAll();
    while(k > 1 && this->heap[k/2]->value < node->value) {
        this->swap(this->heap[k], this->heap[k/2]);
        this->printAll();
        k = k/2;
    }
}

template <typename T>
T Heap<T>::removeFirst() {
    if (this->lastPos == 0) {
        throw "Exception in Heap::removeFront(): Heap is empty";
    }
    T value = this->heap[1]->value;
    cout << "Removing " << value << endl;
    this->printAll();
    delete this->heap[1];
    this->heap[1] = this->heap[this->lastPos];
    this->heap[this->lastPos] = NULL;
    this->lastPos--;
    this->printAll();
    int k = 1;
    while(2*k < this->lastPos) {
        //cout << "k = " << k << "("<<this->heap[k]->value<<"), left: " << 2*k << "("<<*this->heap[2*k]->value<<"), right: " << 2*k+1 << "("<<*this->heap[2*k+1]->value<<")" << endl;

        if (2*k < this->lastPos && this->heap[2*k]->value > this->heap[2*k+1]->value) {
            //cout << "LEFT BRANCH: "<< this->heap[2*k]->value << endl;
            swap(this->heap[k], this->heap[2*k]);
            this->printAll();
            k = k*2;
        } else if (2*k+1 < this->lastPos && this->heap[k]->value < this->heap[2*k+1]->value) {
            //cout << "RIGHT BRANCH: "<< this->heap[2*k+1]->value << endl;
            swap(this->heap[k], this->heap[2*k+1]);
            this->printAll();
            k = k*2+1;
        } else {
            //cout << "BREAK" << endl;
            break;
        }
    }
    this->printAll();

    if (this->lastPos < this->capacity-5) {
        this->resize(this->capacity-5);
    }

    return value;
}

template <typename T>
void Heap<T>::printAll() const {
    for (int i = 0; i < this->capacity; i++) {
        if (this->heap[i] != NULL) {
            cout << this->heap[i]->value << " ";
        } else {
            cout << "- ";
        }
    }
    cout << endl;
}

#endif