[13] 심화 정렬 ( SORT ) - Heap Sort
Heap Sort
- 최악의 경우에도 시간 복잡도 O(nlog2n)
- 추가 배열도 필요하지 않음
- 이진 힙 ( binary heap ) 자료구조를 사용
힙을 알려면 Tree 와 Binary Tree 를 알아야함.
Tree
트리의 속성 중 가장 중요한 것이 ‘루트노드를 제외한 모든 노드는 단 하나의 부모노드만을 가진다’는 것
이 속성 때문에 트리는 다음 성질을 만족함.
- 임의의 노드에서 다른 노드로 가는 경로(path)는 유일하다.
- 회로(cycle)가 존재하지 않는다.
- 모든 노드는 서로 연결되어 있다.
- 엣지(edge)를 하나 자르면 트리가 두 개로 분리된다.
- 엣지(edge)의 수 |EE| 는 노드의 수 |VV|에서 1을 뺀 것과 같다.
참조 ↓
https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/
트리(tree)와 이진트리(binary tree) · ratsgo's blog
이번 글에서는 다양한 분야에서 널리 쓰이고 있는 자료구조인 트리(tree)와 트리의 일종인 이진트리(binary tree)에 대해 살펴보도록 하겠습니다. 힙 정렬이 뭔지 알아보려면 여러가지 개념을 먼저 �
ratsgo.github.io
binary tree
이진트리 : 자식 노드가 최대 두개인 노드들로 구성된 트리.
정이진트리(full binary tree),
완전이진트리(complete binary tree),
균형이진트리(balanced binary tree)
등이 있음.
1. full : 모든 레벨에 노드들이 꽉 차있어야한다.
2. complete : 마지막 레벨 제외한 모든 레벨에 노드들이 꽉 차있고,
마지막 레벨은 가장 오른쪽 ! 부터 몇개정도 노드들이 빠질 수 있다.
Heap
최솟값으나 최댓값을 빠르게 찾아내기 위해
완전 이진 트리를 기반으로 하는 트리
- complete binary tree 이면서
- heap property 를 만족해야한다.
max heap property : 부모는 항상 자식보다 크거나 같다.
min heap property : 부모는 항상 자식보다 작거나 같다.
힙은 일차원 배열로 표현 가능.
왜 ? 이런 규칙성이 있기때문에
루트노드 A[1]
A[i] 의 부모 = A[i/2]
A[i] 의 왼쪽 자식 = A[i*2]
A[i] 의 오른쪽 자식 = A[i*2 +1]
힙 정렬을 하려면 힙 생성 알고리즘 ( Heapify Algorithm ) 을 사용함.
힙 생성 알고리즘은 특정한 하나의 노드 ! 에 대해서 수행하는 것인데,
이 특정한 하나의 노드를 제외하고는 다른 노드들은 힙의 성질을 만족해야한다.