[python] 힙 정렬(Heap sort)

힙(Heap)

• 히프는 완전이진트리 기반 자료구조이다.
• 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다.
• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리를 뜻한다.
• key(부모노드) ≥ key(자식노드) 조건을 항상 성립한다.
• 노드의 인덱스
  • 배열로 구현 시 0번째 인덱스가 아니라 1번째 인덱스에서부터 시작된다.
  • 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
  • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
  • 부모의 인덱스 = (자식의 인덱스) / 2

 

힙 트리

힙 트리는 중복된 값을 허용한다.

 

 

힙 트리가 이닌 예

완전 이진 트리가 아니기 때문에 힙 트리는 아니다.

 

 

힙 종류

최대 힙(max heap)

• 부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전 이진 트리
• key(부모 노드) ≥ key(자식 노드)

최소 힙(min heap)

• 부모 노드의 키값이 자식 노드의 키값보다 작거나 같은 완전 이진 트리
• key(부모 노드) ≤ key(자식 노드)

 

 

힙 정렬

• 최대 힙을 이용하면 정렬이 가능하다.
• 시간 복잡도: O(nlogn)
• 불안정 정렬이다.
• 과정
  • 최대 힙을 구성
    • 루트를 힙의 마지막 원소와 교환한다.
    • 마지막 원소를 제외하고 나머지 원소에 대해서 반복한다.
    • 정렬된 원소를 제외하고 최대 힙에 원소가 1개 남으면 정렬을 종료한다.

 

힙 삽입

• 새로운 노드를 힙의 가장 마지막 노드로 삽입하고, 부모 노드와 비교하여 히프의 성질을 만족시켜 주어야 한다.

 

힙 삭제

• 최대 값을 가진 요소를 제일 먼저 삭제한다. (즉 루트 노드가 삭제)
• 루트 노드를 삭제한 후에 힙의 마지막 노드를 루트 자리에 놓은 후 자식 노드와 크기 비교를 하여 힙의 성질을 만족시킨다.

 

구현

# 힙 정렬
def heapify(unsorted, index, heap_size):
  largest = index
  left = 2 * index + 1
  right = 2 * index + 2
  
  if left < heap_size and unsorted[right] > unsorted[largest]:
    largest = left
    
  if right < heap_size and unsorted[right] > unsorted[largest]:
    largest = right
    
  if largest != index:
    unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
    heapify(unsorted, largest, heap_size)

def heap_sort(unsorted):
  n = len(unsorted)
  
  for i in range(n // 2 - 1, -1, -1):
    heapify(unsorted, i, n)
    
  for i in range(n - 1, 0, -1):
    unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
    heapify(unsorted, 0, i)

  return unsorted

 

출처

https://dpdpwl.tistory.com/45

[Algorithm]힙정렬 알고리즘(C++)

https://github.com/TheAlgorithms/Python/blob/master/sorts/heap_sort.py#L56

GitHub - TheAlgorithms/Python: All Algorithms implemented in Python