fork(1) download
copy 
  1. #include <iostream>
  2.  
  3. #define 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 - 1)/d] < a[node]){
  30. 		std::swap(a[node], a[(node - 1)/d]);
  31. 		node = (node - 1) / d;
  32. 	}
  33. }
  34.  
  35. template <class Item>
  36. void d_ary_fixDown(Item a[], int node, int n){
  37. 	while(d*node <= n){
  38. 		int j = d*node;
  39.  
  40. 		if(j < n && a[j] < a[j + 1]) j++;
  41. 		if(!(a[node] < a[j])) break;
  42. 		std::swap(a[node], a[j]);
  43. 		node = j;
  44. 	}
  45. }
  46.  
  47. template <class Item>
  48. class PQ{
  49. private:
  50. 	Item *pq;
  51. 	int n;
  52. public:
  53. 	PQ(int max){
  54. 		pq = new Item[max + 1];
  55. 		n = 0;
  56. 	}
  57.  
  58. 	~PQ(){
  59. 		delete[] pq;
  60. 	}
  61.  
  62. 	int empty() const{
  63. 		return n == 0;
  64. 	}
  65.  
  66. 	void insert(Item item){
  67. 		pq[++n] = item;
  68. 		d_ary_fixUp(pq, n);
  69. 	}
  70.  
  71. 	Item getmax(){
  72. 		if(!empty()){
  73. 			std::swap(pq[1], pq[n]);
  74. 			d_ary_fixDown(pq, 1, n-1);
  75. 			return pq[n--];
  76. 		}else
  77. 			return 0;
  78. 	}
  79. };
  80.  
  81. int main(){
  82. 	PQ<int> pq(50);
  83. 	int p;
  84.  
  85. 	for(int i = 0; i < 10; i++)
  86. 		pq.insert(i);
  87. 	for(int i = 0; i < 10; i++)
  88. 		std::cout << pq.getmax() << " ";
  89. 	std::cin >> p;
  90. }
Success #stdin #stdout 0s 3416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5 8 6 2 1 4 3 0 0 7
https://ideone.com/PgFn3V
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!