fork download
copy 
  1. // in c++ object is equivalent to pointer keep this in mind so when creating object with
  2. //new keyword keep in mind it will return a pointer
  3. #include<bits/stdc++.h>
  4. #define ull unsigned long long
  5. #define pb push_back
  6. #define mp make_pair
  7. using namespace std;
  8. typedef pair<int,int> pii;
  9. typedef vector<int> vi;
  10.  
  11. struct node
  12. {
  13. 	pair<int,char> p;
  14. 	node *l,*r;
  15. 	node(char c,int freq)
  16. 	{
  17. 		l=r=NULL;
  18. 		this->p.first=freq;
  19. 		this->p.second=c;
  20. 	}
  21. };
  22.  
  23. struct compare
  24. {
  25. 	bool operator()(node *a,node *b)
  26. 	{
  27. 		return (a->p.first > b->p.first);
  28. 	}
  29. };
  30. void printCodes(node* root, string str)
  31. {
  32.     if (!root)
  33.         return;
  34.  
  35.     if (root->p.second != '$')
  36.         cout << root->p.second << ": " << str << "\n";
  37.  
  38.     printCodes(root->l, str + "0");
  39.     printCodes(root->r, str + "1");
  40. }
  41. int main()
  42. {
  43. 	ios::sync_with_stdio(false);
  44. 	//cin.tie(NULL);
  45. 	cout<<"Enter No of characters: ";
  46. 	int n,freq;
  47. 	char c;
  48. 	cin>>n;
  49. 	cout<<"Enter chars along with their frequencies: \n";
  50. 	priority_queue<node*,vector<node* >,compare> pq;
  51. 	for(int i=0;i<n;i++)
  52. 	{
  53. 		cin>>c>>freq;
  54. 		pq.push(new node(c,freq));
  55. 	}
  56. 	node* t=new node('$',0);
  57. 	while(pq.size()!=1)
  58. 	{
  59. 		t->l=pq.top();
  60. 		pq.pop();
  61. 		t->r=pq.top();
  62. 		pq.pop();
  63. 		t->p.first= t->l->p.first + t->r->p.first;
  64. 		pq.push(t);
  65. 	}
  66. 	//cout<<"SuccessFull insertion:)";
  67. 	printCodes(pq.top(),"");
  68. }
  69.  
Time limit exceeded #stdin #stdout 5s 4853760KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Enter No of characters:
https://ideone.com/VpcqgJ
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!