[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

binary tree

 

이진트리 : 자식 노드가 최대 두개인 노드들로 구성된 트리.

 

정이진트리(full binary tree),

완전이진트리(complete binary tree),

균형이진트리(balanced binary tree)

등이 있음.

 

크기는 9 , 높이는 3인 이진 트리

full 과 complete 비교

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 ) 을 사용함.

힙 생성 알고리즘은 특정한 하나의 노드 ! 에 대해서 수행하는 것인데, 

이 특정한 하나의 노드를 제외하고는 다른 노드들은 힙의 성질을 만족해야한다.