fork download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4.  
  5. int heap[3];
  6.  
  7. void minheapify(int idx)
  8. {
  9. 	int left= 1+ 2*idx;
  10. 	int right = 2+ 2*idx;
  11.  
  12. 	int small,smallpos;
  13.  
  14. 	if(left<3 && heap[left]<heap[idx])
  15. 	 {
  16. 	 	// change the heap[0]
  17. 	 	int temp= heap[idx];
  18. 	 	small=heap[left];
  19. 	 	heap[idx]=small;
  20. 	 	heap[left]=temp;
  21. 	 	smallpos=left;
  22. 	 }
  23. 	 else
  24. 	 {
  25. 	 	// no change in the heap[0] 
  26. 	 	small= heap[idx];
  27. 	 	smallpos=idx;
  28. 	 }
  29.  
  30. 	if(right<3 && heap[right]<small)
  31. 	 {
  32. 	 	// change heap[0]
  33. 	 	int temp= heap[idx];
  34. 	 	small=heap[right];
  35. 	 	heap[idx]= small;
  36. 	 	heap[right]=temp;
  37. 	 	smallpos=right;
  38. 	 }
  39.  
  40. 	 //cout<<small<<" "<<smallpos<<endl;
  41.  
  42. 	if(smallpos!=idx)
  43. 	 minheapify(smallpos);
  44. }
  45.  
  46. int main()
  47. {
  48. 	int n;
  49. 	cin>>n;
  50. 	int a[n+1],i;
  51. 	for(i=0;i<n;i++)
  52. 	 cin>>a[i];
  53.  
  54. 	int ans;
  55.  
  56. 	 // method 1 : simply sort
  57. 	// sort(a,a+n);
  58. 	 //ans= a[n-3];
  59. 	 //cout<<ans<<endl;
  60.  
  61. 	 // create heap of size 3, declared globally for ease
  62.  
  63. 	 heap[0]=a[0];
  64. 	 heap[1]=a[1];
  65. 	 heap[2]=a[2];
  66.  
  67. 	 minheapify(0);
  68.  
  69. 	 // start comparing with other elements 
  70.  
  71. 	 // total complexity is O((n-3)logn(n-3)) 
  72. 	 // upper bound O((n-kl)logk)
  73.  
  74. 	 for(i=3;i<n;i++)
  75. 	 {
  76. 	 	if(a[i]<heap[0])
  77. 	 	{
  78. 	 		// since we have created min heap, there'll not be any effect on heap for any element
  79. 	 		//which is less than the smallest element of the heap
  80. 	 	}
  81. 	 	else
  82. 	 	{
  83. 	 		heap[0]=a[i];
  84. 	 		minheapify(0);  // log(3) or log(k) in general
  85. 	 	}
  86. 	 }
  87.  
  88. 	 /*cout<<"\n the heap now is : ";
  89. 	 for(i=0;i<3;i++)
  90. 	  cout<<heap[i]<<" ";
  91. 	 */
  92. 	 // the third maximum number of the input array is the least element of the heap 
  93. 	 // thus, output is heap[0] 
  94.  
  95. 	 cout<<"Third maximum is : "<<heap[0]<<endl;
  96.  
  97. 	 // for generalisztion i.e. for finding k'th maximum, make the heap of size k and repeat the same thing
  98. 	return 0;
  99. }
Success #stdin #stdout 0s 3144KB
comments (?)
stdin
copy 
8
213 31 12 9429 23 32 41312 132
stdout
copy 
Third maximum is : 213
https://ideone.com/jp3uE8
language:
C++ (gcc 8.3)
created:
9 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!