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. /*
  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. 			std::swap(a[max_child], a[(max_child + d - 2) / d]);
  74.  
  75. 		node = j;
  76.  
  77. 	}
  78. }
  79.  
  80. template <class Item>
  81. class PQ{
  82. private:
  83. 	Item *pq;
  84. 	int n;
  85. public:
  86. 	PQ(int max){
  87. 		pq = new Item[max + 1];
  88. 		n = 0;
  89. 	}
  90.  
  91. 	~PQ(){
  92. 		delete[] pq;
  93. 	}
  94.  
  95. 	int empty() const{
  96. 		return n == 0;
  97. 	}
  98.  
  99. 	void insert(Item item){
  100. 		pq[++n] = item;
  101. 		d_ary_fixUp(pq, n);
  102. 	}
  103.  
  104. 	Item getmax(){
  105. 		if(!empty()){
  106. 			std::swap(pq[1], pq[n]);
  107. 			d_ary_fixDown2(pq, 1, n-1);
  108. 			return pq[n--];
  109. 		}else
  110. 			return 0;
  111. 	}
  112. };
  113.  
  114. int main(){
  115. 	PQ<int> pq(50);
  116. 	int p;
  117.  
  118. 	for(int i = 0; i < 10; i++)
  119. 		pq.insert(i);
  120. 	for(int i = 0; i < 10; i++)
  121. 		std::cout << pq.getmax() << " ";
  122. 	std::cin >> p;
  123. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9 7 6 5 4 3 1 2 8 0
https://ideone.com/FbsaMN
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!