#include <iostream>
#include <climits>
#include <fstream>
#include <stdlib.h>
#include <time.h>
#include<string.h>

using namespace std;

struct hufnod{
    char c;
    int frecv;
    struct hufnod *right,*left;
};

struct nod{
    hufnod *p;
    struct nod *next;
};

// swap two integers
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
// Min-heap class
class Min_Heap
{
int *heaparr; // pointer to array of elements in heap
int capacity; // maximum capacity of min heap
int heap_size; // current heap size
public:
Min_Heap(int cap){
heap_size = 0;
capacity = cap;
heaparr = new int[capacity];
}
// to heapify a subtree with the root at given index
void MinHeapify(int );
int parent(int i) { return (i-1)/2; }
// left child of node i
int left(int i) { return (2*i + 1); }
// right child of node i
int right(int i) { return (2*i + 2); }
// extract minimum element in the heap(root of the heap)
int extractMin();
// decrease key value to newKey at i
void decreaseKey(int i, int newKey);
// returns root of the min heap
int getMin() { return heaparr[0]; }
// Deletes a key at i
void deleteKey(int i);
// Inserts a new key 'key'
void insertKey(int key);
void displayHeap(int n){
for(int i = 0;i<n;i++)
cout<<heaparr[i]<<" ";
cout<<endl;

}
};
// Inserts a new key 'key'
void Min_Heap::insertKey(int key)
{
if (heap_size == capacity) {
cout << "\nOverflow: Could not insertKey\n";
return;
}
// First insert the new key at the end
heap_size++;
int i = heap_size - 1;
heaparr[i] = key;
// Fix the min heap property if it is violated
while (i != 0 && heaparr[parent(i)] > heaparr[i])
{
swap(&heaparr[i], &heaparr[parent(i)]);
i = parent(i);
}
}
void Min_Heap::decreaseKey(int i, int newKey) {
heaparr[i] = newKey;
while (i != 0 && heaparr[parent(i)] > heaparr[i]) {
swap(&heaparr[i], &heaparr[parent(i)]);
i = parent(i);
}
}
int Min_Heap::extractMin()
{
if (heap_size <= 0)
return INT_MAX;
if (heap_size == 1) {
heap_size--;
return heaparr[0];
}
// Store the minimum value,delete it from heap
int root = heaparr[0];
heaparr[0] = heaparr[heap_size-1];
heap_size--;
MinHeapify(0);
return root;
}
void Min_Heap::deleteKey(int i)
{
decreaseKey(i, INT_MIN);
extractMin();
}
void Min_Heap::MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int min = i;
if (l < heap_size && heaparr[l] < heaparr[i])
min = l;
if (r < heap_size && heaparr[r] < heaparr[min])
min = r;
if (min != i)
{

swap(&heaparr[i], &heaparr[min]);
MinHeapify(min);
}
}
int main(){

///Tabloul cu caractere
    char text[]={"de_omnibus_dubitandum_est"};
    ///char text[]={de_omnibus_dubitandum_estx"};
    int Frecv[256]={0},i=0,j=0;
    int n=strlen(text);
    while(i<n){
        /*j=0;while(j<256){if(j==text[i])Frecv[j]+=1; j++;}*/
        Frecv[text[i]] +=1;
        i++;
    }
    struct nod *h=NULL,*q,*r;
    cout<<"Lista (cod simbol, numar de aparitii): "<<endl;
    j=0;
    while(j<256){
        if(Frecv[j]){
            ///caracter ,cod caracter ,numar aparitii
            cout<<(char)j<<"->"<<j<<"->"<<Frecv[j]<<endl;
            if(!h){
                h=new struct nod;
                h->p=new struct hufnod;
                h->p->c=j;
                h->p->frecv=Frecv[j];
                h->p->left=h->p->right=NULL;
                h->next=NULL;
            }else{
                r=new struct nod;
                r->p=new struct hufnod;
                r->p->c=j;
                r->p->frecv=Frecv[j];
                r->p->left=h->p->right=NULL;
                r->next=NULL;
                q=h;
                if(r->p->frecv < q->p->frecv){  /// daca se gaseste o frecventa mai mica
                    r->next=q;
                    h=r;
                }else{
                    while(q->next){             /// inserare intre 2 elemente
                        if(q->next->p->frecv > r->p->frecv)
                            break;
                        q=q->next;
                    }
                    r->next=q->next;
                    q->next=r;
                }
            }
        }
        j++;

    }

    struct nod *nou;

    do{
        q=h;
        struct hufnod *a=q->p;
        struct hufnod *b=q->next->p;
        h=q->next->next;
        nou=new struct nod;
        nou->next=NULL;
        nou->p=new struct hufnod;
       /// cout<<a->frecv<<" "<<b->frecv<<" ";
        nou->p->frecv = a->frecv + b->frecv;
       /// cout<<nou->p->frecv<<" ";
        if(a->frecv == b->frecv){
            nou->p->left=a;
            nou->p->right=b;
        }else{
            if(a->frecv > b->frecv){
                nou->p->left=b;
                nou->p->right=a;
            }else{
                nou->p->left=a;
                nou->p->right=b;
            }
        }
        ///cout<<nou->p->left->frecv;
        ///cout<<" "<<nou->p->right->frecv<<endl;;
       q=h;
       if(q){
           if(nou->p->frecv <= q->p->frecv){
                nou->next=q;
                h=nou;
           }else{
                while(q->next){
                    if(q->next->p->frecv > nou->p->frecv)
                        break;
                    q=q->next;
                }
                nou->next=q->next;
                q->next=nou;
                ///cout<<nou->p->frecv<<" ";
           }
       }
    /// cout<<nou->p->frecv<<"\n";
    }while(nou->p->frecv!=n);
///introducere frecventei de afisare in heap
    ifstream f("date.txt");
Min_Heap h1(51);
for(i=0;i<50;i++)
{f>>Frecv[j];
h1.insertKey(Frecv[j]);
}
///afisarea din heap
cout<<"Heap after insertion:";
h1.displayHeap(12);
system("PAUSE");
    return 0;
}