Miscellaneous/Heap Sort.cpp at master · iCoder0020/Miscellaneous · 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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
/*
Heap Sort
O(N*logN)
*/

#include <bits/stdc++.h>

using namespace std;

#define parent(temp) (temp-1)/2
#define left_child(temp) 2*temp + 1
#define right_child(temp) 2*temp + 2

vector <int> heap;

void switch_places(int i, int j)
{
	int temp = heap[i];
	heap[i] = heap[j];
	heap[j] = temp;
}

void heap_insert(int num)
{
	heap.push_back(num);
	int pos = heap.size()-1;
	while(heap[pos] < heap[parent(pos)])
	{
		switch_places(pos, parent(pos));
		pos = parent(pos);
	}
}

int heap_extract()
{
	int ans = heap.front();
	heap[0] = heap.back();
	heap.pop_back();
	int pos = 0;
	while(1)
	{
		if(left_child(pos) < heap.size() && right_child(pos) < heap.size())
		{
			if(heap[pos]>heap[left_child(pos)] || heap[pos]>heap[right_child(pos)])
			{
				if(heap[left_child(pos)] <= heap[right_child(pos)])
				{
					switch_places(pos, left_child(pos));
					pos = left_child(pos);
				}
				else
				{
					switch_places(pos, right_child(pos));
					pos = right_child(pos);
				}
			}
			else
			{
				break;
			}
		}
		else if(left_child(pos) < heap.size())
		{
			if(heap[pos]>heap[left_child(pos)])
			{
				switch_places(pos, left_child(pos));
				pos = left_child(pos);
			}
			else
			{
				break;
			}
		}
		else if(right_child(pos) < heap.size())
		{
			if(heap[pos]>heap[right_child(pos)])
			{
				switch_places(pos, right_child(pos));
				pos = right_child(pos);
			}
			else
			{
				break;
			}
		}
		else
		{
			break;
		}
	}
	return ans;
}

int main()
{
	int N;
	int temp;
	cin>>N;
	while(N--)
	{
		cin>>temp;
		heap_insert(temp);
	}
	vector<int> v;
	while(heap.size()!=0)
	{
		v.push_back(heap_extract());
	}
	for(auto it = v.begin(); it!=v.end(); it++)
	{
		cout<<*it<<" ";
	}
	cout<<endl;
	return 0;
}