[자료구조] Heap (2)

 

안녕하세요? 주니하랑 입니다.

오늘은 자료구조와 알고리즘의 자료구조에서 Heap 구조에 대해 공부 해 보도록 하는 것이에요.

이번 피드는 Heap의 두번째 피드 입니다. 1편을 안 보신 분들은 [자료구조] Heap (1)에 관심을 주세요!

또한, 소스 코드에 대해서 확인 하고 싶으신 분들께서는 주니하랑의 Git hub에 관심을 주세요!

 

 

 

---

 

 

 

📌 Heap 삭제 (Max Heap 예시)

---

    📍 Heap Class 구현

          👉 Delete 첫번째

힙은 최상단 Node (Root Node)를 삭제하는 것이 일반적인 것이에요.

왜냐하면 힙은 본래 용도가 최대값 또는 최소값을 Root Node에 놓은 뒤 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것이기 때문인 것이에요.

 

    def pop(self):  # heap에 있는 Data 꺼내기(삭제) Method
        if len(self.heap_array) <= 1:   # 배열의 길이가 1보다 작다는 것은 Data가 없다는 의미
            return None                 # 배열에 Data가 없으므로, 연산 불가 None을 반환한다.

        returned_data = self.heap_array[1]  # 0인덱스를 쓰지 않고, 1번을 Root Node의 인덱스로 사용하기로 했기 때문에 선언

        # Root Node의 Data를 꺼내면 최초 맨 마지막 인덱스의 값을 Root Node로 올리기 때문에 아래와 같이 구현
        self.heap_array[1] = self.heap_array[-1]  # 0번 인덱스는 쓰지 않기로 했기 때문에 1번 인덱스로 옮긴다.
        retrun returned_data

 

 

          👉 Delete 두번째

상단 Data 삭제가 되면 가장 최하단부 왼쪽에 위치한 Node (일반적으로 가장 마지막에 추가된 Node)를 Root Node로 이동 시킨답니다!

Root Node의 값이 자기 자신 혹은 손자들 보다 작다면 Root Node의 Child Node 중 가장 큰 값을 가진 Node와 Root Node의 위치를 바꿔주는 연산이 필요한 것이에요. (Swap)

 

 

heap = Heap(15)  # 최초 heap에 Heap객체를 생성하여 매개변수로 15를 넣어준다.
heap.insert(10)  # heap객체에 insert Method에 10을 넣어준다.
heap.insert(8)  # heap객체에 insert Method에 8을 넣어준다.
heap.insert(5)  # heap객체에 insert Method에 5을 넣어준다.
heap.insert(4)  # heap객체에 insert Method에 4을 넣어준다.
heap.insert(20)  # heap객체에 insert Method에 20을 넣어준다.
print("heap 배열에 입력된 값은 \"" + str(heap.heap_array) + "\" 입니다.\n")  # List에 들어있는 값들을 출력해 본다.


# 결과 : [None, 20, 10, 15, 5, 4, 8]


print("heap 배열에서 꺼낸 값은 \"" + str(heap.pop()) + "\" 입니다.")   # heap 객체의 pop Method를 호출하여 Root Node를 꺼낸다.

# 결과 : heap 배열에서 꺼낸 값은 "20" 입니다.

print("heap에서 Root Node를 뺀 뒤 들어있는 값은 \"" + str(heap.heap_array) + "\" 입니다.")

# 결과 : heap에서 Root Node를 뺀 뒤 들어있는 값은 "[None, 15, 10, 8, 5, 4]" 입니다.

 

 

 

 

📌 Heap 시간 복잡도

---

트리의 높이 (depth)를 h라고 표기 했을 때, n 개의 Node를 가지는 Heap에 Data 삽입, 삽제 시에 최악의 경우 Root Node에서 Leaf (최하단 Node)까지 비교를 해야할 수도 있는 것이에요! 이 때문에 $h = log2n$에 가깝기 때문에 시간 복잡도는 $O(logn)$인 것이에요.

 

💡참고 :
빅오 (Big O) 표기법에서 $logn$에서의 $log$의 밑은 10이 아니라 2이다.
한번 실행시마다, 50%의 실행 횟수를 줄인다는 것이고, 그 말인 즉, 50%의 실행 시간을 단축 시킬 수 있다는 것이다.