728x90
힙정렬
-
[알고리즘] 힙정렬 (Heap Sort) - C/C++알고리즘/알고리즘 구현 2021. 3. 7. 16:04
힙정렬 (Heap Sort) 1. 기본동작 1) 모든 노드를 순회하면서, 현재 노드를 기준으로 위쪽으로 올라가며 Heapify 한다. 2) 루트 값을 가장 뒤쪽으로 보내고 Heapify 하며 크기를 줄여간다. 2. 시간복잡도 : O(N * log N) 3. 구현 - BOJ 의 11650번 좌표정렬하기를 힙정렬을 직접 구현하여 풀었습니다. (www.acmicpc.net/problem/11650) - 아래 heapSort 코드는 SWEA(swexpertacademy.com/main/visualcode/main.do#/home/mainlayout) 에서 Priority Queue의 레퍼런스 코드를 참고하여 구현하였습니다. #include struct Node { int x, y; } heap[100001]; ..