[Algorithm] Heap 구현해보기

파이썬으로 Heap(Min Heap) 구현해보기

구현 목표 :

• push 메서드 만들기(O(logN)의 시간복잡도를 갖는)
• pop 메서드 만들기(O(logN)의 시간복잡도를 갖는)
• top 메서드 만들기(O(1)의 시간복잡도를 갖는)
• length 메서드 만들기(Heap 내의 노드의 개수를 출력해주는 메서드)

먼저 Heap 객체 만들고, 그 안에 메서드를 만들어줬다. Heap을 하나의 객체로 취급해서 만들었음.

구현 코드 :

# 힙의 특성 중에 하나는 
# 배열로 표현했을 때 자식 노드의 부모 노드 인덱스를 구하려면
# 자식 노드의 인덱스 // 2 를 해주면된다(나머지는 버린다)
# 또한, 부모 노드의 입장에서 왼쪽 자식노드의 인덱스는 '부모노드의 인덱스 * 2'이고,
# 오른쪽 자식 노드의 인덱스는 '(부모노드의 인덱스 * 2) + 1' 이 된다.

class Heap:
  def __init__(self):
    self.heap = [None]
    self.len = 0

  def length(self):
    return len(self.heap) - 1 
  
  def pop(self):
    if len(self.heap) == 1:
      return None
    else:
      heap = self.heap

      temp = heap[1]
      heap[1] = heap[self.len - 1]
      del heap[self.len - 1]
      self.len -= 1 
      idx = 1 

      while True:
        try:
          if heap[idx] > heap[idx * 2] or heap[idx] > heap[(idx * 2) + 1]:
            if heap[idx * 2] > heap[(idx*2)+1]:
              heap[idx], heap[(idx*2)+1] = heap[(idx*2)+1], heap[idx]
              idx = (idx*2)+1
            else:
              heap[idx], heap[idx * 2] = heap[idx * 2], heap[idx]
              idx *= 2 
          else:
            break
        except:
          break

      return temp
  
  def push(self, node) :
    # 맨 뒤에 추가하고, 부모 노드와 연쇄적 비교 시행
    heap = self.heap
    heap.append(node)
    self.len += 1 
    idx = self.len

    while True:
      if idx == 1:
        break
      parent = idx // 2 
      child = idx

      if heap[child] < heap[parent]:
        heap[child], heap[parent] = heap[parent], heap[child]
        idx //= 2
      else:
        break

    return 
    
  def top(self):
    try:
      return self.heap[1]
    except:
      return None

위와 같이 만든 Heap 객체를 이용해 Heap 정렬 만들기

구현 코드 :

# 파이썬으로 heap sort 직접 만들어보기 

def heap_sort(l) :
  # 먼저 받은 배열을 heap으로 만들어야함 
  heap = Heap()
  for el in l :
    heap.push(el)
  # heap으로 만들었음
  # 그러면 pop하면서 정렬해야함
  
  result = [] 
  top = heap.top()

  while top is not None:
    result.append(heap.pop())
    top = heap.top()

  return result