[자료구조] Heap (1)

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

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

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

 

---

 

 

📌 Heap 구조

---

 

    📍 Heap (힙)이란?

Data에서 최대값과 최소값을 빠르게 찾기 위해 고안된 Complete Binary Tree (완전 이진 트리)인 것이에요.

그럼 완전 이진 트리가 무엇일까요? Node를 삽입할 때, 최 하단 왼쪽 Node부터 차례대로 삽입하는 것을 말한답니다!

 

완전 이진 트리

 

          👉 힙을 사용하는 이유

• 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 $O(n)$이 걸린다.
• 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, $O(logn)$이 걸린다.
• 우선 순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용

 

 

 

 

    📍 Heap 구조

 

힙은 최대값을 구하기 위한 구조(최대 힙, Max Heap)와 최소값을 구하기 위한 구조(최소 힙, Min Heap)로 분류할 수 있는 것이에요.

힙은 다음과 같이 두 가지 조건을 가지고 있는 자료 구조랍니다!

1. 각 Node의 값은 해당 Node의 자식 Node가 가진 값보다 크거나 같다(최대 힙의 경우).
   • 최소 힙의 경우는 각 Node의 값은 해당 Node의 자식 Node가 가진 값보다 작거나 같다.
2. 완전 이진 트리 형태를 갖음

 

          👉 힙과 이진 탐색 트리의 공통점과 차이점

• 공통점 : 힙과 이진 탐색 트리는 모두 이진 트리 구조
• 차이점 : 힙은 각 Node의 값이 자식 Node보다 크거나 같다(Max Heap의 경우).
  • 이진 탐색 트리는 부모 Node 기준 왼쪽 자식 Node의 값이 가장 작고, 다음 부모 Node, 다음 부모 Node 기준 오른쪽 Node 값이 가장 크다.
  • 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값이 오른쪽에 와야 한다라는 조건이 없다.
    • 힙의 부모 Node 기준 왼쪽 및 오른쪽 자식 노드의 값은 오른쪽이 클수도 왼쪽이 클수도 있다.
• 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대 / 최소값 검색을 위한 구조 중 하나이다.

 

 

 

 

 

 

📌 Heap 동작

---

Data를 힙 구조에 삽입, 삭제하는 과정을 우리 한번 이해 해 보아요!

 

 

 

    📍 Heap에 Data 삽입 - 기본 동작

힙은 완전 이진 트리이므로, 삽입할 Node는 기본적으로 왼쪽 최하단부 Node부터 Data가 채워지는 것이에요.

 

 

 

 

 

          👉 삽입할 Data가 Heap의 Data보다 클 경우? (Max Heap 예시)

먼저 삽입된 Data는 완전 이진 트리 구조에 맞추어 최하단부 왼쪽 Node부터 채워지는 것이에요.

채워진 Node 위치에서, 부모 Node보다 값이 클 경우, 부모 Node와 위치를 바꿔주는 작업을 반복(Swap)해야 한답니다!

 

20이라는 Data가 들어올 때, 최초 최하단 왼쪽 Node부터 Node가 채워지는 것이에요. 5, 4라는 Data를 가진 Node가 있으니 그 다음 빈 공간에 20이 들어가게 됩니다.

 

그런뒤 20과 부모 Node의 값을 비교를 하는데, 부모 Node의 값이 더 작다면 서로 위치를 바꾸는 것이에요.

 

그런 뒤 또 상위 부모 Node와 값을 비교를 하는데, 부모 Node가 값이 크다면 변화 없이 가만히 있고, 끝이 나겠지만, 그렇지 않다면 또 한번의 위치 변화가 생기는 것이에요.

 

 

 

 

 

 

    📍 Heap에 Data 삭제 (Max Heap 예시)

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

왜냐하면 힙의 용도는 최대값 또는 최소값을 Root Node에 놓기 때문이며, Heap은 최대값과 최소값을 빠르게 구하기 위해 만들어진 자료구조이기 때문에 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것이에요.

그럼 이제 Root Node가 비웠다면 다음 작업으로 상단의 Data 삭제 시, 가장 최하단부 왼쪽에 위치한 Node(일반적으로 가장 마지막에 추가한 Node)를 Root Node로 이동 시킨답니다!

Root Node의 값이 Child Node보다 작다면 Root Node의 Child Node 중 가장 큰 값을 가진 Node와 Root Node와 위치를 바꾸는 작업을 다시 시작하게 된답니다. (Swap)

 

 

위에 그림에서 8이 Root Node로 올라간 뒤 그 중 가장 큰 값인 15와 비교를 해서 자기 보다 크기 때문에 위치를 바꾸는 것이에요.

