Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <climits>
- #include <fstream>
- #include <stdlib.h>
- #include <time.h>
- #include <iostream>
- #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(){
- char text[]={" veni_vidi_vici"};
- 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);
- ifstream f("fisier.txt");
- Min_Heap h1(51);
- for(i=0;i<50;i++)
- {f>>Frecv[j];
- h1.insertKey(Frecv[j]);
- }
- cout<<"Heap after insertion:";
- h1.displayHeap(12);
- int x,y;
- x=h1.extractMin();
- y=h1.extractMin();
- cout<<"Afisare dupa 2 extrageri consecutive a min"<<endl;
- h1.displayHeap(10);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement