fork(1) 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. /*
  28. first_child = node * d + 1 - (d - 1)
  29. last_child	= node * d + 1
  30. parent		= (node + d - 2) / d
  31. */
  32. template <class Item>
  33. void d_ary_fixUp(Item a[], int node){
  34. 	while(node > 1 && a[(node + d - 2)/d] < a[node]){
  35. 		std::swap(a[node], a[(node + d - 2)/d]);
  36. 		node = (node + d - 2) / d;
  37. 	}
  38. }
  39.  
  40. template <class Item>
  41. void d_ary_fixDown(Item a[], int node, int n){
  42. 	int first_child = node*d + 1 - (d - 1);
  43. 	int last_child = node*d + 1;
  44. 	int max_child = first_child;	/*Начнем с самого первого*/
  45.  
  46. 	while(d*node <= n){
  47. 		/*Находим максимального потомка*/
  48. 		for(int i = first_child; i <= last_child; i++)
  49. 			if(a[i] > a[max_child])
  50. 				max_child = i;
  51. 		/*Если он больше родителя, меняем их местами*/
  52. 		if(a[max_child] > a[(max_child + d - 2) / d])
  53. 			std::swap(a[max_child], a[(max_child + d - 2) / d]);
  54. 		node = max_child;
  55. 	}
  56. }
  57.  
  58. template <class Item>
  59. void d_ary_fixDown2(Item a[], int node, int n){
  60. 	int first_child = node*d + 1 - (d - 1);
  61. 	int last_child = node*d + 1;
  62. 	int max_child = first_child;	/*Начнем с самого первого*/
  63.  
  64. 	while(node*d + 1 - (d - 1) <= n){
  65. 		int j = node*d + 1 - (d - 1);
  66.  
  67. 		/*Ищем максимального потомка среди всех d потомков узла node*/
  68. 		for(int i = first_child; i <= last_child; i++)
  69. 			if(a[i] > a[max_child])
  70. 				max_child = i;
  71. 		/*Если потомок max_child больше своего родителя, то меняем их местами*/
  72. 		//if(a[max_child] > a[(max_child + d - 2) / d])
  73. 		if(a[max_child] > a[node])
  74. 			std::swap(a[max_child], a[node]);
  75.  
  76. 		node = max_child;
  77. 		first_child = node*d + 1 - (d - 1);
  78. 		last_child = node*d + 1;
  79. 	}
  80. }
  81.  
  82. template <class Item>
  83. class PQ{
  84. private:
  85. 	Item *pq;
  86. 	int n;
  87. public:
  88. 	PQ(int max){
  89. 		pq = new Item[max + 1];
  90. 		n = 0;
  91. 	}
  92.  
  93. 	~PQ(){
  94. 		delete[] pq;
  95. 	}
  96.  
  97. 	int empty() const{
  98. 		return n == 0;
  99. 	}
  100.  
  101. 	void insert(Item item){
  102. 		pq[++n] = item;
  103. 		d_ary_fixUp(pq, n);
  104. 		/*Выводим состояние массива*/
  105. 		std::cout << std::endl;
  106. 		for(int i = 1; i <= n; i++)
  107. 			std::cout << pq[i] << " ";
  108. 		std::cout << std::endl;
  109. 	}
  110.  
  111. 	Item getmax(){
  112. 		if(!empty()){
  113. 			std::swap(pq[1], pq[n]);
  114. 			d_ary_fixDown2(pq, 1, n-1);
  115. 			return pq[n--];
  116. 			/*Выводим состояние массива*/
  117. 			std::cout << std::endl;
  118. 			for(int i = 1; i <= n; i++)
  119. 				std::cout << pq[i] << " ";
  120. 			std::cout << std::endl;
  121. 		}else
  122. 			return 0;
  123. 	}
  124. };
  125.  
  126. int main(){
  127. 	PQ<int> pq(50);
  128. 	int p;
  129.  
  130. 	for(int i = 0; i < 10; i++)
  131. 		pq.insert(i);
  132. 	for(int i = 0; i < 10; i++)
  133. 		std::cout << pq.getmax() << " ";
  134. 	std::cin >> p;
  135. }
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 

1 0 

2 0 1 

3 0 1 2 

4 3 1 2 0 

5 4 1 2 0 3 

6 5 1 2 0 3 4 

7 5 6 2 0 3 4 1 

8 5 7 2 0 3 4 1 6 

9 5 8 2 0 3 4 1 6 7 
7 6 9 4 3 8 2 1 5 0
https://ideone.com/BRympO
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!