힙 Heaps

root node가 언제나 최대 또는 최소인 완전 이진 트리를 만족하는 자료구조

• 최대 힙 max heap, 최소 힙 min heap

이진 탐색 트리와의 비교

	힙 heaps	이진 탐색 트리
원소들은 완전히 크기 순으로 정렬되어 있는가	x	o
특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가	x	o
부가의 제약 조건이 있는가	완전 이진트리여야 함	x

연산

• __init__() : 비어있는 힙 생성
• insert(item) : 원소 삽입
• remove() : 최대 원소 반환 및 제거

배열을 이용한 이진트리 표현

node = m

• left child node = 2m
• right child node = 2m + 1
• parent node = m // 2

최대 힙 구현

1. 빈 힙 생성

class MaxHeap:
  def __init__(self):
    self.data = [None]

2. insert(item)

def insert(self, item):
  self.data.append(item)

  m = len(self.data) - 1

  while m != 1:
    parentNum = m // 2

    if self.data[m] > self.data[parentNum]:
      self.data[m], self.data[parentNum] = self.data[parentNum], self.data[m]
      m = parentNum
    else:
      break

3. remove()

def remove(self):
  if len(self.data) > 1:
    self.data[1], self.data[-1] = self.data[-1], self.data[1]
    data = self.data.pop(-1)
    self.maxHeapify(1)
  else:
    data = None

  return data

def maxHeapify(self, i):
  left = i * 2
  right = i * 2 + 1

  smallest = i

  if left < len(self.data) and self.data[left] > self.data[smallest]:
    smallest = left

  if right < len(self.data) and self.data[right] > self.data[smallest]:
    smallest = right

  if smallest != i:
    self.data[i]. self.data[smallest] = self.data[smallest], self.data[i]
    self.maxHeapify(smallest)

최대/최소 힙의 응용

1. 우선 순위 큐 priority queue

• enqueue할 때 느슨한 정렬을 이루고 있도록 함 : O(longn)
• dequeue할 때 최댓값을 순서대로 추출 : O(logn)

2. 힙 정렬 heap sort

• 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입 : O(logn)
• 삽입이 끝나면, 힙이 비게 될 때까지 하나씩 삭제 : O(logn)
• 원소들이 삭제된 순서가 원소들의 정렬 순서
• 정렬 알고리즘의 복잡도 : O(nlogn)

힙 정렬 코드 구현

def heapsort(unsorted):
  H = MaxHeap()
  
  for item in unsorted:
    H.insert(item)
    
  sorted = []
  
  d = H.remove()
  
  while d:
    sorted.append(d)
    d = H.remove()

  return sorted