목록heap sort (1)

코딩뚠뚠

[기본문제풀이] heap_sort

풀이 일시 : 2020-08-04 ​ 힙정렬 : 힙 트리구조를 이용하는 정렬방법이다. 힙정렬을 하려면 정해진 데이터를 힙구조를 가지도록 만들어야 한다. ( 힙은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진트리를 기반으로 하는 트리이다. 최대힙은 부모노드가 자식노드보다 큰 힙이다. ) 힙생성 알고리즘 - 큰 자식과 자신의 위치를 바꾸는 것이다. 즉 O(logN) 전체 트리를 힙구조로 만드는 복잡도는 결국 O(N*logN) 이를 가지고 루트의 값을 가장 뒤쪽으로 보내면서 힙트리의 크기를 1씩 빼준다. 가장 뒤쪽으로 보낸 것은 정렬이 된 것이고 다시 나머지에 대해 힙생성 알고리즘을 수행해준다. 결국 전체 힙 정렬의 복잡도는 O(N*logN) 문제를 보면서 이해해보도록 하자. ​ 문제 : 7 6 5 8 ..
알고리즘 문제풀이/기본문제풀이 2020. 12. 27. 15:20
이전 Prev 1 Next 다음