HEAP

#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
#include "string.h"

using namespace std;

struct HeapItem
{
    char* profession;
    float salary;
};

struct Heap
{
    HeapItem** elements;
    //dimensiunea maxima a masivului
    int heapSize;
    //numarul curent de elemente din vector
    int noElements;
};

HeapItem* createElement(char*, float);
void initHeap(Heap&, int);
void enqueue(Heap&, HeapItem*);
void main()
{
    FILE* pFile = fopen("Date.txt", "r");
    Heap heap;
    initHeap(heap, 10);
    if (pFile)
    {
        char buffer[100]; float salary;
        fscanf(pFile, "%s", buffer);
        while (!feof(pFile))
        {
            fscanf(pFile, "%f", &salary);

            //1. create an element of type List*
            HeapItem* newElement = createElement(buffer, salary);
            //2. insert the newly created element
            enqueue(heap, newElement);
            fscanf(pFile, "%s", buffer);
        }
        fclose(pFile);
    }
    for (int i = 0; i < heap.noElements; i++)
    {
        printf("Index: %d - %f\n",
            i, heap.elements[i]->salary);
    }
}



void ReheapUp(Heap heap, int first, int back)
{
    HeapItem* parent;
    int indexParent;
    HeapItem* tmp;
    if (back > first)
    {
        //rehipificare
        indexParent = (back - 1) / 2;
        parent = heap.elements[indexParent];
        if (heap.elements[back]->salary >
            parent->salary)
        {
            //interschimb
            tmp = heap.elements[indexParent];
            heap.elements[indexParent] = heap.elements[back];
            heap.elements[back] = tmp;
            ReheapUp(heap, 0, indexParent);
        }
    }
    //altfel iesire din recursivitate
}
void ReheapDown(Heap heap, int front)
{
    int leftIndex = front * 2 + 1;
    int rightIndex = front * 2 + 2;
    int maxIndex;
    HeapItem* max = NULL;
    HeapItem* parent = heap.elements[front];

    if (leftIndex <= heap.noElements - 1)
    {
        if (leftIndex == heap.noElements - 1)
            max = heap.elements[leftIndex];
        else
        {
            if (heap.elements[leftIndex]->salary >
                heap.elements[rightIndex]->salary)
            {
                max = heap.elements[leftIndex];
                maxIndex = leftIndex;
            }
            else
            {
                max = heap.elements[rightIndex];
                maxIndex = rightIndex;
            }
        }
        if (max->salary > heap.elements[front]->salary)
        {
            heap.elements[front] = max;
            heap.elements[rightIndex] = parent;
            ReheapDown(heap, maxIndex);
        }
    }
}

HeapItem* dequeue(Heap& heap)
{
    HeapItem* result = NULL;
    if (heap.noElements != 0)
    {
        result = heap.elements[0];
        heap.noElements--;
        heap.elements[0] = heap.elements[heap.noElements];
        ReheapDown(heap, 0);
    }
    return result;
}

void enqueue(Heap& heap, HeapItem* item)
{
    if (heap.noElements < heap.heapSize)
    {
        heap.elements[heap.noElements] = item;
        ReheapUp(heap, 0, heap.noElements);
        heap.noElements++;
    }
}

void initHeap(Heap& heap, int size)
{
    heap.elements = (HeapItem**)malloc(sizeof(HeapItem*)* size);
    heap.heapSize = size;
    heap.noElements = 0;
    memset(heap.elements, NULL, sizeof(HeapItem*)*size);
}

HeapItem* createElement(char* buffer, float salary)
{
    //1.allocate memory for the new element
    HeapItem* newElement = (HeapItem*)malloc(sizeof(HeapItem));
    //2.initialize it with the params
    //(the connection attributes should remain NULL)
    newElement->salary = salary;
    newElement->profession = (char*)malloc(strlen(buffer) + 1);
    strcpy(newElement->profession, buffer);
    //3.return the new element
    return newElement;
}