fork download
copy 
  1. #include <iostream>
  2. #include <iterator>
  3. #include <stdexcept>
  4. #include <vector>
  5.  
  6. template <typename T>
  7. void print(const std::vector<T>& arr) {
  8. 	copy(arr.begin(), arr.end(), std::ostream_iterator<T>(std::cout, ", "));
  9. 	std::cout << std::endl;
  10. }
  11.  
  12. template <typename T>
  13. void heapify(size_t index, std::vector<T>& heap) {
  14. 	if (heap.size() <= 1)
  15. 		return;
  16. 	size_t moveTo = index;
  17. 	std::cout << index << ": ";
  18.  
  19. 	if (2 * index + 1 < heap.size() && heap[moveTo] > heap[2 * index + 1]) {
  20. 		moveTo = 2 * index + 1;
  21. 	}
  22.  
  23. 	if (2 * index + 2 < heap.size() && heap[moveTo] > heap[2 * index + 2]) {
  24. 		moveTo = 2 * index + 2;
  25. 	}
  26.  
  27. 	if (index != moveTo) {
  28. 		std::swap(heap[index], heap[moveTo]);
  29. 		heapify(moveTo, heap);
  30. 	}
  31. }
  32.  
  33. template <typename T>
  34. T extract_min(std::vector<T>& heap) {
  35. 	if (heap.empty())
  36. 		throw std::out_of_range("Out");
  37.  
  38. 	T res = heap[0];
  39. 	std::swap(heap[0], heap[heap.size() - 1]);
  40. 	heap.pop_back();
  41. 	heapify(0, heap);
  42. 	return res;
  43. }
  44.  
  45. int main() {
  46. 	std::vector<int> arr = {1, 10, 23, -5, -2, 0, 2, -100, -400, 3, -500, 10000};
  47. 	for (size_t i = arr.size() / 2; ~i; --i) {
  48. 		heapify(i, arr);
  49. 	}
  50. 	print(arr);
  51. 	std::vector<int> res;
  52. 	for (size_t i = 0; i < arr.size(); ++i) {
  53. 	//	res.push_back(extract_min(arr));
  54. 	}
  55. 	//print(res);
  56. 	return 0;
  57. }
Success #stdin #stdout 0s 3428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
6: 5: 4: 10: 3: 8: 2: 5: 1: 4: 10: 0: 1: 3: 7: -500, -400, 0, -100, -2, 23, 2, 1, -5, 3, 10, 10000,
https://ideone.com/CrlMt5
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!