Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<cstdio>
- #include<iostream>
- #define MAX_HEAP_SIZE 100000
- using namespace std;
- class HeapItem
- {
- public:
- char data; //actual data that is stored
- int key; //key value of the data, heap is constructed based on key
- class HeapItem *left;
- class HeapItem *right;
- };
- class MinHeap
- {
- public:
- HeapItem * A; //stores heap items, e.g., nodes
- int heapLength;
- int * map;
- int size;
- MinHeap() //constructor
- {
- A = new HeapItem[MAX_HEAP_SIZE];
- map = new int[MAX_HEAP_SIZE];
- heapLength=0;
- size=0;
- }
- ~MinHeap() //destructor
- {
- if(map) delete [] map;
- if(A) delete [] A;
- map = 0; //set to NULL after deletion
- A = 0; //set to NULL after deletion
- }
- void heapify(int i)
- {
- int l,r,smallest;
- while(1)
- {
- l=2*i; //left child index
- r=2*i+1; //right child index
- smallest=i;
- if(l>heapLength && r>heapLength)
- break; //nothing to do, we are at bottom
- else if(r>heapLength)
- smallest = l;
- else if(l>heapLength)
- smallest = r;
- else if( A[l].key < A[r].key )
- smallest = l;
- else
- smallest = r;
- if(A[i].key <= A[smallest].key)
- break; //we are done heapifying
- else
- {
- //swap nodes with smallest child, adjust map array accordingly
- HeapItem t;
- t=A[i];
- A[i]=A[smallest];
- map[A[i].key]=i;
- A[smallest]=t;
- map[A[smallest].key]=smallest;
- i=smallest;
- }
- }
- }
- void insertItem(char data, int key)
- {
- //Write your codes here
- heapLength++;
- size++;
- A[heapLength].data=data;
- A[heapLength].key=key;
- // buHeapify(heapLength);
- heapify(1);
- }
- HeapItem extract(HeapItem *B){
- HeapItem temp=B[1];
- //temp=B[1];
- B[1]=B[size];
- size--;
- heapLength--;
- heapify(1);
- return temp;
- }
- HeapItem build(){
- HeapItem l,r,root;
- while(heapLength!=1){
- l=extract(A);
- r=extract(A);
- root.key=l.key+r.key;
- root.left=l;
- root.right=r;
- insertItem(root->data,root->key);
- }
- return extract(A);
- }
- void printCodes(HeapItem* root, int arr[], int top)
- {
- // Assign 0 to left edge and recur
- if (root->left)
- {
- arr[top] = 0;
- printCodes(root->left, arr, top + 1);
- }
- // Assign 1 to right edge and recur
- if (root->right)
- {
- arr[top] = 1;
- printCodes(root->right, arr, top + 1);
- }
- // If this is a leaf node, then it contains one of the input
- // characters, print the character and its code from arr[]
- if (!(root->left) && !(root->right))
- {
- printf("%c: ", root->data);
- for(int i=1;i<top;i++)
- printf("%d",arr[top]);
- }
- }
- void printHeap()
- {
- HeapItem* root = build();
- int arr[100], top = 0;
- printCodes(root,arr,top);
- }
- };
- main()
- {
- int n;
- scanf("%d",&n);
- MinHeap heap;
- char ch[100]= {};
- int f[100]= {};
- for(int i=0; i<n; i++)
- {
- cin>>ch[i];
- cin>>f[i];
- heap.insertItem(ch[i],f[i]);
- }
- heap.printHeap();
- // huffman()
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement