heap

힙 트리란

• 부모와 자식간에 대소관계가 성립하는 완전이진트리의 자료구조를 말합니다.
  • 최대 힙: 부모가 자식보다 항상 크다.
  • 최소 힙: 부도가 자식보다 항상 작다.

트리 구조

• 여러 노드가 한 노드를 가리킬 수 없는 구조를 말합니다.(단방향 그래프)
• 트리는 계층구조가 존재합니다.
  • A노드가 B노드를 가리킬 때 A노드 부모, B노드는 자식입니다.
• 트리는 비선형 자료구조 입니다.
  • 선형 자료구조: 하나의 자료 뒤에 하나의 자료가 존재
  • 비선형 자료구조: 하나의 자료 뒤에 여러개의 자료가 존재할 수 있음

완전이진트리

• 이진트리: 각 노드가 최대 두 개의 자식노드를 가지는 트리 구조
• 완전이진트리: 최상위 노드를 기준으로 왼쪽부터 빠짐없이 채워져 있는 트리 구조
  • 마지막 hierarchy는 왼쪽부터 값이 들어있으면 되고, 여기에 모든 노드가 채워져 있을 필요는 없다

heapify

• heap: 완전이진트리 중 특별한 성질(부모와 자식간에 대소관계)을 가지는 자료구조
• heapify: 주어진 자료구조를 heap 형태로 바꾸는 것
  • (최대 힙 기준) heapify수행방법
    • 최상단 노드부터 순차적으로 다음의 검사를 실시한다.
      • 자신의 부모가 자신보다 작으면 서로 값을 바꾼다.
      • 현재위치에서 최상단노드까지 heap정렬이 잘 되어있는지 검사한다.

#파이썬 heapify
def heapify(lst,n):
    for i in range(1,n):
        c = i
        while c != 0: #c가 0이되면 멈춘다 == 현재 위치(c)부터 가장 꼭대기 노드(0)까지 다 검사했으면 멈춘다
            root = (c-1)//2 #root찾는 방법!
            if lst[root] < lst[c]: #부등호 방향만 바꾸면 반대로(최대 or 최소) 정렬됨
                lst[root],lst[c] = lst[c],lst[root]
            c = root    

• heap sort
  • heapify를 수행하면 가장 최상위 노드에 최대값이 들어있는 건 확실합니다.
    하지만 아직 나머지 노드들이 모두 순서대로 정렬되어 있지 않습니다.
  • 이렇게 하면 어떨까요?
    • 힙정렬을 합니다.
    • 가장 큰 값(부모 노드의 값)을 꺼냅니다.
    • 가장 큰 값이 빠진 나머지 노드들을 다시한번 정렬 합니다.
    • 나머지 노드에서 가장 큰 값을 꺼냅니다.
    • 나머지의 나머지를 또 정렬합니다.
    • 나머지의 나머지에서 가장 큰 값을 또 뺍니다.
    • ...
  • 구현에서는 값을 꺼내지 않고 가장 마지막에 있는 값과 위치를 교환합니다.

#파이썬 heap_sort
def heap_sort():
    for i in range(len(lst)-1,-1,-1):   
        lst[0],lst[i] = lst[i],lst[0]
        heapify(lst,i)

장점

• 빠릅니다. - O(N*logN)
  • 실제로는 1/2개의 노드만 대해서만 heapify를 수행해도 heap구조가 되기 때문에 (N*logN)/2까지 빨라진다.

단점

• 불안정정렬이다.
  • 중복된 값을 입력 순서와 동일하게 정렬하지 않음.(기존의 정렬상태를 유지하지 않음)
  • 불안정정렬이 어떤 점에서 얼마나 안좋은 건지는 잘 모르겠음.

References

• https://goodgid.github.io/DS-Linear-and-NonLinear/