fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. using std::vector;
  3. using std::swap;
  4.  
  5. template <class T>
  6. class heap {
  7. public:
  8. 	int size() {
  9. 		return n;
  10. 	}
  11. 	int top() {
  12. 		return h[0];
  13. 	}
  14. 	bool empty() {
  15. 		return n == 0;
  16. 	}
  17. 	void push(T a) {
  18. 		h.push_back(a);
  19. 		SiftUp(n);
  20. 		n++;
  21. 	}
  22. 	void pop() {
  23. 		n--;
  24. 		swap(h[n], h[0]);
  25. 		h.pop_back();
  26. 		SiftDown(0);
  27. 	}
  28. 	void clear() {
  29. 		h.clear();
  30. 		n = 0;
  31. 	}
  32. 	T operator [] (int a) {
  33. 		return h[a];
  34. 	}
  35. private:
  36. 	vector<T> h;
  37. 	int n = 0;
  38. 	void SiftUp(int a) {
  39. 		while (a) {
  40. 			int p = (a - 1) / 2;
  41. 			if (h[p] > h[a]) swap(h[p], h[a]);
  42. 			else break;
  43. 			a--; a /= 2;
  44. 		}
  45. 	}
  46. 	void SiftDown(int a) {
  47. 		while (2 * a + 1 < n) {
  48. 			int l = 2 * a + 1, r = 2 * a + 2;
  49. 			if (r == n) {
  50. 				if (h[l] < h[a]) swap(h[l], h[a]);
  51. 				break;
  52. 			}
  53. 			else if (h[l] <= h[r]) {
  54. 				if (h[l] < h[a]) {
  55. 					swap(h[l], h[a]);
  56. 					a = l;
  57. 				}
  58. 				else break;
  59. 			}
  60. 			else if (h[r] < h[a]) {
  61. 				swap(h[r], h[a]);
  62. 				a = r;
  63. 			}
  64. 			else break;
  65. 		}
  66. 	}
  67. };
  68. void heapsort(int* l, int* r) {
  69. 	heap<int> h;
  70. 	for (int *i = l; i < r; i++) h.push(*i);
  71. 	for (int *i = l; i < r; i++) {
  72. 		*i = h.top();
  73. 		h.pop();
  74. 	}
  75. }
  76.  
  77.  
  78. unsigned rnd = 0;
  79. int myrandom() {
  80. 	rnd = rnd * 1664525u + 1013904223u;
  81. 	return int(rnd >> 2);
  82. }
  83.  
  84. int const N = 10000000;
  85. int a[N], b[N];
  86.  
  87. int main () {
  88. 	for (int i=0; i<N; ++i)
  89. 		a[i] = b[i] = myrandom();
  90.  
  91. 	double t1 = clock();
  92. 	heapsort(a, a+N);
  93. 	t1 = (clock()-t1)/CLOCKS_PER_SEC;
  94.  
  95. 	double t2 = clock();
  96. 	std::make_heap(b, b+N);
  97. 	std::sort_heap(b, b+N);
  98. 	t2 = (clock()-t2)/CLOCKS_PER_SEC;
  99.  
  100. 	std::cout << t1 << '\n' << t2 << '\n';
  101. }
Success #stdin #stdout 4.38s 93376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2.29051
2.07506
https://ideone.com/BRV0KK
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!