[algorithm] 알고리즘 03 : 정렬알고리즘 - [2] 힙정렬
자바로 쉽게 배우는 알고리즘 - part 3 - 1 : 정렬알고리즘 - 힙 정렬
참조 변형
책에 있는 코드를 구현해 보았지만 계속 무한루핑이 돌아 인터넷에 있는 코드를 대신한다.
- 책에 있는 코드 대신 참조한 힙정렬 코드 출처 : https://velog.io/@youswim96/%ED%9E%99-%EC%A0%95%EB%A0%ACHeap-sort-%EC%9E%90%EB%B0%94JAVA
- 힙에 대한 설명 참조 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
우선순위 큐
- 우선순위 큐를 구현하는데 적합한 자료구조
- 우선순위 큐는 큐와 유사하나 항목들이 추가되고 처리되는 순서가 우선 순위에 따라 정해짐
- 우선순위 큐의 연산
- 우선순위가 가장 높은 항목을 검색한다 (FindMax)
- 우선순위가 가장 높은 항목을 제거한다 (DeleteMax)
- 새로운 항목을 추가한다 (Insert)
힙
- 이러한 우선순위 큐의 연산들을 효율적으로 구현한 자료 구조가 바로 힙
- 힙은 “힙 조건”을 만족시키는 “완전 이진 트리”
-> 완전 이진 트리는 마지막 층에 있는 노드들이 왼쪽부터 오른쪽으로 중간에 비지 않고 채워진 트리 - 힙 조건의 종류
-> 힙의 종류에 따라 힙 조건이 나뉩- 최소 힙 (조건) : 트리의 각 노드의 값이 자식 노드들의 값보다 작은 경우
- 최대 힙 (조건) : 트리의 각 노드의 값이 자식 노드들의 값도다 큰 경우
- 힙의 성질
- n개의 노드를 가진 힙은 정확히 하나만 있고 그 힙(트리)의 높이는 [$\log_{2}{N}$]
- 힙의 루트 노드는 항상 최댓값을 저장한다.
- 힙의 한 노드와 그 노드의 자손 노드들로 이루어진 부분트리도 힙이다.
- 힙의 구현
- 힙을 저장하는 표준적인 자료구조는 배열이다.
구현을 쉽게 하기 위하여 배열의 첫번째 인덱스인 0은 사용되지 않는다.
(보통 배열의 첫 값은 지수가 포함 되나, 나는 귀찮아서 포함 시킴 그로인한 로직 변경 발생함)- 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
ex) 예를 들어 ROOT 노드의 오른쪽 노드 번호는 항상 3이다. - 힙에서의 부모노드와 자식 노드의 관계
- 왼쪽 자식의 인덱스 = (부모의 인덱스)*2
- 오른쪽 자식의 인덱스 = (부모의 인덱스)*2+1 → 이 값이 있는 경우 이진트리 구조
- 부모의 인덱스 = (자식의 인덱스)/2 … 여기서 나머지는 무시
- 리프노드의 시작 지점은 : n/2 + 1 (소숫점 없음, 나머지 무시)
- 구조노드의 마지막 지점은 : n/2 (소숫점 없음, 나머지 무시)
힙 정렬
- 힙정렬 단계
1단계. 주어진 배열에 대해 힙을 구성한다.
2단계. (남은) 힙에서 루트 노드(최대값)을 제거한다. (n-1)번 수행 - 힙 정렬 알고리즘의 일반화시켜 적용
- 주어진 배열을 힙(힙 조건을 만족시키는 완전 이진트리)으로 만든다.
- 다음을 (n-1)번 반복한다.
2.1. 힙에서 최대값을 제거한다.(힙의 루트 노드의 값을 마지막 노드의 값과 교환한다.)
2.2. 트리에서 마지막 노드를 제거한다.
2.3. 남은 트리를 힙으로 만든다.
- 힙 정렬 알고리즘의 골격
- A[1 .. n] 을 힙으로 만든다.
- eh = n
- while(eh>1) {
3.1. A[1]과 A[eh]의 값을 교환한다.
3.2. eh = eh -1
3.3. A[1 .. eh]를 힙으로 만든다.
}
-
생성 소스 참조 : https://github.com/chrisna2/AlgorithmWithJava/blob/master/src/part3/heap/HeapSortDebug.java
- Debug log
- 내가 잘못한 것 : findLarger 메서드의 조건을 잘못 봤다. 자식노드가 1개인 것과 2개인 것을 나누는 기준이 상위 비교 조건으로 들어 갔어야 했는데 자식노드가 1개인 조건을 2개인 조건안에 넣어 놨다. 해당 조건을 상위 조건으로 옮기고 수정.
- 이 책에서 잘못된 것 : findLarger 의 리턴 값 y의 값의 초기화 값이 0으로 설정 된 것, 아래의 조건들이 모든 경우의 수를 포함하지 않으며 해당 경우의 수를 벗어나면 리턴 값이 0으로 고정이 되어 무한 루핑이 돌게된다. 따라서 해당 y의 값의 초기 값을 부모 노드의 인덱스 값으로 설정함.
- 애매한 것 : 근본적으로 해당 테스트로 생성된 힙 배열의 경우 첫번째 값은 비워 둔다. 힙구조의 배열의 경우 인덱스의 첫번째 값(0)은 비워 둔다. 그런데 나 같은 경우 배열의 첫번째 값 까지 알뜰하게 써먹다 보니 에러가 발생함 (사실, 2번의 결함도 그로인한 에러인 것 같다.) 테스트 데이터를 바꾸는 것이 답일수도 있으나, heapSort, buildHeap 메서드의 root 노드의 값을 1이 아닌 0으로 설정하고, 메서드에 사용된 1의 값들을 모두 0으로 변경하여 처리함
- 생성 결과
힙 정렬 전 => 423 178 449 412 488 211 68 159 255 371 286 59 413 373 291
=========================================================================
힙 전환 배열 =>
488
449 423
413 371 286 412
291 255 178 211 59 68 373 159
=========================================================================
힙 정렬 후 =>
59
68 159
178 211 255 286
291 371 373 412 413 423 449 488
힙 정렬의 효용성
- 힙 정렬은 1단계 힙 구성 단계와 2단계 힙 정렬 단계 각각 개별의 연산을 수행한다.
- 1단계 힙 구성 단계에서 최악의 경우, 각 노드의 최대힙조건을 구성하기 위해서 다음과 같은 연산을 수행함.
2(n - $\log{(n+1)}$) ∈ θ(n) (1차 지수 시간복잡도.) - 2단계 힙 정렬 단계에서는 최대값을 (n-1)번 재거 하고 최대값을 한번 재거 할때 마다 트리를 다시 힙으로 만들기 위해 최악의 경우 루트노드를 O(h)만큼 아래 층으로 내려 보내야 한다. 따라서 최악의 경우 O(n $\log{n}$) 복잡도를 가짐
- 따라서 힙정렬의 최악 시간 복잡도는 O(n $\log{n}$)
- 힙 정렬은 추가 메모리 공간을 사용하지 않기 때문에 공간복잡도가 적다. (지수 끼리만 변경)
- 1단계 힙 구성 단계에서 최악의 경우, 각 노드의 최대힙조건을 구성하기 위해서 다음과 같은 연산을 수행함.
※ 알고리즘 공부의 방향성 찾기
- 다음 부터는 공부 할때 항상 노트랑 팬을 들고 공부를 하자.
- 10분 고민 뒤 바로 생각안나면 찾아보자 (나는 쌓여 있는게 없다. 시간도 부족하다.)
- 근데 아무리 생각해 봐도 이 책은 수준이 좀 높은게 아닐까 싶다. 일단 지금 이 파트는 너무 어렵다. 일단 급한 정렬 알고리즘 부터 본다. 복잡한 수식은 일단 재껴 놓는게 필요
- 이 책 문제점이 알고리즘 연습문제에 대한 풀이가 없다. 연습문제는 주말에 몰아서 풀어야 할듯 진도 위주 진행. part2완료.
- 대학 교재라서 그런지 연습문제 풀이도 없고, 책에 있는 코드 그대로 수행해도 무한 루프가 발생한다. 아무리 생각해도 책을 잘못 고른것 같다. 젠장.
- 일단 확인 결과 내 잘못도 있었고 책의 잘못도 있었다. 일단 책을 한번 읽어 보고 접근하니 문제가 보이기 시작하고 디버깅이 가능해졌다.
- 일단 실전에는 크게 도움이 되지 않을 거라는 걸 알지만, 정렬 알고리즘에 대해 깊게 공부를 진행해 보기로 하였다. 모두의 알고리즘 파이썬의 책을 보면 선택정렬, 삽입정렬, 힙정렬 외에도 병합정렬, 퀵정렬이 포함되어 있어 해당 하는 정렬도 따로 추가로 공부할 계획이다.
Comments