영어로 힙(Heap)은 "아무렇게나 쌓아놓은 더미"를 의미합니다. 힙 정렬에서 다루는 힙은 아무렇게나 쌓여있는 것 같지만 내부적으로는 수학적인 원리에 의해 데이터를 관리하고 있습니다. 힙은 데이터 집합에서 가장 큰 값을 효율적으로 뽑아낼 수 있는 자료구조입니다. 그래서 힙을 "우선순위 큐"의 예로 많이 듭니다. 힙 정렬은 데이터들을 힙에 쌓아두고 가장 큰 값을 계속 뽑아서 차곡차곡 배치하면 정렬이 된다는 단순한 원리입니다. 원리는 단순하지만 이것을 효율적인 방법으로 구현하는 것은 또 다른 도전이 됩니다. 힙의 모양은 이진트리이기 때문에 통상적인 연결리스트로 힙을 구현할 경우 상당한 오버헤드가 발생하기 때문입니다.
하지만 이진트리를 배열로 저장하는 방법이 고안되면서 얘기는 달라집니다. 간단한 첨자 조작 만으로 트리를 배열에 저장할 수 있어 오버헤드가 최소화됩니다. 이런 물적 토대가 갖추어지면서 비로서 힙정렬은 실용적인 알고리즘이 됩니다.
이런 스토리를 이해하고 힙정렬에 대한 이야기를 들으면 더욱 더 재미있을 겁니다. 힙정렬은 입력자료에 관계없이 항상 일정한 성능을 보여주는 독특한 특성을 가지고 있습니다. 정렬에 대한 고정관념을 깨는 좋은 기회가 될 겁니다.
강의 자료
강의 동영상
11.0 힙정렬 - 시작 : 힙정렬은 우선순위큐를 이용한 정렬입니다. 또한 고정관념을 깨뜨리는 알고리즘이기도 합니다. 전혀 새로운 접근법으로 정렬하는 방법을 배워봅시다.
11.1 우선순위 큐 : 우선순위 큐는 범위가 넓은 개념으로 이미 그 예들을 배워 왔습니다. 일반적인 우선순위큐의 정의와 기본 동작에 대해 배워 봅니다.
11.2 힙의 개념 : 힙은 뭔가를 쌓아놓은 더미를 의미하는데, 아무렇게나 쌓아 놓은 건 아닙니다. 힙은 이진트리의 형태로 체계적이고 효율적인 우선순위 큐입니다. 힙의 기본 개념과 동작을 알아봅니다.
11.3 트리를 배열로 표현하기 : 트리는 일반적으로 연결리스트와 비슷한 형태로 표현합니다만 처리 속도가 느린 단점이 있습니다. 이진트리의 경우 간단한 수학적 조작으로 배열에 저장할 수 있습니다. 그 방법에 대해 알아봅니다.
11.4 힙 정렬의 구현 : 먼 길을 돌아 왔습니다. 힙에 대해 알아 보았으니, 이 힙을 이용하여 어떻게 정렬하는지 알아봅니다. 그런데 싱거울 정도로 간단합니다.
11.5 힙정렬의 분석 : 힙정렬은 아주 이상적인 성능 수치를 보여 줍니다. 게다가 부가 메모리가 전혀 필요치 않습니다. 힙정렬의 성능에 대해 자세히 알아봅니다.
11.6 힙정렬의 개선 : 콜롬부스의 달걀과 같은 단순한 발상으로 힙정렬의 성능을 약간 개선할 수 있습니다.
11.7 힙정렬 성능 분석 : 힙정렬의 성능을 분석해 봅니다. 힙정렬은 오버헤드가 큰 편이지만 입력자료에 관계없이 일정한 성능을 보여주기 때문에 안정성이 필요한 경우 사용할 수 있습니다.
11.9 힙정렬 - 결론 : 재미있었던 힙정렬 탐험을 정리해 봅니다.
관련글 |
- C++로 배우는 알고리즘
- 이진트리의 종류에 대하여 (오류 수정)
- 10장 : 퀵 정렬
- 12장 : 쉘 정렬, 병합 정렬
댓글 없음:
댓글 쓰기