알고리즘 4주차

힙

힙이란?

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리

항상 최대, 최소값들이 요구되는 연산이 있을 때 쓰기 매우 좋다

💡

그렇다면 힙을 구현하려면 어떻게 해야할까? 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨(또는 반대로) 있게 하는 자료구조. 즉 부모 노드의 값이 자식 노드의 값보다 항상 커야 함(또는 반대로) 이를 통해 최대의 값을 빠르게 구할 수 있음

      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 힙

Max 힙에 원소 추가

힙의 규칙: 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있어야함. 원소를 추가할때도 이 규칙 필요.

원소 추가
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

# 출처: 스파르타코딩클럽

코드 구현

❓

Q. 맥스 힙은 원소를 추가한 다음에도 맥스 힙의 규칙을 유지해야 한다. 맥스 힙에 원소를 추가하시오.

class MaxHeap:
    def __init__(self):
        self.items = [None]

    def insert(self, value):
        # 구현해보세요!
        return


max_heap = MaxHeap()
max_heap.insert(3)
max_heap.insert(4)
max_heap.insert(2)
max_heap.insert(9)
print(max_heap.items)  # [None, 9, 4, 2, 3] 가 출력되어야 합니다!

class MaxHeap:
    def __init__(self):
        self.items = [None]
    # 1. 새 노드를 맨 끝에 추가
    # 2. 지금 넣은 새 노드를 부모 노드와 비교. 부모보다 크다면 교체
    # 3. 해당 과정을 반복
    def insert(self, value):
        self.items.append(value)
        cur_index = len(self.items) - 1

        while cur_index > 1:
            parent_index = cur_index // 2
            if self.items[cur_index] > self.items[parent_index]:
                self.items[cur_index],self.items[parent_index] = self.items[parent_index], self.items[cur_index]
                cur_index = parent_index
            else:
                break
        return


max_heap = MaxHeap()
max_heap.insert(3)
max_heap.insert(4)
max_heap.insert(2)
max_heap.insert(9)
print(max_heap.items)  # [None, 9, 4, 2, 3] 가 출력되어야 합니다!

해당 메소드의 시간복잡도는 어떻게 될까?

💡

맥스 힙은 결국 원소를 맨 밑에 넣어서 꼭대기까지 비교하면서 올린다. 완전 이진트리의 최대 높이는

O(log(N))

이기에 반복하는 최대 횟수도

O(log(N))

맥스 힙의 원소 추가는

O(log(N))

만큼의 시간 복잡도를 가진다.

Max 힙에 원소 제거

최대 힙에서 원소를 삭제하는 방법은 최댓값 즉 루트 노드를 삭제하는 것

스택과 마찬가지로 맨 위 원소만 제거 가능하며 다른 위치의 노드는 삭제 불가능

원소를 삭제하면서도 기본 힙의 규칙인 "부모 노드가 자식 노드보다 커야한다"가 지켜져야 함

💡

1. 루트 노드와 맨 끝에 있는 원소를 교체한다. 2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다. 3. 변경된 노드와 자식 노드들을 비교합니다. 두 자식 중 더 큰 자식과 비교해서 더 크다면 자리를 바꿉니다. 4. 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 3. 과정을 반복합니다. 5. 2에서 제거한 원래 루트 노드를 반환합니다. # 출처: 스파르타코딩클럽

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

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

      **8**      Level 0
    7   6    Level 1  
   2 5 **4**     Level 2 

      **4**      Level 0
    7   6    Level 1  
   2 5 **8**     Level 2 

2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다. (이 값을 반환해줘야 합니다!)

      4      Level 0
    7   6    Level 1  
   2 5 **X**      Level 2 

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

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

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

3-2. 다시 자식 노드와 비교합니다. 
우선 부모와 왼쪽 자식을 비교합니다.
왼쪽 자식인 2는 부모인 4보다 작으니까, 제외 합니다.

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

이번에는 오른쪽 자식과 비교합니다. 5가 4보다 더 크니까 둘의 자리를 변경합니다.

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

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

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

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

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

# 출처: 스파르타 코딩클럽

코드 구현

❓

