백준 2751 수 정렬하기2

백준 2751 수 정렬하기2 문제는 시간복잡도와 관계가 있는 문제이다.

 

일반적인 버블 정렬과 삽입 정렬로는 처리 시간이 오래 걸리기 때문에 좀 더 빠른 알고리즘으로 처리해야한다.

 

그 중에 대표적으로 Heap 정렬이 있다.

 

아래 코드는 Heap 정렬 코드다.

#include <iostream>
#include <vector>
#include <algorithm>

void push_heap(std::vector<int>& heap, int Value) {
	heap.push_back(Value);

	int index = heap.size() - 1;

	while (index > 0 && heap[(index - 1) / 2] < heap[index]) {
		std::swap(heap[index], heap[(index - 1) / 2]);
		index = (index - 1) / 2;
	}
}

void pop_heap(std::vector<int>& heap) {
	heap[0] = heap.back();
	heap.pop_back();
	int here = 0;
	while (true) {
		int left = here * 2 + 1, right = here * 2 + 2;
		if (left >= heap.size()) break;
		int next = here;
		if (heap[next] < heap[left]) next = left;
		if (right < heap.size() && heap[next] < heap[right]) next = right;
		if (next == here) break;
		std::swap(heap[here], heap[next]);
		here = next;
	}
}

void sort_heap(std::vector<int>& heap) {
	for (int count = 1; count < heap.size(); count++) {
		std::swap(heap[heap.size() - count], heap[0]);
		int here = 0;
		while (true) {
			int left = here * 2 + 1, right = here * 2 + 2;
			if (left >= heap.size() - count) break;
			int next = here;
			if (heap[next] < heap[left]) next = left;
			if (right < heap.size() - count && heap[next] < heap[right]) next = right;
			if (next == here) break;
			std::swap(heap[here], heap[next]);
			here = next;
		}
	}
}

int main() {
	int N;
	std::cin >> N;

	std::vector<int> heap;
	for (int i = 0; i < N; i++) {
		int temp;
		std::cin >> temp;
		push_heap(heap, temp);
	}

	sort_heap(heap);

	for (auto content : heap)
		std::cout << content << "\n";

	return 0;
}