그냥 심심해서 구현해본 Heap Sort다. 사실 이게 진짜 Heap Sort인지는 나도 모른다-_-. 그냥 힙에 원소를 모조리 집어넣었다가 다시 모조리 빼면 정렬된 값이 나오니까 그게 정렬아닌가? ㅋㅋ 사용한 자료구조는 배열을 이용한 이진 트리이며, 나중에 이것저것 정렬해보기 위해 템플릿으로 구현하였다.
이 알고리즘의 Time Complexity를 나름 분석해보겠다. 정렬을 할 때 걸리는 시간은 직관적으로 엔트리들을 힙에 삽입하는 시간 T(enQueue)과 힙에서 엔트리를 빼내는 시간 T(deQueue)의 합을 통해 알 수있다.
1. Enqueue
Heap에 엔트리를 추가할 때 사용되는 함수는 enQueue()안에서 호출된 upWard()이다. 부모와 자식을 비교해서 자식이 크면 값을 교환하고 부모의 위치에서 자기 자신을 재귀호출 하는 간단한 함수이다. 참고로 Heap에 새로운 엔트리를 추가할 때 가장 밑에서부터 우선순위를 따지며 위로 올라오며 위치가 바뀌기 때문에 이 과정을 Reheapification Upward라고 한다. (리히피피케이션 업워드 -_-)
InputSize : Size of Array[N], N
Basic Operation : number of call upWard() recursively
Time Complexity : O(N * Log N)
처음에 enQueue()를 통해 배열의 마지막 부분에 엔트리를 삽입하고 그 후부터 upWard()를 이용해서 새로 삽입한 엔트리를 부모와 값을 비교하여 재귀호출을 하게 되는데, worst case가 맨 마지막에서 부터 맨 앞(root)으로 이동하는 경우인데, 이 경우 2진 트리이기 때문에 재귀호출하는 횟수는 밑수가 2인 로그의 N이 된다. 이러한 과정을 N번 되풀이 하니까 O(N * Log N)이 된다.
2. Dequeue
Heap에서 엔트리를 뽑아낼 때(제거할 때) 사용되는 함수는 remove()안에서 호출된 downWard()이다. 가장 첫번째 엔트리(root)를 빼내고, Heap에 저장된 제일 뒤에 위치한 엔트리를 root자리에 복사한 다음 downWard()를 호출하여 자식들보다 작으면 값을 교환하고 자식의 위치에서 재귀호출 하는 함수이다. 이 과정은 Reheapification Downward라고 한다. (리히피피케이션 다운워드 -_-)
InputSize : Size of Array[N], N
Basic Operation : number of call downWard() recursively
Time Complexity : O(N * Log N)
downWard()는 deQueue()함수 안에서 root의 위치에서 부터 시작된다. 즉 downWard(0)부터 호출된다는 말이다. worst case가 root에서부터 가장 아래로(배열의 마지막으로) 내려가는 경우인데, 2진 트리이므로 밑수가 2인 로그의 N이 된다. 이러한 과정을 N번 되풀이 하므로 O(N * Log N)
삽입할 때도 O(N * Log N)이고 빼낼 때도 O(N * Log N)이다.
따라서 이 알고리즘의 최종 Time Complexity는 O(N * Log N)이 되겠다.
전체 소스파일 (왜 이따구로 허접하게 구현했냐? 라고 물어본다면 할 말 없음 -_-ㅗ)
invalid-file
이 알고리즘의 Time Complexity를 나름 분석해보겠다. 정렬을 할 때 걸리는 시간은 직관적으로 엔트리들을 힙에 삽입하는 시간 T(enQueue)과 힙에서 엔트리를 빼내는 시간 T(deQueue)의 합을 통해 알 수있다.
1. Enqueue
Heap에 엔트리를 추가할 때 사용되는 함수는 enQueue()안에서 호출된 upWard()이다. 부모와 자식을 비교해서 자식이 크면 값을 교환하고 부모의 위치에서 자기 자신을 재귀호출 하는 간단한 함수이다. 참고로 Heap에 새로운 엔트리를 추가할 때 가장 밑에서부터 우선순위를 따지며 위로 올라오며 위치가 바뀌기 때문에 이 과정을 Reheapification Upward라고 한다. (리히피피케이션 업워드 -_-)
source code : upWard()
InputSize : Size of Array[N], N
Basic Operation : number of call upWard() recursively
Time Complexity : O(N * Log N)
처음에 enQueue()를 통해 배열의 마지막 부분에 엔트리를 삽입하고 그 후부터 upWard()를 이용해서 새로 삽입한 엔트리를 부모와 값을 비교하여 재귀호출을 하게 되는데, worst case가 맨 마지막에서 부터 맨 앞(root)으로 이동하는 경우인데, 이 경우 2진 트리이기 때문에 재귀호출하는 횟수는 밑수가 2인 로그의 N이 된다. 이러한 과정을 N번 되풀이 하니까 O(N * Log N)이 된다.
2. Dequeue
Heap에서 엔트리를 뽑아낼 때(제거할 때) 사용되는 함수는 remove()안에서 호출된 downWard()이다. 가장 첫번째 엔트리(root)를 빼내고, Heap에 저장된 제일 뒤에 위치한 엔트리를 root자리에 복사한 다음 downWard()를 호출하여 자식들보다 작으면 값을 교환하고 자식의 위치에서 재귀호출 하는 함수이다. 이 과정은 Reheapification Downward라고 한다. (리히피피케이션 다운워드 -_-)
source code : downWard()
InputSize : Size of Array[N], N
Basic Operation : number of call downWard() recursively
Time Complexity : O(N * Log N)
downWard()는 deQueue()함수 안에서 root의 위치에서 부터 시작된다. 즉 downWard(0)부터 호출된다는 말이다. worst case가 root에서부터 가장 아래로(배열의 마지막으로) 내려가는 경우인데, 2진 트리이므로 밑수가 2인 로그의 N이 된다. 이러한 과정을 N번 되풀이 하므로 O(N * Log N)
삽입할 때도 O(N * Log N)이고 빼낼 때도 O(N * Log N)이다.
따라서 이 알고리즘의 최종 Time Complexity는 O(N * Log N)이 되겠다.
전체 소스파일 (왜 이따구로 허접하게 구현했냐? 라고 물어본다면 할 말 없음 -_-ㅗ)
invalid-file
Implementation of Heap Sort with C++