[자료구조] 힙 Heap

Heap

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

---

사용하는 이유

• 배열의 최대값 최소값 찾기 복잡도 \( O_{n} \) (데이터 넣고 빼는 거 까지)
• heap의 최대값 최소값 찾기 복잡도 \( O_{logn} \) (데이터 넣고 빼는 거 까지)
• 우선 순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 경우에 사용함

---

구조

• Max Heap : 최대값을 구하기 위한 구조
• Min Heap : 최소값을 구하기 위한 구조
• 2가지 조건
  • Max Heap의 경우 각 node의 값은 해당 mode의 자식 node가 가진 값보다 크거나 같아야 함.(Min Heap은 반대)
  • 완전 이진 트리 형태를 가짐

https://hackr.io/blog/stack-vs-heap

---

Heap 과 Binary Search Tree

Heap

• Max Heap의 경우 Parent Node의 값이 Child Node보다 크거나 같음
• Child Node는 따로 정해진 규칙없이 배치된다
• 최대, 최소값을 구하기 위한 구조

Binary Search Tree

• Parent Node의 값이 가장 크고 left Child Node의 값이 right Chile Node값보다 작다
• 탐색을 위한 구조

---

 

 

Heap 구현¶

배열 구현¶

 

 

• 배열은 인덱스가 0부터 시작하지만, 편의를 위해 root node의 인덱스는 1로 지정 (0에는 유의미한 값이 들어가지 않음)
  • Parent Node's index = Child Node's index // 2
  • Left Child Node's index = Parent Node's index * 2
  • Righ Child Node's index = Parent Node's index * 2 + 1

 

 

heap class

 

In [156]:

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)
    
    def move_down(self, popped_idx):
        left_child_popped_idx = popped_idx * 2
        right_child_popped_idx = popped_idx * 2 + 1
        
        # case1: No left node
        if left_child_popped_idx >= len(self.heap_array):
            return False
        # case2: No right node
        elif right_child_popped_idx >= len(self.heap_array):
            if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                return True
            else:
                return False
        # case3: exgist both node
        else:
            if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]:
                if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                    return True
                else:
                    return False
            else:
                if self.heap_array[popped_idx] < self.heap_array[right_child_popped_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]
        popped_idx = 1
        
        while self.move_down(popped_idx):
            left_child_popped_idx = popped_idx * 2
            right_child_popped_idx = popped_idx * 2 + 1

            # case2: No right node
            if right_child_popped_idx >= len(self.heap_array):
                if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                    self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]
                    popped_idx = left_child_popped_idx
            # case3: exgist both node
            else:
                if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]:
                    if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                        self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]
                        popped_idx = left_child_popped_idx
                else:
                    if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
                        self.heap_array[popped_idx], self.heap_array[right_child_popped_idx] = self.heap_array[right_child_popped_idx], self.heap_array[popped_idx]
                        popped_idx = right_child_popped_idx
        
        return returned_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) == 1:
            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    

 

In [157]:

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

 

 

[None, 20, 10, 15, 5, 4, 8]

 

In [158]:

heap.pop()

 

Out[158]:

20

 

In [159]:

heap.heap_array

 

Out[159]:

[None, 15, 10, 8, 5, 4]

 

In [160]:

heap.heap_array

 

Out[160]:

[None, 15, 10, 8, 5, 4]