그런데, 만약 15 밑에 또다른 Child Node가 있었고, 그 숫자가 또 8보다 크다면? 이 작업은 더 반복 되게 될 것이에요.

 

 

 

 

📌 Heap 구현

---

    📍 Heap에 Data 삭제 (Max Heap 예시)

 

• 일반적으로 힙 구현시 배열 자료구조를 활용한다고 합니다!
• 배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해, root 노드 인덱스 번호를 1로 해볼 것이에요!
  • 부모 노드 인덱스 번호 (parent node's index) = 자식 노드 인덱스 번호 (child node's index) // 2
    (나누기 2)
  • 왼쪽 자식 노드 인덱스 번호 (left child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2
  • 오른쪽 자식 노드 인덱스 번호 (right child node's index) = (부모 노드 인덱스 번호 (parent node's index) * 2) + 1

 

 

 

 

          👉 10을 가진 Node(Index Number 2)의 부모 Node Index Number 구하기!

2 // 2

# 결과 : 1

 

 

          👉 15을 가진 Node(Index Number 1)의 왼쪽 자식 Node Index Number 구하기!

1 * 2

# 결과 : 2

 

 

          👉 15을 가진 Node(Index Number 1)의 오른쪽 자식 Node Index Number 구하기!

(2 * 2) + 1

# 결과 : 5

 

 

 

📌 Heap에 Data 삽입 구현 (Max Heap 예시)

---

    📍 Heap Class 구현

class Heap:
    def __init__(self, data):  # 생성자 생성 (data를 매개변수로 받는다.)
        self.heap_array = list()  # heap_array를 리스트로 만든다.
        
        # heap_arrary에 최초 0번 인덱스에 None을 넣는다. (1번 인덱스부터 사용하기 위함)
        self.heap_array.append(None)
        
        # 1번 인덱스부터 data가 들어오게 한다.
        self.heap_array.append(data)
        
        
heap = Heap(1)
print(heap.heap_arrary)

# 결과 : [None, 1]

 

 

          👉 Insert Method 구현

인덱스 번호는 1부터 시작하도록 할 것이고, 아래 그림처럼 작동하도록 구현 해 보겠습니다!

 

class Heap:
    def __init__(self, data):  # 생성자 생성 (data를 매개변수로 받는다.)
        self.heap_array = list()  # heap_array를 리스트로 만든다.
        
        # heap_arrary에 최초 0번 인덱스에 None을 넣는다. (1번 인덱스부터 사용하기 위함)
        self.heap_array.append(None)
        
        # 1번 인덱스부터 data가 들어오게 한다.
        self.heap_array.append(data)  
        
        
    def insert(self, data):  # 배열에 Data를 입력하기 위한 Method
        if len(self.heap_array) == 0:  # 배열의 길이가 0이라면? 즉, 배열에 Data가 들어있지 않다면?
            self.heap_array.append(None)  # 초기화를 위해 0번 인덱스에 None을 넣어준다.
            self.heap_array.append(data)  # 그런뒤 1번 인덱스에 Data가 들어오도록 한다.
            return True  # 참을 반환해준다.
		
        # 배열의 길이가 0이 아니라면? 입력된 Data를 배열의 마지막 인덱스 번호에 입력해 준다.
        self.heap_array.append(data)
        return True  # 참을 반환해준다.

 

 

삽입한 Node가 자신의 부모 Node보다 가진 값이 크다면 부모 Node와 삽입한 Node의 위치를 바꿔야 하는 것이에요.

삽입한 Node가 Root Node가 되거나, 부모 Node보다 값이 작거나 같을 때까지 빙빙빙~ 반복을 한답니다!

 

          👉 특정 Node의 관련 Node의 위치 알아내기!

• 부모 노드 인덱스 번호 (parent node's index) = 자식 노드 인덱스 번호 (child node's index) // 2 
  (나누기 2)
• 왼쪽 자식 노드 인덱스 번호 (left child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2
• 오른쪽 자식 노드 인덱스 번호 (right child node's index) = (부모 노드 인덱스 번호 (parent node's index) * 2) + 1

 

 

 

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을 넣어준다.

# List에 들어있는 값들을 출력해 본다.
print("heap 배열에 입력된 값은 \"" + str(heap.heap_array) + "\" 입니다.\n")  
print("=" * 100 + "\n")



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

 

 

---

 

주니하랑의 글이 마음에 드셨나요? 구독과 공감! 그리고, 댓글은 주니하랑에게 많은 힘이 됩니다