힙정렬

힙정렬은 비교적 빠른 정렬 방식중 하나이다. 먼저 트리와 힙에 대해서 알아본뒤, 힙정렬을 어떻게 하는지 알아보고 마지막으로 시간복잡도에 대해서 설명하겠다.

Tree

위의 슬라이드에 보이는 것들이 모두 Tree구조이다.

이진트리

자식이 최대 2개있는 트리를 이진트리라고 부른다. 이진트리의 종류는 대표적으로 Full, Complete, Perfect가 있다.

Full

이진트리중에서 자식 노드가 아예 없거나 혹은 2개 가지고 있는것을 Full 이진트리라고 부른다.

Complete

왼쪽부터 노드가 하나하나 채워져 있는 것을 Complete 이진 트리라고 부른다.

Perfect

모든 레벨의 노드가 꽉꽉 채워져 있는것을 Perfect 이진트리라고 부른다

힙(heap)은 원래 어떤 물건들이 막 쌓여져 있는 모습을 의미하는 단어이지만, 여기서는 Complete 이진 트리를 의미한다. 이 힙을 이용하면 효율적인 정렬이 가능하다.

최대힙

모든 부모노드가 자식노드 보다 항상 큰 상태를 최대힙 이라고 부른다.

최소힙

모든 부모노드가 자식노드보다 항상 작은 경우를 최소힙 이라고 부른다

힙정렬

힙의 컨셉을 활용하여, 위와같이 배열을 오름차순으로 정렬할 수 있다. 힙의 컨셉을 활용한다는건 배열을 힙 이라는 트리 구조로 다시 만든다는 말은 아니다(추가적인 메모리 사용 X). 힙은 complete 이진트리 이기 때문에, 배열의 index 만 가지고도 충분히 정렬이 가능하다.

작동방식

  1. 배열의 원소들을 힙에 왼쪽부터 하나하나 넣었다고 생각한다. 실제 코드로 뭘 해서 메모리에 반영되는건 아니다. 단지 그렇게 생각만 하는것이다.
  2. 최대 힙을 만들어 준다. 핵심은 자식 노드가 부모노드 보다 큰지 확인한후 더 크다면 위로 올리는 것이다. 배열의 끝부터 시작해서 좌우 자식 노드를 비교한 후 그중 더 큰놈을 또 부모랑 비교해서 더 크면 부모노드랑 swap한다. 여기서 주의할점은, Level 4는 자식 노드가 없어서 그냥 위로만 올려주면 되지만, Level 3은 자식 노드가 있기 때문에 부모노드(Level 2)와 비교해서 swap 당한 노드를 Level 4와 또 비교해줘야 한다는 것이다. 그래야 모든 부모노드가 자식노드 보다 크게 될 수 있다.
올려 보낸 다음에 아래쪽 노드랑 다시 비교하는 과정

3. 맨 위쪽 노드(index = 0)과 맨 아래쪽 노드를 바꿔준다. 가장 큰 노드를 배열의 마지막 요소와 swap해 주는 것이다. 그리고 이제 더 이상 맨 마지막 노드는 신경쓰지 않는다(= 비교 과정에 넣지 않는다).

4. 맨 위쪽 노드를 가능한 아래로 내리는 과정(=최대힙 만들기)을 거친다. 그러면 그 다음으로 큰 노드가 맨 위에 올라가 있을 것이다.

5. 3,4번 과정을 계속 반복해주면 배열이 오름차순으로 정리가 된다.

자식 노드와 부모노드를 비교하는 방법

영상에서도 알 수 있듯이, 자식노드끼리 먼저 비교하고 그 다음에 부모노드랑 비교를 한다. 실제 이것을 수행하려면 우리는 배열의 어디에 자식노드가 있는지, 부모노드가 있는지 알아야 한다. 다행히 힙은 complete 이진 트리이기 때문에 부모노드와 자식노드가 index를 기준으로 아래와 같은 관계성을 가진다.

leftChildIndex = 2 * parent + 1

rightChildIndex = 2 * parent + 2

그래서 어느 하나의 index만 알고 있으면 왼쪽 오른쪽 노드 그리고 부모 노드의 값까지 알 수 있는것이다. 정렬하려는 배열에 위의 공식을 사용한 index를 바탕으로 값을 가져와서 비교하면 된다.

다시 심플하게 정리하면,

  1. 배열을 최대힙으로 만들어 주고
  2. 값이 가장큰 맨 꼭대기 노드와 맨 마지막 노드를 바꿔치기 해주고
  3. 꼭 대기에 있는 노드를 아래로 내리면서 또 큰 노드를 맨 꼭대기에 올라가게 만든다. (= 최대힙 만들기)

이런식으로 하다보면 큰 순서대로 노드들이 비교 대상에 제외되고 결국 오름차순으로 정리가 되는것이다.

