[Algorithm]힙정렬 알고리즘(C++)
힙정렬은 시간복잡도가 nlogn 으로 퀵정렬과 병합(합병)정렬과 같은 시간복잡도를 가진 정렬 알고리즘이다. 하지만 병합정렬과는 다르게 추가적인 메모리가 필요하지않고, 항상 nlogn의 정렬 성능을 보여주기때문에 최악의 경우 n^2 의 성능을 보이는 퀵정렬보다 안정적인 성능을 보인다. 힙정렬은 힙의 구조에 대해 알고있으면 생각보다 간단한 정렬이다. 힙정렬을 알아보기전에 힙(Heap) 에 대해 간단히 알아보자. 힙(Heap)힙 트리 라고도 하는 힙은 완전이진트리 형태의 자료구조이다. 완전이진트리노드를 삽일할때 왼쪽부터 차례대로 추가하는 이진트리(모든 노드의 차수가 2이하로 구성된 트리) 위와같은 트리가 완전이진트리이며(각노드의 왼쪽부터 채워진 이진트리) 아래는 그냥 이진트리. 힙에는 최소힙과 최대힙이 있으며..
