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