fork download 
  1. #include <vector>
  2. #include <iostream>
  3. #include <cstdlib>
  4. #include <time.h>
  5. using namespace std;
  6.  
  7. vector<unsigned long long> myArray;
  8. vector<unsigned long long> orig_index;
  9. vector<unsigned long long> new_index;
  10.  
  11. unsigned long long heapify(unsigned long long count) 
  12. {
  13. 	unsigned long long temp, left, right, min;
  14. 	long long j;
  15. 	unsigned long long n_swaps = 0;
  16.  
  17.  
  18. 	for (long long i = (count % 2 ? (count - 2) / 2 : (count - 1) / 2); i >= 0; --i) {
  19. 		left = (2 * i) + 1;
  20. 		right = (2 * i) + 2;
  21.  
  22. 		j = i;
  23. 		while (((myArray.at(j) > myArray.at(left)) && left < count) || ((myArray[j] > myArray.at(right)) && (right < count))) {
  24.  
  25. 			//Swap
  26.  
  27. 			//Find lesser of left or right
  28. 			if (right >= count) {
  29. 				min = myArray[left];
  30. 			}
  31. 			else {
  32. 				min = myArray[left] > myArray[right] ? myArray[right] : myArray[left];
  33. 			}
  34.  
  35. 			if (myArray[j] > myArray[left] && (min == myArray[left])) {
  36. 				temp = myArray[j];
  37. 				myArray[j] = myArray[left];
  38. 				myArray[left] = temp;
  39.  
  40. 				//Update indexes
  41. 				orig_index.push_back(j);
  42. 				new_index.push_back(left);
  43.  
  44. 				j = left;
  45. 				right = (2 * left) + 2;
  46. 				left = (2 * left) + 1;
  47. 				++n_swaps;
  48. 			}
  49. 			else if ((right < count) && (myArray[j] > myArray[right])) {
  50. 				temp = myArray[j];
  51. 				myArray[j] = myArray[right];
  52. 				myArray[right] = temp;
  53.  
  54. 				//Update indexes
  55. 				orig_index.push_back(j);
  56. 				new_index.push_back(right);
  57.  
  58. 				j = right;
  59. 				left = (2 * right) + 1;
  60. 				right = (2 * right) + 2;
  61. 				++n_swaps;
  62. 			}
  63.  
  64. 		}
  65. 	}
  66. 	return n_swaps;
  67. }
  68.  
  69. void generate(unsigned long long count, unsigned long long max) {
  70. 	srand(time(NULL));
  71. 	//Dummy array of max size
  72. 	vector<unsigned long long> dummy;
  73.  
  74. 	//Populate the dummy
  75. 	for (unsigned long long i = 0; i < max; ++i) {
  76. 		dummy.push_back(i);
  77. 	}
  78.  
  79. 	//Select random number from dummy, swap with last and pop
  80. 	unsigned long long temp;
  81. 	unsigned long long swap;
  82. 	unsigned long long dummy_size = max - 1;
  83.  
  84. 	cout << "****************Indices************" << endl;
  85. 	for (unsigned long long i = 0; i < count; ++i) {
  86. 		temp = rand() % dummy_size;
  87. 		myArray.push_back(dummy.at(temp));
  88.  
  89. 		//Swap and pop
  90. 		swap = dummy[temp];
  91. 		dummy[temp] = dummy.at(dummy_size);
  92. 		dummy[dummy_size] = swap;
  93. 		--dummy_size;
  94. 	}
  95. 	cout << "*************End*****************" << endl;
  96. 	dummy.clear();
  97. }
  98.  
  99. int main(void) {
  100.  
  101. 	unsigned long long count = 25000;
  102. 	unsigned long long max = 1000000;
  103.  
  104. 	//Generate random numbers and push on array
  105. 	generate(count, max);
  106.  
  107.  
  108. 	//Build heap
  109. 	unsigned long long n_swaps = heapify(count);
  110.  
  111. 	return 0;
  112. }
Runtime error #stdin #stdout #stderr 0.02s 3972KB
comments (?)
stdin 
Standard input is empty
stdout 
****************Indices************
*************End*****************
stderr 
terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 25000) >= this->size() (which is 25000)
https://ideone.com/V3lJn8
language:
C++14 (gcc 8.3)
created:
9 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!