Advertisement
Guest User

Untitled

a guest
May 22nd, 2017
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.78 KB | None | 0 0
  1. #include<cstdio>
  2. #include<iostream>
  3. #define MAX_HEAP_SIZE 100000
  4. using namespace std;
  5.  
  6.  
  7.  
  8. class HeapItem
  9. {
  10. public:
  11. char data; //actual data that is stored
  12. int key; //key value of the data, heap is constructed based on key
  13. class HeapItem *left;
  14. class HeapItem *right;
  15. };
  16.  
  17. class MinHeap
  18. {
  19.  
  20. public:
  21. HeapItem * A; //stores heap items, e.g., nodes
  22. int heapLength;
  23. int * map;
  24. int size;
  25. MinHeap() //constructor
  26. {
  27. A = new HeapItem[MAX_HEAP_SIZE];
  28. map = new int[MAX_HEAP_SIZE];
  29. heapLength=0;
  30. size=0;
  31. }
  32.  
  33. ~MinHeap() //destructor
  34. {
  35. if(map) delete [] map;
  36. if(A) delete [] A;
  37. map = 0; //set to NULL after deletion
  38. A = 0; //set to NULL after deletion
  39. }
  40.  
  41. void heapify(int i)
  42. {
  43. int l,r,smallest;
  44. while(1)
  45. {
  46. l=2*i; //left child index
  47. r=2*i+1; //right child index
  48. smallest=i;
  49.  
  50. if(l>heapLength && r>heapLength)
  51. break; //nothing to do, we are at bottom
  52. else if(r>heapLength)
  53. smallest = l;
  54. else if(l>heapLength)
  55. smallest = r;
  56. else if( A[l].key < A[r].key )
  57. smallest = l;
  58. else
  59. smallest = r;
  60.  
  61. if(A[i].key <= A[smallest].key)
  62. break; //we are done heapifying
  63. else
  64. {
  65. //swap nodes with smallest child, adjust map array accordingly
  66. HeapItem t;
  67. t=A[i];
  68. A[i]=A[smallest];
  69. map[A[i].key]=i;
  70. A[smallest]=t;
  71. map[A[smallest].key]=smallest;
  72. i=smallest;
  73. }
  74.  
  75. }
  76. }
  77.  
  78.  
  79.  
  80. void insertItem(char data, int key)
  81. {
  82. //Write your codes here
  83. heapLength++;
  84. size++;
  85. A[heapLength].data=data;
  86. A[heapLength].key=key;
  87. // buHeapify(heapLength);
  88. heapify(1);
  89.  
  90.  
  91. }
  92.  
  93. HeapItem extract(HeapItem *B){
  94.  
  95. HeapItem temp=B[1];
  96. //temp=B[1];
  97. B[1]=B[size];
  98. size--;
  99. heapLength--;
  100. heapify(1);
  101. return temp;
  102.  
  103.  
  104. }
  105.  
  106. HeapItem build(){
  107. HeapItem l,r,root;
  108. while(heapLength!=1){
  109. l=extract(A);
  110. r=extract(A);
  111.  
  112. root.key=l.key+r.key;
  113. root.left=l;
  114. root.right=r;
  115. insertItem(root->data,root->key);
  116. }
  117. return extract(A);
  118.  
  119. }
  120.  
  121. void printCodes(HeapItem* root, int arr[], int top)
  122. {
  123. // Assign 0 to left edge and recur
  124. if (root->left)
  125. {
  126. arr[top] = 0;
  127. printCodes(root->left, arr, top + 1);
  128. }
  129.  
  130. // Assign 1 to right edge and recur
  131. if (root->right)
  132. {
  133. arr[top] = 1;
  134. printCodes(root->right, arr, top + 1);
  135. }
  136.  
  137. // If this is a leaf node, then it contains one of the input
  138. // characters, print the character and its code from arr[]
  139. if (!(root->left) && !(root->right))
  140. {
  141. printf("%c: ", root->data);
  142. for(int i=1;i<top;i++)
  143. printf("%d",arr[top]);
  144. }
  145. }
  146.  
  147.  
  148.  
  149. void printHeap()
  150. {
  151. HeapItem* root = build();
  152. int arr[100], top = 0;
  153. printCodes(root,arr,top);
  154. }
  155.  
  156.  
  157.  
  158. };
  159.  
  160.  
  161.  
  162.  
  163.  
  164. main()
  165. {
  166.  
  167. int n;
  168. scanf("%d",&n);
  169. MinHeap heap;
  170. char ch[100]= {};
  171. int f[100]= {};
  172. for(int i=0; i<n; i++)
  173. {
  174. cin>>ch[i];
  175. cin>>f[i];
  176. heap.insertItem(ch[i],f[i]);
  177.  
  178. }
  179. heap.printHeap();
  180. // huffman()
  181.  
  182. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement