[자료구조] 힙(Heap), 최대힙(MaxHeap), 최대힙 삽입, 최대힙 추출, 이진트리, 이진탐색트리

---

힙(Heap)

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) //왼쪽부터 쭉쭉 채움!

 

항상 최대/최소의 값들이 필요한 연산이 있다면? 바로 힙을 쓰면 되겠죠!

 

힙을 구현하려면 어떻게 해야할까요? 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조입니다. 다시 말하면 부모 노드의 값이 자식 노드의 값보다 항상 커야 합니다. 그러면 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 가겠죠! 따라서 최대의 값들을 빠르게 구할 수 있게 되는 것입니다.

 

      8      Level 0
    6   3    Level 1
     2 1     Level 2  # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다!

      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
   4 2 1     Level 2  # 자식 노드보다 크니까 힙이 맞습니다!


      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
   4 2 5     Level 2  # 자식 노드보다 크지 않아서 힙이 아닙니다..!

 

힙은 다음과 같이 최대값을 맨 위로 올릴수도 있고, 최솟값을 맨 위로 올릴 수도 있습니다!

최댓값이 맨 위인 힙을 Max 힙, 최솟값이 맨 위인 힙을 Min 힙이라고 합니다.

 

• BST(이진탐색트리)와 다르다. 좌, 우 자식의 위치가 대소관계를 반영하지 않음.
• 계산 편의를 위해 인덱스는 1부터 사용한다. (parent: x, left: 2x, right: 2x+1) //0부터도 상관없지만 이게 편함

  =>  [None, 10, 15, 30, 40, 50, 100, 40] // 인덱스 1 부터 사용하므로 인덱스 0은 None

 

이진 트리(Binary Tree)와 완전 이진 트리(Complete Binary Tree)는 트리 자료구조의 두 가지 유형입니다. 이 두 가지는 노드의 배치 규칙에 따라 구별됩니다.

 

이진 트리 (Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조입니다. 다음은 이진 트리의 주요 특징입니다:

• 각 노드는 최대 두 개의 자식 노드(왼쪽 자식과 오른쪽 자식)를 가질 수 있습니다.
• 이진 트리의 구조에는 특별한 제약이 없습니다. 즉, 모든 노드가 두 자식 노드를 가질 필요는 없고, 트리의 깊이도 균등할 필요가 없습니다.

예시:

    A
   / \
  B   C
 /   / \
D   E   F

 

 

완전 이진 트리 (Complete Binary Tree)

완전 이진 트리는 특정한 규칙을 따라 모든 레벨에서 노드가 최대한 왼쪽부터 채워진 이진 트리입니다. 완전 이진 트리의 주요 특징은 다음과 같습니다:

• 모든 레벨이 완전히 채워져 있어야 하며, 마지막 레벨의 노드들은 모두 왼쪽부터 차례로 채워져야 합니다.
• 완전 이진 트리는 배열로 쉽게 표현될 수 있으며, 배열 인덱스를 통해 부모-자식 관계를 쉽게 찾을 수 있습니다.

예시:

    A
   / \
  B   C
 / \ /
D  E F

 

비교

• 구조: 이진 트리는 구조에 대한 제약이 거의 없지만, 완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져야 하며, 마지막 레벨의 노드는 왼쪽부터 차례로 채워져야 합니다.
• 노드 배치: 완전 이진 트리는 더 엄격한 노드 배치 규칙을 따릅니다.
• 배열 표현: 완전 이진 트리는 배열로 쉽게 표현할 수 있으며, 인덱스를 통해 부모와 자식 노드를 쉽게 찾을 수 있습니다.

 

이진 탐색 트리 (Binary Search Tree, BST)

• 구조: 각 노드는 최대 두 개의 자식 노드를 가질 수 있습니다.
• 제약 조건:
  • 왼쪽 자식 노드의 값은 부모 노드의 값보다 작아야 합니다.
  • 오른쪽 자식 노드의 값은 부모 노드의 값보다 커야 합니다.
  • 이러한 제약 조건은 재귀적으로 모든 노드에 적용됩니다.

예시:

    5
   / \
  3   8
 / \ / \
2  4 6  9

 

• 노드 배치 규칙: 이진 탐색 트리는 각 노드의 값이 특정 규칙(왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰)을 따릅니다. 이진 트리는 이러한 규칙 없이 자유롭게 노드가 배치될 수 있습니다.
• 연산의 효율성: 이진 탐색 트리는 검색, 삽입, 삭제 등의 연산이 평균적으로 O(log⁡n)의 시간 복잡도를 갖습니다. 이진 트리는 이러한 효율성을 보장하지 않습니다

 

 

힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있어야 합니다.

---

최대 힙 - 삽입 

원소를 추가하거나 삭제할때도 위의 규칙이 지켜져야 합니다! 원소를 추가할 때는 다음과 같이 하시면 됩니다.

1. 원소를 맨 마지막에 넣습니다.

2. 그리고 부모 노드와 비교합니다. 만약 더 크다면 자리를 바꿉니다.

3. 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2. 과정을 반복합니다.

이 맥스 힙에서 9를 추가해보겠습니다!
      8      Level 0
    6   3    Level 1  
   4 2 1     Level 2 

1. 맨 마지막에 원소를 넣습니다.

      8      Level 0
    6   3    Level 1  
   4 2 1 "9"   Level 2 

2-1. 부모 노드와 비교합니다. 3보다 9가 더 크니까! 둘의 자리를 변경합니다.

      8      Level 0
    6   "3"    Level 1  
   4 2 1 "9"   Level 2 

      8      Level 0
    6   9    Level 1  
   4 2 1 3   Level 2 

2-2. 다시 부모 노드와 비교합니다. 8보다 9가 더 크니까! 둘의 자리를 변경합니다.

      8      Level 0
    6   "9"    Level 1  
   4 2 1 "3"   Level 2 

      "9"      Level 0
    6   "8"    Level 1  
   4 2 1 3   Level 2 

3. 가장 위에 도달했으므로 멈춥니다. 힙의 특성을 그대로 유지해 데이터를 삽입했습니다!

      9      Level 0
    6   8    Level 1  
   4 2 1 3   Level 2

 

최대 힙 - 삽입  시간 복잡도

결국 원소를 맨 밑에 넣어서 꼭대기까지 비교하면서 올리고 있습니다.

완전 이진트리의 최대 높이는 O(log(N)) 이라고 말씀 드렸었죠!

그러면, 반복하는 최대 횟수도 O(log(N)) 입니다.

즉! 맥스 힙의 원소 추가는 O(log(N)) 만큼의 시간 복잡도를 가진다고 분석할 수 있습니다. (최악의 경우)

 

최대 힙 삽입 구현

 

class BinaryMaxHeap:
    def __init__(self):
        # 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
        self.items = [None]

    def insert(self, k):
        self.items.append(k)
        self._percolate_up()

    def _percolate_up(self):
        # percolate: 스며들다.
        
        # 힙 배열[None,8,6,3,4,2,1] => 배열의 길이에서 None을 뺀 것. 인덱스 1부터 시작하므로
        cur = len(self.items) - 1
        
        # 나의 좌표값으로 부터의 부모의 좌표값 (우리가 인덱스를 1로 잡은 이유!! cur//2 -> 편리 )
        # left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2
        parent = cur // 2

        while parent > 0:
            if self.items[cur] > self.items[parent]:
            	# 부모-자식의 자리를 바꿈
                self.items[cur], self.items[parent] = self.items[parent], self.items[cur]
			
            # 부모와 자리를 바꿨으므로, 이제 내 위치는 부모의 위치로 잡음
            cur = parent
            parent = cur // 2

---

최대 힙 _ 추출

최대 힙에서 원소를 추출하는 방법은 최댓값, 루트 노드를 삭제하는 것입니다!

스택과 같이 맨 위에 있는 원소(root)만 제거할 수 있고, 다른 위치의 노드를 삭제할 수는 없습니다!

(세번째로 큰 원소를 제거하고 싶다면, 추출을 3번 진행해야함.)

또한 맥스 힙에 원소를 추가했던 것과 마찬가지로 원소를 삭제할때도 힙의 규칙이 지켜져야 합니다!

아래와 같은 방법으로 하면 됩니다.

 

1. 루트 노드와 맨 끝에 있는 원소를 교체한다.

2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다.

3. 변경된 노드와 자식 노드들을 비교합니다. 두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꿉니다.

4. 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 3. 과정을 반복합니다.

5. 2에서 제거한 원래 루트 노드를 반환합니다. 

이 맥스 힙에서 원소를 제거해보겠습니다! (항상 맨 위의 루트 노드가 제거 됩니다.)
      8      Level 0
    6   7    Level 1  
   2 5 4 3   Level 2 

1. 루트 노드와 맨 끝에 있는 원소를 교체한다.

      "8"      Level 0
    6   7    Level 1  
   2 5 4 "3"   Level 2 

      "3"      Level 0
    7   6    Level 1  
   2 5 4 "8"   Level 2 

2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제합니다. 
이 값이 기존 맥스힙에 있던 가장 큰 값입니다. 따라서 이 값을 마지막에는 반환해줘야 합니다!

      3      Level 0
    6   7    Level 1  
   2 5 4 "X"   Level 2 

3-1. 변경된 노드를 더 큰 자식 노드와 비교해야 합니다. 
우선 부모와 왼쪽 자식을 비교합니다. 그리고 부모와 오른쪽 자식을 비교합니다.
그리고 부모 보다 큰 자식 중, 더 큰 자식과 변경해야 합니다.
왼쪽 자식인 6과 오른쪽 자식인 7 중에서 7이 더 크고, 부모인 3보다 크니까 둘의 자리를 변경합니다.

      "3"      Level 0
    "6"   "7"    Level 1  
   2 5 4     Level 2 

      "7"      Level 0
    6   "3"    Level 1  
   2 5 4     Level 2 

3-2. 다시 자식 노드와 비교합니다. 
우선 부모와 왼쪽 자식을 비교합니다.
왼쪽 자식인 4는 부모인 3보다 더 크니까 둘의 자리를 변경합니다.

      7      Level 0
    6   "3"    Level 1  
   2 5 "4"     Level 2 

      7      Level 0
    6   "4"    Level 1  
   2 5 "3"     Level 2 


4. 가장 아래 레벨에 도달했으므로 멈춥니다. 힙의 특성을 그대로 유지해 데이터를 삭제했습니다!

      7      Level 0
    6   4    Level 1  
   2 5 3     Level 2 

5. 그리고, 아까 제거한 원래 루트 노드, 8을 반환하면 됩니다!

 

최대 힙 - 추출 시간복잡도

결국 원소를 맨 위에 올려서 바닥까지 비교하면서 내리고 있습니다.

완전 이진트리의 최대 높이는 O(log(N)) 이므로, 반복하는 최대 횟수도 O(log(N)) 입니다.

즉! 맥스 힙의 원소 삭제는 O(log(N))만큼의 시간 복잡도를 가진다고 분석할 수 있습니다.

 

 

최대 힙 구현

class BinaryMaxHeap:
    def __init__(self):
        # 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
        self.items = [None]

    def insert(self, k):
        self.items.append(k)
        self._percolate_up()

    def _percolate_up(self):
        # percolate: 스며들다.
        cur = len(self.items) - 1
        # left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2
        parent = cur // 2

        while parent > 0:
            if self.items[cur] > self.items[parent]:
                self.items[cur], self.items[parent] = self.items[parent], self.items[cur]

            cur = parent
            parent = cur // 2

    def extract(self):
        if len(self.items) - 1 < 1:
            return None
        
        # 제일 꼭대기에 있는 root
        root = self.items[1]
        # 가장 마지막 노드와 root의 위치를 바꿔준다.
        self.items[1] = self.items[-1]
        # 마지막 노드(root였던 것)를 지워준다.
        self.items.pop()
        self._percolate_down(1)
		
        # 루트 반환
        return root

    def _percolate_down(self, cur):
        biggest = cur
        left = 2 * cur
        right = 2 * cur + 1

        if left <= len(self.items) - 1 and self.items[left] > self.items[biggest]:
            biggest = left

        if right <= len(self.items) - 1 and self.items[right] > self.items[biggest]:
            biggest = right

        if biggest != cur:
            self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur]
            self._percolate_down(biggest)

---

예제.  k번째 큰 요소

Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Can you solve it without sorting?
 
Example 1:
Input: nums = [3,2,1,5,6,4], k = 2 Output: 5   // 2번째로 큰 요소 -> 5
Example 2:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4 // 4번째로 큰 요소 -> 4 (같은 두수는 다르게 count ex. 5,5 각각 cnt)

https://leetcode.com/problems/kth-largest-element-in-an-array/description/

 

풀이: 최대힙을 만든 후, k번 추출한다. (큰 순서대로 힙에서 추출되므로) 마지막으로 추출된 루트값을 반환한다.

 

test_max_heap.py

import heapq

from heap.structures import BinaryMaxHeap

# 맥스힙 직접 구현
def test_maxheap_we_made(lst, k):
    maxheap = BinaryMaxHeap()

    # for 문을 눈여겨봐두세요.
    # 힙정렬 시간복잡도 계산의 토대입니다.
    for elem in lst:
        maxheap.insert(elem)

    return [maxheap.extract() for _ in range(k)][k - 1]

# 내장 함수 heapq 사용 // 보통 우리는 이런 식으로 코딩하게 될 것!
def test_maxheap_heapq(lst, k):
    return heapq.nlargest(k, lst)[-1]  # [-1]:가장 마지막 요소


assert test_maxheap_we_made([3, 2, 3, 1, 2, 4, 5, 5, 6], 1) == 6
assert test_maxheap_we_made([3, 2, 3, 1, 2, 4, 5, 5, 6], 2) == 5
assert test_maxheap_we_made([3, 2, 3, 1, 2, 4, 5, 5, 6], 3) == 5
assert test_maxheap_we_made([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) == 4
assert test_maxheap_we_made([3, 2, 3, 1, 2, 4, 5, 5, 6], 5) == 3
assert test_maxheap_we_made([3, 2, 3, 1, 2, 4, 5, 5, 6], 6) == 3
assert test_maxheap_we_made([3, 2, 3, 1, 2, 4, 5, 5, 6], 7) == 2
assert test_maxheap_we_made([3, 2, 3, 1, 2, 4, 5, 5, 6], 8) == 2
assert test_maxheap_we_made([3, 2, 3, 1, 2, 4, 5, 5, 6], 9) == 1


assert test_maxheap_heapq([3, 2, 3, 1, 2, 4, 5, 5, 6], 1) == 6
assert test_maxheap_heapq([3, 2, 3, 1, 2, 4, 5, 5, 6], 2) == 5
assert test_maxheap_heapq([3, 2, 3, 1, 2, 4, 5, 5, 6], 3) == 5
assert test_maxheap_heapq([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) == 4
assert test_maxheap_heapq([3, 2, 3, 1, 2, 4, 5, 5, 6], 5) == 3
assert test_maxheap_heapq([3, 2, 3, 1, 2, 4, 5, 5, 6], 6) == 3
assert test_maxheap_heapq([3, 2, 3, 1, 2, 4, 5, 5, 6], 7) == 2
assert test_maxheap_heapq([3, 2, 3, 1, 2, 4, 5, 5, 6], 8) == 2
assert test_maxheap_heapq([3, 2, 3, 1, 2, 4, 5, 5, 6], 9) == 1

 

structures.py

class BinaryMaxHeap:
    def __init__(self):
        # 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
        self.items = [None]

    # len 쓸 일이 많은데 항상 len-1 해주어야함 (인덱스 1부터 사용하므로)
    # 파이썬 내장 메소드 __len__
    # 클래스들은 기본적으로 가지고 있음 -> 이걸 상속해준다!
    def __len__(self):
        # len() 연산을 가능하게 하는 매직 메서드 덮어쓰기(Override).
        return len(self.items) - 1

    def _percolate_up(self):
        # percolate: 스며들다.
        cur = len(self)
        # left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2
        parent = cur // 2

        while parent > 0:
            if self.items[cur] > self.items[parent]:
                self.items[cur], self.items[parent] = self.items[parent], self.items[cur]

            cur = parent
            parent = cur // 2

    def _percolate_down(self, cur):
        biggest = cur
        left = 2 * cur
        right = 2 * cur + 1

        if left <= len(self) and self.items[left] > self.items[biggest]:
            biggest = left

        if right <= len(self) and self.items[right] > self.items[biggest]:
            biggest = right

        if biggest != cur:
            self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur]
            self._percolate_down(biggest)

    def insert(self, k):
        self.items.append(k)
        self._percolate_up()

    def extract(self):
        if len(self) < 1:
            return None

        root = self.items[1]
        self.items[1] = self.items[-1]
        self.items.pop()
        self._percolate_down(1)

        return root

 

매직 메소드

언더바(_)로 둘러쌓인 메소드. 
파이썬에서 어떤 용도로 쓸건 지 미리 정해 둔 함수.
자기 자신의 것을 상속받아 덮어쓸 수 있다.(오버라이딩)

ex.

def __init__(self):
	pass
def __len__(self):
	pass

 

 

💡 heapq 내장함수

파이썬에서 힙은 최소힙. 

최대힙을 사용하려면 최소힙을 만든 후 최대힙으로 바꿔야한다.

 

https://docs.python.org/ko/3/library/heapq.html