코드(python3)

# -*- coding: utf-8 -*- 

def swap(list, a, b) :
  temp = list[b]
  list[b] = list[a]
  list[a] = temp

def getChildren(lastIndex, parent) :
  # parent가 더 작은걸 명심하자
  childLeft = (parent * 2) + 1
  childRight = (parent * 2) + 2
  if ( lastIndex >= childRight ) :
    return [childLeft, childRight]
  if ( lastIndex == childLeft ) :
    return [childLeft, False]

  return False
  
def compare(list, parent, childLeft, childRight = False) :
  compareTarget = childLeft
  if ( childRight ) :
    if ( list[childRight] > list[childLeft] ) :
      compareTarget = childRight
  
  if ( list[compareTarget] > list[parent] ) :
    swap(list, parent, compareTarget)
    return compareTarget

  return False

def heapSort(arr) :
  topIndex = 0
  lastIndex = len(arr) - 1

  # 일단 맨 처음에는 가장 큰놈을 위로 끌어 올려보낸다(= maxHeap을 만드는 과정).
  # 0번째는 루프를 돌지 않는다 !
  for i in range(lastIndex, -1, -1) :
    # 홀수(leftChildNode의 index)만 고려한다
    if ( i % 2 == 0 ) :
      continue

    # 일단 위로 올려 보내고
    parent = int((i - 1) / 2)
    children = getChildren(lastIndex, parent)
    swapedIndex = compare(arr, parent, children[0], children[1])

    # swap이 안되서 False가 나올 수도 있으니까
    if ( swapedIndex ) :

      # 아래로 쭉 내려간다
      while True :
        parent = swapedIndex
        children = getChildren(lastIndex, parent)

        # swap은 됬지만 children이 없을 수 있음
        if not children :
          break

        swapedIndex = compare(arr, parent, children[0], children[1]) # parent, childLeft, childRight


  # 이제 맨 위에있는 가장 큰 노드와 비교적 작은 맨 바닥의 오른쪽 노드를 바꾼다
  swap(arr, topIndex, lastIndex)

  # 더이상 마지막 원소는 생각할 필요가 없으니(= 비교 과정에 넣지 않는다), lastIndex를 하나 감소시켜준다. 마치 배열의 길이가 lastIndex - 1인것처럼 !
  lastIndex = lastIndex - 1

  # 여기서부터는 위에서 아래로 작은놈을 계속 끌어 내리는 과정이다
  while lastIndex >= 0 :
    parent = topIndex # start point는 항상 맨 꼭대기
    while True :
      children = getChildren(lastIndex, parent)
      if ( children ) :
        parent = compare(arr, parent, children[0], children[1])

        # swap에 실패했다는것은 부모 노드가 자식 노드보다 크다는 의미이기때문에 여기서 STOP !
        if not parent :
          break
      else :
        break

    swap(arr, topIndex, lastIndex)
    lastIndex = lastIndex - 1

시간복잡도

최대힙 만들기

n은 노드의 개수이다. 아래에서 부터 각 Level별로 스왑이 일어나는 횟수를 초록색으로 표시했다. 앞에 곱해주는 수가 올라가는 이유는 부모노드와 swap이 일어나고 나서 또 아래로 아래로 맨 밑 Level까지 swap이 일어날 수 있기 때문이다.

(1+2+3\cdots+h) * {n \over 2^h}
= {h(h + 1) \over 2} * {n \over 2^h}

시간복잡도에서는 h^2{h^2 \over 2} 거기서 거기기 때문에, 더 심플하게 표현하면 아래와 같이 된다.

h^2 * {n \over 2^h}

그리고, h(Level) = logn 이기 때문에, 결국 시간복잡도는 O(n) 가 된다.

그 다음 최대힙 만들어 주기

기본적으로 처음에 최대힙만 만들어 주면 그 다음부터는 남은 노드중에 가장 큰노드를 찾는건 매우 빨리 진행된다. 왜냐면 level 별로 한번만 비교를 수행해 주면 되기 때문이다. 예를들어 127개의 노드가 최대힙으로 정리되어 있다면, 위에서부터 맨 아래까지 내려오는데 고작 6번만 swap하면 된다.


그래서 두번째 최대힙 만들어 주는 과정은 n * logn(n = 노드의 개수)번 이루어 진다. n을 곱하는 이유는 꼭대기에 올라간 작은 노드가 아래로 내려오는 과정(logn)이 모든노드(n)들에게 거의 똑같이 일어나기 때문이다.(정렬이 되면서 Level이 낮아지고, 점점 줄어들기는 하겠지만,,크게 영향을 끼치지는 않는다. )

결과적으로, 힙정렬의 시간복잡도는 O(n + nlog) = O(nlogn) 이된다.

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다

Up Next:

삽입정렬

삽입정렬