Heap

BIS·2024년 1월 6일
algorithm

Algorithm

목록 보기
2/4
post-thumbnail

Heap

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

항상 최대/최소의 값들이 필요한 연산에서 자주 사용된다.

Heap은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조이다.

부모 노드의 값이 자식 노드의 값보다 항상 커야 한다.

      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  # 자식 노드보다 크지 않아서 힙이 아니다
  1. 최댓값이 맨 위인 Heap을 Max Heap
  2. 최솟값이 맨 위인 Heap을 Min Heap이라고 한다.
    `BST(이진탐색트리)와 다르다. 좌, 우 자식의 위치가 대소관계를 반영하지 않는다.

최대 Heap_삽입

✅ 힙의 규칙

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

1. 원소를 맨 마지막에 넣는다.
2. 부모 노드와 비교한다. 만약 부모보다 크다면 자리를 바꾼다.
3. 부모 노드보다 작거나 가장 위(root)에 도달하지 않을 때까지 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

⌚ 시간 복잡도

Max Heap의 원소 추가는 O(log(N)만큼의 시간 복잡도를 가진다고 할 수 있다.

최대 Heap_추출

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


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

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을 반환하면 됩니다!

⌚ 시간복잡도

Max Heap의 원소 삭제는 O(log(N))만큼의 시간 복잡도를 가진다고 할 수 있다.

Heap 구현

✅ code

class BinaryMaxHeap:
    def __init__(self):
        # 계산 편의를 위해 첫번째 인덱스는 0이 아니라 1로 둔다.
        self.items = [None]

    def __len__(self):
        return len(self.items) - 1

    # _ 하나만 쓰는 이유는 클래스 안에서만 사용하기 위해서 작성한 것이다.
    def _percolate_up(self):
        # 전체 길이를 구하면 마지막 원소를 가르키기 때문이다.
        cur = len(self)
        # 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

✅ code 설명

초기화

    def __init__(self):
        # 계산 편의를 위해 첫번째 인덱스는 0이 아니라 1로 둔다.
        self.items = [None]

계산의 편의를 위해 1번째 인덱스부터 사용한다.

    def __len__(self):
        return len(self.items) - 1

__를 함수명에 붙이게 되면 오버라이드와 같은 효과를 지닌다.

인덱스를 0번째에 None을 두고 시작하기 때문에 len()을 구할 때 1을 빼서 계산한다.

값 삽입

    def insert(self, k):
        self.items.append(k)
        self._percolate_up()
        
        # _ 하나만 쓰는 이유는 클래스 안에서만 사용하기 위해서 작성한 것이다.
    def _percolate_up(self):
        # 전체 길이를 구하면 마지막 원소를 가르키기 때문이다.
        cur = len(self)
        # 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

insert()는 새로 들어온 값을 heap에 넣고, 부모 노드와 계속해서 값을 비교한다.

cur은 현재 삽입된 값의 위치(마지막에 들어가기 때문에 배열의 길이와 마지막 인덱스는 일치한다.)

이진 트리의 경우 자식 엔덱스를 반으로 나눈 값이 부모가 된다.

cur = 현재 인덱스, parent = 부모 인덱스의 값을 비교하면서 현재 인덱스의 값이 더 클 경우 부모와 값을 변경하고 인덱스의 위치도 변경한다.

값 추출

    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
        
    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)

값 추출의 경우 heap의 정렬을 유지한채 root의 값을 꺼내와야 한다.

root의 값을 추출하고 root 값과 마지막 인덱스 값을 변경한다.

_percolate_down(self, cur) 함수의 경우

biggest : 최초에 부모 값
left : 자식의 좌측 값
right : 자식의 우측 값

현재 마지막 인덱스가 root와 변경되서 가장 상단(인덱스에서 가장 앞)에 위치해 있다.

부모 노드에서 2, 2 + 1 한 값들은 자식 노드가 된다.

자식의 왼쪽부터 값을 확인하며 부모, 좌측 자식, 우측 자식 3개를 전부 비교하여 가장 큰 값을 부모 노드에 위치 시킨다.

만약 부모 노드와 자식 노드의 값이 변경되었다면 인덱스 위치를 변경 시킨다.

위 과정을 계속해서 반복하게 되면 Heap 정렬을 계속해서 유지 할 수 있다.

파이썬에서의 Heap

✅ 파이썬에서 Heap은 heapq를 통해 위 과정을 간편하게 사용할 수 있다.

  1. heapq.heappush(heap, item): 힙에 원소를 추가한다.

    • heap: 힙 리스트
    • item: 추가할 원소

  2. heapq.heappop(heap): 힙에서 가장 작은 원소를 제거하고 반환한다.

    • heap: 힙 리스트

  3. heapq.heapify(iterable): 주어진 iterable을 힙으로 변환한다. 기존 리스트를 힙으로 만드는 데 사용된다.

  4. heapq.heappushpop(heap, item): 힙에 원소를 추가한 후 가장 작은 원소를 반환한다. 추가와 팝을 동시에 수행하여 한 번의 팝 작업을 줄일 수 있다.

  5. heapq.nlargest(n, iterable, key=None): 주어진 iterable에서 가장 큰 n개의 원소를 반환한다.

key 함수를 사용하여 원소 비교 방식을 지정할 수 있다.

  1. heapq.nsmallest(n, iterable, key=None): 주어진 iterable에서 가장 작은 n개의 원소를 반환한다.

key 함수를 사용하여 원소 비교 방식을 지정할 수 있다.

profile
BIS
Backend Developer
이전 포스트

HashMap (개별 체이닝 방식)

다음 포스트

Linked List (연결 리스트)

0개의 댓글