컴퓨터 알고리즘(힙 정렬)

힙 정정 (Heap Sort)

 - 힙 구조의 특성을 이용한 정렬

 - 수행시간은 합병정렬과 동일한 O(nlon)

 - 삽입정렬과 동일한 제자리 정렬 (Sort in Place)

 

 

 

 

힙의 형태 (The chape of a heap)

 - 완전 이진 트리(Complete binary tree)에 가까운 형태 (트리는 부모노드와 자식 노드로 구성되어있는 그래프)

 - 이진트리(Binary tree)는 각 노드의 자식수가 2 이하인 경우

 - 완전 이진트리는 Root노드부터 Leaf노드까지 빠짐없이 채워져 있는 트리

맨 위에가 Root, 가장 아래가 Leaf

최대힙 특성 (Max-Heap Property)

 - 부모 노드의 값은 항상 자식 노드의 값보다 크거나 같다.

 - 따라서 전체 트리의 Root 노드값이 가장크다.

 - 또한 각 하위 트리 구조의 Root 노드가 가장 큰 값을 가진다.

 

최소힙 특성 (Min-Heap Property)

 - 자식 노드의 값은 항상 부모 노드의 값보다 크다.

 - 따라서 전체 트리의 Root 노드 값이 가장 작다.

 - 또한 각 하위 트리 구조의 Root 노그가 가장 작은 값을 가진다.

 

 

 

힘 구조에 대한 설명

부모 노드는  i/2 이고 반대로 자식 노드는 2i 가 된다. 완전 이진 트리이기 때문에 이러한 특성을 띈다. 

 

노드이 높이 (Height of Node)

 - 노드의 높이는 현재 노드에서 leaf 노드까지 내려갈때 가장 단순하게 내려가는 가장 긴 경로에서 (simple path) 거쳐야 하는 간선의 수이다.

 

그림 1

위의 그림 1에서 현재노드를 16이라 했을때 simple path는 3이다.

 

힙의 높이(Height of Heap)

 - lgn

 - Heap은 완전 이진 트리 구조를 가지기 때문에 각 레벨마다 노드의 수가 2배씩 증가하므로 높이는 lgn

 

힙 특성 관리(Maintaining the heap property)

 - Man-Heapify

   노드가 입력으로 주어졌을 때 노드의 좌 우 하위 트리들은 max-heap 특성을 유지하지만 노드의 값이 하위 트리 값보다 작거나 같아서 max-heap 특성을 만족하지 않을 때 max-heap 특성이 유지되도록 바꾸는 연산

 

  주어진 노드의 값을 "흘러내리게" 해서 주어진 노드와 하위 트리가 max-heap 특성을 가질 수 있도록 변경

 

이와 같이 Max-heapify 해준다

MAX-HEAPIFY란?? ROOT부터 LEAF 까지 가장 심플하게 내려가는것

노드의 값을 바꾸게되면 전체에서 확인을 해야 하기 때문에 힙의 높이인 lgn만큼의 수행시간이 걸린다.

 

힙 구조 만들기 (Building a heap)

왜 배열의 절반 크기로부터 으로 부터 시작하는지?  마지막 노드의 부모는 그 노드의 절반 에 해당하는 위치에 존재한다. 그래서 절반의 크기에 있는 부모노드를 보고 MAX-HEAP 구조를 만들어 준다.

 

 

n/2번째부터 Building 을 시작한다. 즉 5번 노드부터 MAX-HEAP을 만든다. 만약 노드의 변경이 일어나면 번경된 를 부모로 가지는 노드에서도 다시 MAX-HEAP을 만들어줘야한다.

 

수행시간 

MAX-HEAPIFI는 logn, 호출 횟수는 n/2 따라서 전체 수행 시간은 nlogn

 

최대값 추출 (Extract-Max)

Heap 에서 가장 큰 값을 제거하고 MAx-heap 구조를 복원하는 연산

가장 마지막에 있는 값음 root 값과 교체한다. 즉 root에서 노드방향으로 max-heapify를 해주면 된다. 

즉 첫번째 값과 마지막 값의 자리를 바꾼 후 max-heapify를 해주면 된다.

 

힙 소트 (Heap Sort)

 

 

MAX-HEAP 구조에서 오름차순 정렬을 만드는 과정이다. 

오름 차순이 된다.