Q. 맥스 힙은 원소를 제거한 다음에도 맥스 힙의 규칙을 유지해야 한다. 맥스 힙의 원소를 제거하시오.

# 코드 스니펫
class MaxHeap:
    def __init__(self):
        self.items = [None]

    def insert(self, value):
        self.items.append(value)
        cur_index = len(self.items) - 1

        while cur_index > 1:  # cur_index 가 1이 되면 정상을 찍은거라 다른 것과 비교 안하셔도 됩니다!
            parent_index = cur_index // 2
            if self.items[parent_index] < self.items[cur_index]:
                self.items[parent_index], self.items[cur_index] = self.items[cur_index], self.items[parent_index]
                cur_index = parent_index
            else:
                break

    def delete(self):
        # 구현해보세요!
        return 8  # 8 을 반환해야 합니다.


max_heap = MaxHeap()
max_heap.insert(8)
max_heap.insert(7)
max_heap.insert(6)
max_heap.insert(2)
max_heap.insert(5)
max_heap.insert(4)
print(max_heap.items)  # [None, 8, 7, 6, 2, 5, 4]
print(max_heap.delete())  # 8 을 반환해야 합니다!
print(max_heap.items)  # [None, 7, 5, 6, 2, 4]

class MaxHeap:
    def __init__(self):
        self.items = [None]

    def insert(self, value):
        self.items.append(value)
        cur_index = len(self.items) - 1

        while cur_index > 1:  # cur_index 가 1이 되면 정상을 찍은거라 다른 것과 비교 안하셔도 됩니다!
            parent_index = cur_index // 2
            if self.items[parent_index] < self.items[cur_index]:
                self.items[parent_index], self.items[cur_index] = self.items[cur_index], self.items[parent_index]
                cur_index = parent_index
            else:
                break
    # 1. 루트 노드를 맨 마지막 우측 노드와 교환(self.items의 마지막 원소. 즉 self.items[-1])
    # 2. 루트 노드를 배열에서 제거한뒤 저장한다.
    # 3. 현재 맨 위 노드(원래 마지막 우측이었던) 노드를 자식 노드와 비교하면서 내려보낸다. 이때 둘 중 더 큰 자식 노드와 교환한다.
    # 4. 이 과정을 자식들 보다 자신이 더 크거나(max_index가 자신) 가장 로우 레벨 바닥에 내려갔을 때 까지 반복

    def delete(self):
        # 1
        self.items[1], self.items[-1] = self.items[-1], self.items[1]
        prev_max = self.items.pop()
        cur_index = 1
        while cur_index <= len(self.items) - 1:
            left_child_index = cur_index * 2
            right_child_index = cur_index * 2 + 1
            max_index = cur_index

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

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

            if max_index == cur_index:
                break

            self.items[cur_index], self.items[max_index] = self.items[max_index], self.items[cur_index]
            cur_index = max_index

        return prev_max  # 8 을 반환해야 합니다.


max_heap = MaxHeap()
max_heap.insert(8)
max_heap.insert(7)
max_heap.insert(6)
max_heap.insert(2)
max_heap.insert(5)
max_heap.insert(4)
print(max_heap.items)  # [None, 8, 7, 6, 2, 5, 4]
print(max_heap.delete())  # 8 을 반환해야 합니다!
print(max_heap.items)  # [None, 7, 5, 6, 2, 4]

해당 메소드의 시간복잡도는 어떻게 될까?

💡

결국 원소를 맨 위에 올려서 바닥까지 비교하면서 계산한다. 완전 이진트리의 최대 높이는

O(log(N))

, 그러면 반복하는 최대 횟수도

O(log(N))

맥스 힙의 원소 삭제는

O(log(N))

만큼의 시간 복잡도를 가진다.

알고리즘 4주차 - BFS, DFS (0)	2021.02.08
알고리즘 4주차 - 그래프 (0)	2021.02.05
알고리즘 4주차 - 트리 (0)	2021.02.03
알고리즘 4주차 - 개요(트리, 힙, 그래프, BFS, DFS, 동적계획법) (0)	2021.02.02
알고리즘 3주차 - 숙제 (0)	2021.02.01

우기의 알

우기의 알