Python 자료구조&알고리즘 - 힙(Heap)

1. 힙(Heap)

 

---

1-1. 힙

• 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
• 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

 

---

1-2. 힙을 사용하는 이유

• 배열에 데이터를 넣고 최대값, 최소값을 찾으려면 시간이 많이 걸릴 수 있음
• 힙에 데이터를 넣고 최대값, 최소값을 찾으면 시간이 적게 소모됨
• 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현등에 활용됨

 

---

2. 힙(Heap) 구조

• 힙은 최대값을 구하기 위한 구조(최대힙, Max Heap)와 최소값을 구하기 위한 구조(최소 힙, Min Heap)로 분류할 수 있음
• 힙은 아래와 같이 두가지 조건을 가지고 있는 자료구조
  1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙인 경우)
  2. 완전 이진 트리 형태를 가짐

---

2-1. 힙과 이진 탐색 트리의 공통점과 차이점

• 공통점
  • 힙과 이진 탐색 트리는 모두 이진 트리임
• 차이점
  • 힙은 각 노드의 값이 자식 노드보다 크거나 같은
  • 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드값이 큼
  • 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건이 없음

---

3. 힙(Heap)의 동작

---

3-1. 힙의 데이터 삽입하기

• 힙은 완전 이진트리이므로 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입
• 채워진 노드 위치에서 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꾸는(swap) 작업을 반복함

 

---

3-2. 힙 데이터 삭제하기

• 최상단 노드를 삭제하는 것이 일반적
• 힙의 용도는 최대값 또는 최소값을 root노드에 놓아서 최대값 또는 최소값을 바로 꺼낼 수 있도록 하는 것
• 상단의 데이터 삭제시 가장 최하단부 왼쪽에 위치하는 노드(일반적으로 가장 마지막에 추가한 노드)를 root 노드로 이동
• root 노드의 값이 child node보다 작을 경우. root 노드의 child node 중 가장 큰 값을 가진 노드와 root노드 위치를 바꿔주는 작업을 반복

---

4. 힙 구현 하기

• 힙 구현시 배열 자료구조를 활용
• 배열은 인덱스가 0번부터 시작하지만 힙 구현의 편의를 위해 root 노드 인덱스 번호를 1로 지정하면 구현이 좀 더 수월함
  • 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 // 2
  • 완쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2
  • 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 +1

# 예1 : 10 노드의 부모 노드 인덱스
2 // 2 # 인덱스 2에 대한 부모 노드 인덱스

# 예2 : 부모 노드 왼쪽 자식 노드 인덱스
1 * 2

# 예3: 부모 노드의 오른쪽 자식 노드 인덱스
2 * 2 + 1

 

4-1. 힙 클래스 구현하기

 

class Heap:
  def __init__(self, data):
    self.heap_array = list()
    self.heap_array.append(None) # 0번을 비워주고 1번부터 시작하기 위해 None을 넣으
    self.heap_array.append(data)

heap = Heap(1)
heap.heap_array

 

4-2. 삽입 구현하기

class Heap:
  def __init__(self, data):
    self.heap_array = list()
    self.heap_array.append(None)
    self.heap_array.append(data)

  def insert(self, data):
    if len(self.heap_array) == 0:# 방어 코드
      self.heap_array.append(None) 
      self.heap_array.append(data)      
      return True
    self.heap_array.append(data)
    return True

heap = Heap(15)
heap.insert(10)
heap.insert(8)
heap.insert(5)
heap.insert(4)
heap.insert(20)
heap.heap_array

 

• 삽입한 노드가 부모 노드의 값보다 클 경우 부모 노드와 삽입한 노드 위치를 바꿈
• 삽입한 노드가 루트 노드가 되거나 , 부모 노드보다 값이 작을 경우까지 계속 반복

 

class Heap:
  def __init__(self, data):
    self.heap_array = list()
    self.heap_array.append(None)
    self.heap_array.append(data)

  def move_up(self, inserted_idx):
    if inserted_idx <= 1:
      return False
    parent_idx = inserted_idx // 2
    if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
      # 부모 값보다 내 값이 더 크다면 swap(변경)
      return True
    else:
      return False

  def insert(self, data):
    if len(self.heap_array) == 0:# 방어 코드
      self.heap_array.append(None) 
      self.heap_array.append(data)      
      return True
    self.heap_array.append(data)
    inserted_idx = len(self.heap_array) - 1 
