'힙정렬' 태그의 글 목록

힙 정렬 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법으로, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 1. 정렬해야할 n개의 요소들로 최대힙(완전 이진 트리 형태)를 만든다. 내림차순 기준 정렬2. 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다.3. 삭제되는 요소들(최댓값부터 삭제)는 값이 감소되는 순서로 정렬되게 된다. - 완전 이진 트리를 기본으로 하는 힙 자료구조를 기반으로한 정렬방식이다.- 힙은 1차원 배열로 쉽게 구현될 수 있다.- 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값이나 작은 값을 구할 때, 최대 k만큼 떨어진 요소들을 정렬할 때 이다. 시간 복잡도최선/최악/평균 모두 O(n..