오늘은 지난 번에 공부했던 연결 리스트에 이어서 Heap 힙에 대해서 공부 정리한 내용입니다.
목차
1. Heap 힙 정렬
- 힙 정렬은 병합정렬(Merg sort)와 퀵 정렬(Quick sort) 만큼 빠른 정렬 알고리즘입니다.
- Heap 힙은 Heap Tree 구조를 이용하고 있습니다.
- 이진 트리 : 모든 노드의 자식 노드가 2개 이하 트리 구조 입니다. 최대 2개까지 자식 노드를 가질 수 있습니다.
- 완전 이진 트리는 왼쪽부터 채워가는 것 입니다.
- 구조는 최소값, 최대값을 빠르게 찾을 수 있습니다.
힙 붕괴가 일어날 경우 최소 값, 최대 값에 맞게 스왑을 진행해 위로 숫자에 맞게 정렬을 합니다.
부모 값과 비교하여 진행됩니다.
시간 복잡도는 O(logn)를 가집니다.