힙정렬(Heap sort) 개념정리

 힙정렬이란 '힙(Heap)' 이라고 하는 특수한 자료형태를 사용하여 정렬을하는 정렬입니다.

특징이라고하면 특징일 수 있는것은, 어느 한 트리에서 루트노드는 그 아래있는 여러 노드들을 대표하는 노드를 의미합니다.

 

힙(Heap)의 종류

1. MAX힙 :
  어느 한 트리에서 모든 서브트리의 루트노드가 그 각각의 트리에서 가장 크거나 같은  완전이진트리 (= 루트로부터 내림차순)

2. MIN힙 :
  어느 한 트리에서 모든 서브트리의 루트노드가 그 각각의 트리에서 가장 작거나 같은 완전이진트리 (= 루트로부터 오름차순)

힙(Heap)을 구성하는방법

MAX힙을 기준으로 나타내겠습니다.

              6
            /    ＼
          5         3
        /   ＼     /  
     15      8  9      

위와같은 트리가 있다고 가정합시다.

정렬은 딱히 설명하기는 좀 어렵고, 예시를 보면서 읶히는쪽이 빠를 것 같습니다.

먼저 첫번째로 위치변경의 시작은 말단노드입니다

              6
            /    ＼
         15        3
        /   ＼     /   
      5       8  9       

: 15,5,8로 이루어진 트리에서 가장큰 15를 그 트리의 루트로 보내주었습니다.


              6
            /    ＼
         15        9
        /  ＼      /   
      5      8  3

: 다음으로 옆의 3,9로 이루어진 트리도 가장큰 값을 그 트리의 루트로 보내주었습니다.


              15
            /    ＼
          6        9
        /  ＼    /   
      5      8 3

: 6,15,9로 이루어진 트리에 집중해볼때, 가장큰값인 15를 6과 교환하였습니다.


              15
            /    ＼
          6        9
        /   ＼   /      
      5       8 3        

: 한단계 전에서 15와 6을 교환해주니 6,5,8로 이루어진 서브트리가 MAX힙의 규칙에서 어긋나게 되었습니다.


              15
            /    ＼
          8        9
        /   ＼    /    
      5      6  3        

: 이를바로잡아주기위해 가장큰값인 8을 6과교환해주었습니다.

이상, 이런 방식으로 일반 이진트리를 힙트리로 만들 수 있습니다.

힙정렬 하는법

위에서 만들었던 힙트리를 이용하여 힙정렬을 해봅시다.

             15
            /    ＼
          8        9
        /   ＼    /     
      5       6 3       

첫번째단계는, 이 트리의 루트를 출력(=제외)합니다.

          8         9
        /   ＼     /
      5       6  3       

: 15가 출력(=트리에선 제외)되었습니다.


              3
            /    ＼
          8        9
        /   ＼        
      5       6         


: 가장 오른쪽 아래있는값 3을 15자리에 넣어줍니다.


              3
            /    ＼
          8        9
        /   ＼        
      5       6       

: 그리고 3,8,9서브트리를 건드릴 차례입니다.


              9
            /    ＼
          8        3
        /   ＼        
      5       6     

: 3,8,9를 힙으로 구성하였습니다.  


              6
            /    ＼
          8        3
        /           
      5            

: 9를 출력했습니다. 그자리에 가장 마지막 노드인 6이 들어갔습니다.


              8
            /    ＼
          6        3
        /           
      5           

: 이것을 다시 힙으로 구성하였습니다.

              6
            /    ＼
          5        3

: 8을 출력하고 5가 그자리를 매운뒤 힙으로 구성했습니다.    


             5
           /   
         3

: 6을 출력하고 3이 그자리를 매운뒤 힙으로 구성했습니다.

            3 


: 5가 출력되면 3만이 남습니다. 이제 3마저 출력하면 아무것도 남지않습니다.

이런과정을 통해 15,9,8,6,5,3  으로 출력된 순서대로 나타나게되며, 이는 내림차순정렬과 같습니다.

힙정렬의 삽입, 삭제

힙정렬에서의 삽입은 Upheap 이라고도 불리며 규칙은 다음과같습니다.

1. 가장 높은레벨(= 단말노드가 있는레벨)의 오른쪽 끝자리에 삽입할 데이터를 삽입합니다.

2. 삽입한 데이터와 부모노드와 비교했을 때 부모노드보다 크다면 부모노드와 자리를 바꿉니다.

3. 적정한 자리가 정해질때까지 1번과 2번을 반복합니다.

Example) 위에서 만든 힙트리를 이용하겠습니다.

              15
            /    ＼
          8         9
        /   ＼     /  
      5       6  3       

이제 33을 삽입한다 가정합시다.


              15
            /    ＼
          8         9
        /   ＼     /  ＼ 
      5       6  3    33

: 처음모습은 이렇게 될 것 입니다.

   
              15
            /    ＼
          8         33
        /   ＼     /  ＼ 
      5       6  3      9


: 9와 비교하여보니 33과 9가 위치를 바꿉니다.


              33
            /    ＼
          8         15
        /   ＼     /  ＼ 
      5       6  3      9

: 15와 33을 비교해보니 15와 33을 바꿔줬습니다.

이상 힙으로 구성되었으며 삽입이 완료되었습니다.





힙정렬에서 삭제는 Downheap 이라고도 불리며 이는 루트노드를 삭제하는 것으로, 이미 힙정렬 예시를 통해 보여드렸으므로 생략하겠습니다.

 

- 손님가두고, 손님늘리는 강압적인 놀이공원??(롤러코스터타이쿤)

- 입장료도 놀이기구 탑승료도 무료인 이 놀이공원 돈은 어떻게벌?