[기술면접/알고리즘] Heap Sort

Heap Sort에 대해 설명하세요

Keyword

heap,

---

Script

Heap Sort는 heap 자료구조를 기반으로 정렬을 수행하는 알고리즘입니다. 내림차순 정렬을 위해서는 최대 힙, 오름차순을 위해서는 최소 힙 자료구조를 사용할 수 있습니다. 주어진 배열의 n개의 요소를 Heap에 삽입하고, 하나씩 삭제하면서 이를 새로운 배열에 저장하는 방식으로 정렬을 수행할 수 있습니다. Heap 자료구조에서 삽입/삭제는 O(logN)의 시간복잡도로 수행되므로, n개의 요소들을 모두 삽입/삭제하는데에는 O(NlogN)의 시간복잡도로 수행됩니다.

---

Additional

시간복잡도

Heap Tree의 전체 높이 = logN
=> 삽입/삭제 => logN

요소의 개수 = n

T(n) = NlogN

그림

코드 (python)

# 힙 정렬
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

정렬 알고리즘 시간복잡도 비교