# 지금 집어 넣은 인덱스 값을 구하고 전체 인덱스보다 
# +1 이 나오기 때문에 -1을 해주어 값을 맞춰준다    

    while self.move_up(inserted_idx):
      # 내 인덱스 값을 넣고 확인한다 
      parent_idx = inserted_idx // 2
      self.heap_array[inserted_idx], self.heap_array[parent_idx] =  self.heap_array[parent_idx], self.heap_array[inserted_idx]
      # 위치를 바꿔주는 방법은 파이썬에서 간단하게 위취를 바꾸는 것으로 사용이 가능하다
      inserted_idx = parent_idx
    return True 

heap = Heap(15)
heap.insert(10)
heap.insert(8)
heap.insert(5)
heap.insert(4)
heap.insert(20)
heap.heap_array

 

4-3. 삭제 구현하기

• 최상단 노드(root 노드)를 삭제하는 방법

 

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)
    def move_up(self, inserted_idx):
        if inserted_idx <= 1:
            return False
        parent_idx = inserted_idx // 2
        if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
            return True
        else:
            return False
    def insert(self, data):
        if len(self.heap_array) == 0:
            self.heap_array.append(None)
            self.heap_array.append(data)
            return True
        self.heap_array.append(data)
        inserted_idx = len(self.heap_array) - 1
        while self.move_up(inserted_idx):
            parent_idx = inserted_idx // 2
            self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]
            inserted_idx = parent_idx
        return True

    def pop(self):
      if len(self.heap_array) <= 1:
        return None
      
      returned_data = self.heap_array[1]
      return returned_data


* 상단의 데이터 삭제시 가장 최하단부에 위치한 노드(일반적으로 가장 마지막에 추가한 노드)를 root 노드로 이동
* root 노드의 값이 child node보다 작을 경우, root 노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)
    def move_up(self, inserted_idx):
        if inserted_idx <= 1:
            return False
        parent_idx = inserted_idx // 2
        if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
            return True
        else:
            return False
    def insert(self, data):
        if len(self.heap_array) == 0:
            self.heap_array.append(None)
            self.heap_array.append(data)
            return True
        self.heap_array.append(data)
        inserted_idx = len(self.heap_array) - 1
        while self.move_up(inserted_idx):
            parent_idx = inserted_idx // 2
            self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]
            inserted_idx = parent_idx
        return True
    def move_down(self, poped_idx):
        left_child_poped_idx = poped_idx * 2
        right_child_poped_idx = poped_idx * 2 + 1
        # 자식 노드가 없을 때
        if left_child_poped_idx >= len(self.heap_array):
            return False
        # 왼쪽 자식 노드만 있을 때
        elif right_child_poped_idx >= len(self.heap_array):
            if self.heap_array[poped_idx] < self.heap_array[left_child_poped_idx]:
                return True
            else:
                return False
        # 왼쪽 오른쪽 자식 노드가 모두 있을 때
        else:
            if self.heap_array[left_child_poped_idx] > self.heap_array[right_child_poped_idx]:
                if self.heap_array[poped_idx] < self.heap_array[left_child_poped_idx]:
                    return True
                else:
                    return False
            else:
                if self.heap_array[poped_idx] < self.heap_array[right_child_poped_idx]:
                    return True
                else:
                    return False
    def pop(self):
        if len(self.heap_array) <= 1:
            return None
        returned_data = self.heap_array[1]
        self.heap_array[1] = self.heap_array[-1]
        del self.heap_array[-1]
        poped_idx = 1
        while self.move_down(poped_idx):
            left_child_poped_idx = poped_idx * 2
            right_child_poped_idx = poped_idx * 2 + 1
            # 왼쪽 자식 노드만 있을 경우
            if right_child_poped_idx >= len(self.heap_array):
                if self.heap_array[poped_idx] < self.heap_array[left_child_poped_idx]:
                    self.heap_array[poped_idx], self.heap_array[left_child_poped_idx] = self.heap_array[left_child_poped_idx], self.heap_array[poped_idx]
                    poped_idx = left_child_poped_idx
            # 왼쪽 오른쪽 노드 모두 있을 경우
            else:
                if self.heap_array[left_child_poped_idx] > self.heap_array[right_child_poped_idx]:
                    if self.heap_array[poped_idx] < self.heap_array[left_child_poped_idx]:
                       self.heap_array[poped_idx],  self.heap_array[left_child_poped_idx] = self.heap_array[left_child_poped_idx], self.heap_array[poped_idx]
                       poped_idx = left_child_poped_idx
                else:
                    if self.heap_array[poped_idx] < self.heap_array[right_child_poped_idx]:
                        self.heap_array[poped_idx], self.heap_array[right_child_poped_idx] = self.heap_array[right_child_poped_idx], self.heap_array[poped_idx]
                        poped_idx = right_child_poped_idx
        return returned_data

heap = Heap(15)
heap.insert(10)
heap.insert(8)
heap.insert(5)
heap.insert(4)
heap.insert(20)
heap.heap_array

heap.pop()