fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class heap{
  4. 	vector<int> a;
  5. 	int order;
  6. 	#define l(x) 2*x+1
  7. 	#define r(x) 2*x+2
  8. 	#define p(x) (x-1)/2
  9. 	#define null -INT_MAX
  10. 	public:
  11. 	heap(int x = 0){ order = x; }
  12. 	bool cmp(int x, int y){
  13. 		if (order == 0) return x>y; //min-heap
  14. 		if (order == 1) return x<y; //max-heap
  15. 	}
  16. 	void add(int x){
  17. 		a.push_back(x);
  18. 		go(a.size()-1);
  19. 	}
  20. 	void go(int u){
  21. 		if(u == 0) return;
  22. 		int P = p(u);
  23. 		if(cmp(a[P], a[u])) swap(a[P], a[u]), go(P);
  24. 	}
  25. 	void heapify(int u){
  26. 		int L = l(u), R = r(u), n = a.size();
  27. 		if(L>=n and R>=n) return;
  28. 		int v = (L<n&&R<n)?(cmp(a[R], a[L])?L:R):L;
  29. 		if(cmp(a[u], a[v])) swap(a[u], a[v]), heapify(v);
  30. 	}
  31. 	int extract(){
  32. 		if (a.empty()){
  33. 			cout << "Oops! heap is empty!" << endl;
  34. 			return null;
  35. 		}
  36. 		int ans = a[0];
  37. 		if(a.size() == 1) {
  38. 			a.clear();
  39. 			return ans;
  40. 		}
  41. 		a[0] = a.back();
  42. 		a.pop_back();
  43. 		heapify(0);
  44. 		return ans;
  45. 	}
  46. };
  47.  
  48. int main()
  49. {
  50. 	ios_base::sync_with_stdio(false);
  51. 	cin.tie(NULL);
  52. 	int i,n,k,j;
  53. 	heap H(1); // 1 for max-heap, 0 for min-heap
  54. 	vector<int> a{13, 1, 10, 34, 42, -10};
  55. 	for(int x: a) H.add(x);
  56. 	for(int x: a) cout << H.extract() << " ";
  57. 	return 0;
  58. } 
  59.  
  60.  
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
0 0
stdout
copy 
42 34 13 10 1 -10
https://ideone.com/m1IfEB
my template :)
language:
C++14 (gcc 8.3)
created:
7 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!