fork download 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. void push(vector<int>& heap, int x) {
  7. 	heap.push_back(x);
  8. 	int index = heap.size() - 1;
  9. 	while (index > 0 && heap[index] < heap[(index - 1) / 2]) {
  10. 		swap(heap[index], heap[(index - 1) / 2]);
  11. 		index = (index - 1) / 2;
  12. 	}
  13. }
  14.  
  15. int pop_min(vector<int>& heap) {
  16. 	int value = heap.front();
  17. 	swap(heap.front(), heap.back());
  18. 	heap.pop_back();
  19.  
  20. 	int index = 0;
  21. 	while ((index * 2 + 1 < heap.size() && heap[index] > heap[index * 2 + 1]) ||
  22. 		   (index * 2 + 2 < heap.size() && heap[index] > heap[index * 2 + 2])) {
  23. 		if (index * 2 + 2 < heap.size() && heap[index * 2 + 2] < heap[index * 2 + 1]) {
  24. 			swap(heap[index], heap[index * 2 + 2]);
  25. 			index = index * 2 + 2;
  26. 		} else {
  27. 			swap(heap[index], heap[index * 2 + 1]);
  28. 			index = index * 2 + 1;
  29. 		}
  30. 	}
  31.  
  32. 	return value;
  33. }
  34.  
  35. int main() {
  36. 	vector<int> h;
  37. 	push(h, 5);
  38. 	push(h, 1);
  39. 	push(h, 12);
  40. 	push(h, 7);
  41. 	push(h, 9);
  42. 	cout << pop_min(h) << endl;
  43. 	cout << pop_min(h) << endl;
  44. 	push(h, 8);
  45. 	cout << pop_min(h) << endl;
  46. 	cout << pop_min(h) << endl;
  47. 	cout << pop_min(h) << endl;
  48. 	cout << pop_min(h) << endl;
  49. 	return 0;
  50. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
Standard input is empty
stdout 
1
5
7
8
9
12
https://ideone.com/MRaHHM
language:
C++14 (gcc 8.3)
created:
6 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!