Workspace/heaps.cpp at master · gods-mack/Workspace · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

// HEAP

#include<iostream>
#include<bits/stdc++.h>
using namespace std;


void max_heapify(vector<int> &a,int i,int n){


	int tmp = a[i];
	int j = 2*i; // assign j to left node

	while(j <= n){
		if(j < n and a[j+1]>=a[i]){
			j = j + 1;
		}
		if(tmp > a[j]){  // if already max
			break;
		}
		else if(tmp <= a[j]){
			a[j/2] = a[j];
			j = 2 * j;
		}

	}
	a[j/2]  = tmp;
	return ;

} // end of function

void min_heapify(vector<int> &a,int i,int n){


	int tmp = a[i];
	int j = 2*i; // assign j to left node

	while(j <= n){
		if(j < n and a[j+1] <= a[i]){
			j = j + 1;
		}
		if(tmp < a[j]){  // if already max
			break;
		}
		else if(tmp >= a[j]){
			a[j/2] = a[j];
			j = 2 * j;
		}

	}
	a[j/2]  = tmp;
	return ;

} // end of function min_heapify


void max_heap(vector<int> &a,int n){
	//int n = a.size()-1;
	for(int i = n/2 ;i>=1; i--){
		max_heapify(a,i,n);
	}

}

void min_heap(vector<int> &a,int n){
	for(int i=n/2; i>=1; i--){
		min_heapify(a,i,n);
	}
}


int main(){
	int n;
	cin>>n;
	vector<int> a(n+1);
	for(int i=1; i<=n; i++){
		cin>>a[i];
	}

	max_heap(a,n);
	min_heap(a,n);

	cout<<"after operations"<<endl;
	for(int i=1; i<=n; i++){
		cout<<a[i]<<" ";
	}


}