fork(1) download
copy 
  1. #include <iostream>
  2. #define RIGHT(s) 2*s+1
  3. #define LEFT(s) 2*s
  4. using namespace std;
  5.  
  6. class MaxHeap
  7. {
  8. private:
  9. 	int *a;
  10. 	int heapsize;
  11. 	int maxsize;
  12. 	void maxHeapify(int i)
  13. 	{
  14. 		int l=LEFT(i);
  15. 		int r=RIGHT(i);
  16. 		int largest=i;
  17. 		if(l<=heapsize && a[l]>a[i])
  18. 			largest=l;
  19. 		if(r<=heapsize && a[r]>a[largest])
  20. 			largest=r;
  21. 		if(largest!=i)
  22. 		{
  23. 			std::swap(a[i],a[largest]);
  24. 			maxHeapify(largest);
  25. 		}
  26. 	}
  27. public:
  28. 	MaxHeap(int n)
  29. 	{
  30. 		a=new int[n+1];
  31. 		heapsize=0;
  32. 		maxsize=n;
  33. 	}
  34. 	void Insert(int s)
  35. 	{
  36. 		if(heapsize<maxsize)
  37. 		{
  38. 			a[++heapsize]=s;
  39. 			maxHeapify(heapsize);
  40. 		}
  41. 		else
  42. 			cout<<"Heap size exceeded. Can't Insert\n";
  43. 	}
  44. 	int extractMax()
  45. 	{
  46. 		maxHeapify(heapsize);
  47. 		if(!isEmpty())
  48. 		{
  49. 			std::swap(a[1],a[heapsize--]);
  50. 			maxHeapify(1);
  51. 			return a[heapsize+1];
  52. 		}
  53. 		else
  54. 			cout<<"Sorry, Heap Empty\n";
  55. 	}
  56. 	int size()
  57. 	{
  58. 		return heapsize;
  59. 	}
  60. 	bool isEmpty()
  61. 	{
  62. 		if(heapsize==0)
  63. 			return 1;
  64. 		return 0;
  65. 	}
  66. };
  67.  
  68. int main()
  69. {
  70. 	int n;
  71. 	cin>>n;
  72. 	MaxHeap heap(n);
  73. 	for(int i=0;i<n;i++)
  74. 	{
  75. 		int x;
  76. 		cin>>x;
  77. 		heap.Insert(x);
  78. 	}
  79. 	while(!heap.isEmpty())
  80. 		cout<<heap.extractMax()<<endl;
  81. 	return 0;
  82. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
7
9
90
1
2
3
100
101
stdout
copy 
9
101
100
90
3
2
1
https://ideone.com/yIz1vR
language:
C++14 (gcc 8.3)
created:
10 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!