fork download
copy 
  1. #include <iostream>
  2.  
  3. const int d = 3;	/*Арность кучи*/
  4.  
  5. /*Реализация функций перестроения бинарной кучи*/
  6. template <class Item>
  7. void fixUp(Item a[], int node){
  8. 	while(node > 1 && a[node/2] < a[node]){
  9. 		std::swap(a[node], a[node/2]);
  10. 		node = node / 2;
  11. 	}
  12. }
  13.  
  14. template <class Item>
  15. void fixDown(Item a[], int node, int n){
  16. 	while(2*node <= n){
  17. 		int j = 2*node;
  18.  
  19. 		if(j < n && a[j] < a[j + 1]) j++;
  20. 		if(!(a[node] < a[j])) break;
  21. 		std::swap(a[node], a[j]);
  22. 		node = j;
  23. 	}
  24. }
  25.  
  26. /*Реализация функций перестроения d-арной кучи*/
  27. template <class Item>
  28. void d_ary_fixUp(Item a[], int node){
  29. 	while(node > 1 && a[(node + d - 2)/d] < a[node]){
  30. 		std::swap(a[node], a[(node + d - 2)/d]);
  31. 		node = (node + d - 2) / d;
  32. 	}
  33. }
  34.  
  35. template <class Item>
  36. void d_ary_fixDown(Item a[], int node, int n){
  37. 	int first_child = node*d + 1 - (d - 1);
  38. 	int last_child = node*d - 1;
  39. 	int max_child = first_child;	/*Начнем с самого первого*/
  40.  
  41. 	while(d*node <= n){
  42. 		/*Находим максимального потомка*/
  43. 		for(int i = first_child; i <= last_child; i++)
  44. 			if(a[i] > a[max_child])
  45. 				max_child = i;
  46. 		/*Если он больше родителя, меняем их местами*/
  47. 		if(a[max_child] > a[(max_child + d - 2) / d])
  48. 			std::swap(a[max_child], a[(max_child + d - 2) / d]);
  49. 		node = max_child;
  50. 	}
  51. }
  52.  
  53. template <class Item>
  54. class PQ{
  55. private:
  56. 	Item *pq;
  57. 	int n;
  58. public:
  59. 	PQ(int max){
  60. 		pq = new Item[max + 1];
  61. 		n = 0;
  62. 	}
  63.  
  64. 	~PQ(){
  65. 		delete[] pq;
  66. 	}
  67.  
  68. 	int empty() const{
  69. 		return n == 0;
  70. 	}
  71.  
  72. 	void insert(Item item){
  73. 		pq[++n] = item;
  74. 		d_ary_fixUp(pq, n);
  75. 	}
  76.  
  77. 	Item getmax(){
  78. 		if(!empty()){
  79. 			std::swap(pq[1], pq[n]);
  80. 			d_ary_fixDown(pq, 1, n-1);
  81. 			return pq[n--];
  82. 		}else
  83. 			return 0;
  84. 	}
  85. };
  86.  
  87. int main(){
  88. 	PQ<int> pq(50);
  89. 	int p;
  90.  
  91. 	for(int i = 0; i < 10; i++)
  92. 		pq.insert(i);
  93. 	for(int i = 0; i < 10; i++)
  94. 		std::cout << pq.getmax() << " ";
  95. 	std::cin >> p;
  96. }
Time limit exceeded #stdin #stdout 5s 3408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XXZnF8
language:
C++ (gcc 8.3)
created:
8 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!