컴퓨터알고리즘#8
LeeMir, 07 April 2021
힙과 힙정렬(이어서)
힙 정렬 개선
- 제자리 힙 정렬은 힙 정렬의 공간 사용을 줄인다
- 상향식 힙 생성은 힙 정렬의 속도를 높인다
- 제자리 힙 정렬
- 이 방식은 정렬되어야 할 리스트가 배열로 주어진 경우에만 적용
- 힙을 저장하는데 리스트의 일부를 사용함으로써 외부 힙 사용을 피함
- 지금까지 사용했던 최소힙 대신, 최대 원소가 맨 위에 오게 되는 최대힙을 사용
- 1기(생성)
- 비어 있는 힙으로부터 출발하여 리스트의 경계를 왼쪽으로 오른쪽으로 한 번에 한 칸씩 이동
- 2기(정렬)
- 힙의 최대 원소를 삭제하면서 배열의 인덱스 n부터 1순서대로 넣음
- 상향식 힙 생성
- 힙 정렬의 1기에서, n회의 연속적인 insertItem 작업을 사용하여 O(n log n) 시간에 힙을 생성
- 대안으로, 만약 힙에 저장되어야 할 모든 키들이 미리 주어진다면, O(n) 시간에 수행하는 상향식 생성 방식이 있음