[자료구조] Heap

파이톨치·2022년 5월 6일

대학수업

목록 보기

6/32

Heap

힙은 왜 쓰는건가?

힙은 우선순위 큐의 한 종류이다. 때문에 리스트에 우선순위를 부여해서 만드는 것이다. 우리가 만약 큰 값이 중요하거나 작은 값이 중요한 데이터를 가지고 있다고 생각해보자. 만약 우선순위가 부여되어 있지 않으면 우리는 중요한 값을 찾기 위해 매번 검색을 하며 제일 큰 값을 찾아야 할 것이다. 이렇게 하면 시간이 너무 오래 걸린다. 때문에 이러한 우선순위 힙을 쓰는 것이다.

완전 이진 트리?

힙을 쓸 때는 완전 이진 트리를 사용한다. 이런 식으로 이진트리를 사용하는 이유를 개인적으로 생각해보자면 이진트리를 사용했을 때 검색할 때 편하기 때문이다.

완전 이진 트리에 대해 적어보자면, 루트로부터 시작해 모든 노드가 자식 노드를 2개씩 가지면서 내려간다. 노드의 수가 2의 k승 - 1 개가 되지 못하는 경우에는 왼쪽부터 차례로 채운다.

이것이 완전 이진 트리의 규칙이다.

완전 이진 트리여야 하는 이유는 뭘까? 완전 이진 트리를 써야 하는 내 개인적인 이유는 그래야 규칙이 꼬이지 않기 때문이다. 힙의 조건에 대해 설명하자면

A[k] 노드의 자식은 A[2k+1]과 A[2k+2]
A[k] 노드의 부모는 A[⌊k-1/2⌋]

이다.
완전 이진 트리가 아니면 이 규칙이 꼬이기 때문에 완전 이진 트리를 사용할 수 밖에 없는 것이다.

추가적으로

힙이 우선순위 큐를 구현하는 대표적인 수단이다.
힙이 우선순위 큐를 구현하는 유일한 방법은 아니다.
힙은 우선순위 큐를 지원하기 위한 함수를 포함한다.

구현

어떻게 구현할까? 우리가 생각해보아야 하는 기능을 우선 생각해보자.

__A[] : 힙을 저장하는 리스트
insert(x) : 힙에 원소 x를 삽입
deleteMax(x) : 힙의 최대 원소를 알려주고 삭제
max() : 힙의 최대 원소를 알려줌
buildHeap() : 리스트 A[]를 힙으로 구성
isEmpty() : 힙이 비었는지 알려줌
clear() : 힙을 깨끗이 청소

생성

class Heap:
  def __init__(self, *args):
    if len(args) != 0:
      self.__A = args[0]
    else:
      self.__A = []

우선 생성을 해주자. 클래스를 만들 때 가변 파라미터를 사용해서 안에 값을 넣어줄 수 있게 만들어주자. 그냥 결국엔 list에 넣어주는 것이다.

삽입

  def insert(self, x):
    self.__A.append(x)
    # 맨 끝에서 시작
    self.__percolateUp(len(self.__A) - 1)

삽입을 해주는 코드이다. 여기서 생각해보아야 하는 것은 저 self.__percolateUp이라는 코드이다.

  # 타고 올라가기
  def __percolateUp(self, i:int):
    # A[k] 노드의 자식은 A[2k+1]과 A[2k+2] 
    # A[k] 노드의 부모는 A[⌊k-1/2⌋]
    parent = (i-1) // 2
    if i>0 and self.__A[i] > self.__A[parent]:
      self.__A[i], self.__A[parent] = self.__A[parent], self.__A[i]
      # 부모 노드의 위도 바꿔준다. 
      self.__percolateUp(parent)

저게 어떤 함수인지 설명을 해보자면 저 함수를 사용하면 내가 넣어준 index 에서 부모 노드와 나와 비교하는 것이다. 만약 내가 부모 노드가 더 커야하는 상황이면 비교를 해서 부모 노드가 더 크게 만들어준다. 그리고 또 그 부모와 비교를 해서 끝까지 올라게 된다. 그렇게 되면 내가 삽입을 할 때도 동일한 구조를 유지하게 되는 것이다.

삭제

  # 맨 위  지워
  def deleteMax(self):
    if (not self.isEmpty()):
      # 맨 위
      max = self.__A[0]
      # self.__A.pop() is 맨 뒤
      # 맨 앞 <- 맨 뒤
      self.__A[0] = self.__A.pop()
      # 타고 내려가기
      self.__percolateDown(0)
      return max
    else:
      return None

다음은 맨위를 지우는 함수이다. 솔직히 왜 지우는지는 잘 모르겠지만 지우는 상황이 필요한가 보다. 여기서 self.__percolateDown() 함수는 바로 보자.

  # 타고 내려가기
  def __percolateDown(self, i:int):
    # A[k] 노드의 자식은 A[2k+1]과 A[2k+2] 
    left = 2 * i + 1
    right = 2 * i + 2
    if (left <= len(self.__A) - 1):
      # 왼쪽이 더 커야함.
      if(right <= len(self.__A)-1 and self.__A[left] < self.__A[right]):
        left = right 
      # 부모가 작으면 안됨
      if self.__A[i] < self.__A[left]:
        self.__A[i], self.__A[left] = self.__A[left], self.__A[i]
        self.__percolateDown((left))

얘는 아까 나왔던 함수와 반대이다. A[k] 노드의 자식은 A[2k+1]과 A[2k+2] 이 개념이 중요하다.

얘는 타고 내려가면서 비교를 해주는 친구다. 왼쪽이 더 커야하고 부모가 작으면 안된다. 재귀를 정말 잘 쓰는 것 같다.

힙 생성

  def buildHeap(self):
    for i in range(len(self.__A) - 2 // 2, -1, -1):
      self.__percolateDown(i)

모든 서브 트리(Sub-tree)가 힙의 성질을 만족하도록 노드 교환
두 개의 서브 트리(힙)를 병합하여 하나의 큰 힙으로 구성
최종적으로 하나의 힙을 완성 (재귀적 방식)
자식 노드 중 큰 값을 가진 것과 교환
자식 노드 중 큰 값을 가진 것과 교환 (하위 노드에 대해서도 반복)
모든 자식 노드 보다 크거나 같은 값을 가지면 종료

len(self.__A) - 2 // 2 == 마지막 노드의 부모 인덱스
(= 리프노드가 아닌 최초의 노드 인덱스)

원소의 갯수 : n = len(__A)
마지막 노드 : A[n-1]
마지막 노드의 부모: A[⌊(n-1)-1/2⌋]

출력

  def heapPrint(self):
    print("========================")
    start = 0
    end = 1
    # A[k] 노드의 자식은 A[2k+1]과 A[2k+2] 
    while (1):
      try:
        for k in range(start, end):
          print(self.__A[k], end= " ")
        print()
        
        start = 2 * start + 1
        end = 2 * start + 1
      except:
        print()
        return