패캠 네카라쿠배 도전: HTML CSS

[패캠 네카라쿠배 2기] 2차 테스트 - 10일차 데이터구조8: 힙

닉네임이 멋이 중헌디 2021. 6. 25. 15:58

대표적인 데이터 구조8: 힙

1. 힙 (Heap) 이란?

  • 힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
    • 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

  • 힙을 사용하는 이유
    • 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸림
    • 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, O(logn) 이 걸림
    • 우선순위 큐(우선순위를 같이 지정해줘서 우선순위가 높은 애부터 추출)와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨

2. 힙 (Heap) 구조

  • 힙은 최대값을 구하기 위한 구조 (최대 힙, Max Heap) 와,
  • 최소값을 구하기 위한 구조 (최소 힙, Min Heap) 로 분류할 수 있음
  • 힙은 다음과 같이 두 가지 조건을 가지고 있는 자료구조임
    1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우): 그러므로 루트 노드가 가장 크다 [부모노드 >= 자식노드]
      • 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작음
    2. 완전 이진 트리 형태를 가짐 : 왼쪽부터 채워가게 되어 있는 구조 

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

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

3. 힙 (Heap) 동작

  • 데이터를 힙 구조에 삽입, 삭제하는 과정을 그림을 통해 선명하게 이해하기

힙에 데이터 삽입하기 - 기본 동작

  • 힙은 완전 이진 트리이므로, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드(왼쪽이 있으면 오른쪽)부터
  • 채워지는 형태로 삽입/ 자식은 둘뿐 

힙에 데이터 삽입하기 - 삽입할 데이터가 힙의 데이터보다 클 경우 (Max Heap 의 예)

  • 먼저 삽입된 데이터는 완전 이진 트리 구조에 맞추어, 최하단부 왼쪽 노드부터 채워짐
  • 채워진 노드 위치에서, 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업을 반복함 (swap)ex. 20을 넣을 때: 루트 노드인 15보다 크다
  • (1) Insert 20 : 완전 이진 트리에 따라 배치
  •  1) 왼쪽 있는지, 그 아래 왼쪽이 있는, 오른쪽 있는지 
  • 2) 오른쪽 있는지, 그 아래 왼쪽이 있는지, 오른쪽 있는지 [완전 이진 트리에 따라 먼저 배치]
  •  
  • (2) Swap 20 for 8
  • 1)자식노드 20와 부모노드 8과 비교 : 20이 더 크니까 교체 
  •  
  • (3) 자식노드 20와 부모노드 15와 비교 : 20이 더 크니까 교체 
  • // insert한 값이 루트노드가 되거나 비교한 위의노드보다 작을 때까지 교체 

힙의 데이터 삭제하기 (Max Heap 의 예 : Max는 루트 노드이므로 특정한 )

  • 보통 삭제는 최상단 노드 (root 노드)를 삭제하는 것이 일반적임 (1)
    • 힙의 용도는 최대값 또는 최소값을 root 노드에 놓아서, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것임
    • 루트 노드가 가장 유의미한 값, 그러므로 삭제 시 루트 노드를 삭제하는 것이 일반적
  • 상단의 데이터 삭제시, 가장 최하단부 왼쪽에 위치한 노드 (일반적으로 가장 마지막에 추가한 노드) 를 root 노드로 이동 (2)
  • root 노드의 값이 child node 보다 작을 경우, root 노드의 child node 중 가장 큰 값을 가진 노드(15)와 root 노드(8) 위치를 바꿔주는 작업을 반복함 (swap) // 여기서는 누가 더 큰지 모르니까 (완전 이진 트리면 오른쪽이 더 크다)

4. 힙 구현

힙과 배열

  • 일반적으로 힙 구현시 배열 자료구조를 활용함 [완전 이진 트리 형태이므로 배열로 표현 가능]
  • 배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해, root 노드 인덱스 번호를 1로 지정하면, 구현이 좀더 수월함
    • 부모 노드 인덱스 번호 (parent node's index) = 자식 노드 인덱스 번호 (child node's index) // 2
    • 왼쪽 자식 노드 인덱스 번호 (left child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2
    • 오른쪽 자식 노드 인덱스 번호 (right child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2 + 1
    • 그러므로 자식노드를 2로 나눈 몫은 부모 노드
    • 배열 [15,10,8,5,4] 
    •  

힙에 데이터 삽입 구현 (Max Heap 예)

  • 힙 클래스 구현1

In [8]:

class Heap:

def __init__(self, data):

self.heap_array = list()

self.heap_array.append(None)

self.heap_array.append(data)

 

In [9]:

heap = Heap(1) // Heap 클래스로 heap.array라는 리스트를 만들고 None과 data=1을 append

heap.heap_array 

Out[9]:

[None, 1]

  • 힙 클래스 구현2 - insert1
    • 인덱스 번호는 1번부터 시작하도록 변경
    • insert : 1)이진트리처럼 왼쪽부터 쌓아가는 2)쌓은 노드를 부모 노드랑 비교하는 것

In [11]:

class Heap:

def __init__(self, data):

self.heap_array = list()

self.heap_array.append(None)

self.heap_array.append(data)

 

def insert(self, data):

if len(self.heap_array) == 0: // 이런 경우는 없겠지만 초기화, root node가 없는 단계

(없으면 data를 넣고 return하면 끝난다) 

   self.heap_array.append(None) 

   self.heap_array.append(data)

   return True

 

self.heap_array.append(data) // 배열 끝에 data를 추가 (힙의 구조와 인덱스의 순서가 잘 맞음)

 

inserted_idx = len(self.heap_array)-1 

// 배열의 길이 -1 (왜냐하면 None이 있으니까)

// 방금 들어간 data의 인덱스 번호를 구해서 부모 노드의 인덱스 번호를 구해서 비교하면 된다

return True

 

  • 힙 클래스 구현3 - insert2 
  • insert : 1)이진트리처럼 왼쪽부터 쌓아가는 2)쌓은 노드를 부모 노드랑 비교하는 것
    • 삽입한 노드가 부모 노드의 값보다 클 경우, 부모 노드와 삽입한 노드 위치를 바꿈
    • 삽입한 노드가 루트 노드가 되거나, 부모 노드보다 값이 작거나 같을 경우까지 반복
  • 특정 노드의 관련 노드 위치 알아내기
    • 부모 노드 인덱스 번호 (parent node's index) = 자식 노드 인덱스 번호 (child node's index) // 2
    • 왼쪽 자식 노드 인덱스 번호 (left child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2
    • 오른쪽 자식 노드 인덱스 번호 (right child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2 + 1

In [16]:

 

 

 

heap = Heap(15)heap.insert(10)heap.insert(8)heap.insert(5)heap.insert(4)heap.insert(20)heap.heap_array

Out[16]:

[None, 20, 10, 15, 5, 4, 8]

In [15]:

 

 

 

class Heap: 

def __init__(self, data):

self.heap_array = list()

self.heap_array.append(None)

self.heap_array.append(data)

 

def move_up(self, inserted_idx): // 루트 노드라서 바꿀 필요가 없는지, 비교해서 바꿔야 하는지 

if inserted_idx <= 1: # 루트 노드라는 말(그러므로 바꾸지 않아도 되므로 아래 self.move_up while문이 발동걸리지 않게 false로 만든다) 

return False

parent_idx = inserted_idx // 2

if self.heap_array[inserted_idx] > self.heap_array[parent_idx]: #부모노드와 비교. 더 크면 아래 while문 발동되도록 return true

return True

else:

return False

 

def insert(self, data):  #완전 이진 트리에 삽입

if len(self.heap_array) == 0:

self.heap_array.append(None)

self.heap_array.append(data)

return True

self.heap_array.append(data)

inserted_idx = len(self.heap_array) - 1

 

while self.move_up(inserted_idx): // 부모노드와 바꿔줘야하면 true가 나와서 while문을 계속 하도록 

parent_idx = inserted_idx // 2 #parent는 2로 나눈 몫 

self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]

#1,2 = 2,1로 swap! (위 그림에서 20, 8을 swap) 

inserted_idx = parent_idx  #주인공이 되는 node의 index 번호를 부모 노드의 index로 바꾼다 

                                  #다음 부모노드와 또 비교

return True ​

 

힙에 데이터 삭제 구현 (Max Heap 예)

  • 힙 클래스 구현4 - delete1
  • 보통 삭제는 최상단 노드 (root 노드)를 삭제하는 것이 일반적임
    • 힙의 용도는 최대값 또는 최소값을 root 노드에 놓아서, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것임

In [18]:

class Heap:

def __init__(self, data):

self.heap_array = list()

self.heap_array.append(None)

self.heap_array.append(data)

 

def pop(self): // 데이터를 삭제하는 것보다도 데이터를 꺼내는 느낌이라 pop 사용 

if len(self.heap_array) <= 1: // None 또는 data가 없는 경우 

return None

returned_data = self.heap_array[1] // [0]은 None이니까 [1]은 root node

return returned_data  // 삭제하는 코드를 별도로 넣을 필요는 없다. 왜냐하면 마지막에 넣은 node를 올리면 된다 

 

  • 힙 클래스 구현4 - delete2
    • 상단의 데이터 삭제시, 가장 최하단부 왼쪽에 위치한 노드 (일반적으로 가장 마지막에 추가한 노드) 를 root 노드로 이동
    • root 노드의 값이 child node 보다 작을 경우, root 노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복함 (swap) (8과 15)
  • 특정 노드의 관련 노드 위치 알아내기
    • 부모 노드 인덱스 번호 (parent node's index) = 자식 노드 인덱스 번호 (child node's index) // 2
    • 왼쪽 자식 노드 인덱스 번호 (left child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2
    • 오른쪽 자식 노드 인덱스 번호 (right child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2 + 1

In [23]:

heap = Heap(15)

heap.insert(10)

heap.insert(8)

heap.insert(5)

heap.insert(4)

heap.insert(20)

heap.heap_array

 

Out[23]:

[None, 20, 10, 15, 5, 4, 8]

 

In [24]:

heap.pop()

Out[24]:

20

In [25]:

heap.heap_array

Out[25]:

[None, 15, 10, 8, 5, 4]

In [22]:

class Heap:

def __init__(self, data):

self.heap_array = list()

self.heap_array.append(None)

self.heap_array.append(data)

 

def move_down(self, popped_idx): 

left_child_popped_idx = popped_idx * 2 // 왼쪽 노드 인덱스 

right_child_popped_idx = popped_idx * 2 + 1 // 오른쪽 노드 인덱스 

but 내릴 때도 이미 data가 없으면 더 이상 비교할 것이 없으므로 끝난다 

# case1: 왼쪽 자식 노드도 없을 때

if left_child_popped_idx >= len(self.heap_array): // 있는 것의 개수보다 더 많다 (없다)

return False

# case2: 오른쪽 자식 노드만 없을 때(왼쪽은 있을 때)

elif right_child_popped_idx >= len(self.heap_array): 

if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]: // root node보다 왼쪽이 더 크면 바꿔줘야 하니까

return True

else: 

return False

# case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때 (둘다 X, 왼만, 둘다)

왼, 오를 비교해서 큰 노드를 찾고 그 다음에 자신과 비교를 해야 한다 

else:

if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]: // 왼오를 먼저 비교해야 한다 (왼이 더 클때) 

if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:  (부모와 왼 비교, 부모가 더 작으면)

return True // 바꿔줘야하니까 true(아래 while문 실행하게)

else:

return False /

else: // 부모가 더 큰데 

if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]: //부모가 오른쪽보다 작을 때 

return True // 바꿔줘야한다 

else:

return False

 

def pop(self):

if len(self.heap_array) <= 1:

return None

returned_data = self.heap_array[1]

self.heap_array[1] = self.heap_array[-1] // root를 마지막에 추가된 값으로 (-1은 뒤에서 첫번째) 

del self.heap_array[-1] // 맨 끝에 있는 데이터의 공간을 지워준다 (root node의 자리로 간거나 다름 없음)

popped_idx = 1 // root자리에 갔으니까

 

while self.move_down(popped_idx):

// 밑과 swap을 해야하는지를 판단하는 부분. self.move_down이 true인 동안만 실행 

// 어느 칭구끼리 바꿔야하는지 보여주기 위해 다시 case를 나눠서 바꾼다 

left_child_popped_idx = popped_idx * 2

right_child_popped_idx = popped_idx * 2 + 1​

# case2: 오른쪽 자식 노드만 없을 때

if right_child_popped_idx >= len(self.heap_array): // right없다는 뜻

if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]: // 왼쪽이 해당 노드보다 크면

self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]

# 해당 노드, 왼쪽 = 왼쪽, 해당 노드 [바꾼다]

popped_idx = left_child_popped_idx // 해당 노드를 왼쪽의 자리로 내린다 

# case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때

else:

if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]:// 왼쪽이 오른쪽보다 크면 

if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]: // 해당 노드보다 왼쪽이 크면 

self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]

#마찬가지로 해당노드, 왼 = 왼, 해당노드 [교체]

popped_idx = left_child_popped_idx 

else:

if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]: // 오른쪽이 해당 노드보다 더 크면 

self.heap_array[popped_idx], self.heap_array[right_child_popped_idx] = self.heap_array[right_child_popped_idx], self.heap_array[popped_idx]

#해당노드, 오 = 오, 해당노드[교체]

popped_idx = right_child_popped_idx

return returned_data

 

def move_up(self, inserted_idx):

if inserted_idx <= 1:

return False parent_idx = inserted_idx // 2

if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:

return True

else:

return False​

 

def insert(self, data):

if len(self.heap_array) == 1:

self.heap_array.append(data)

return True

self.heap_array.append(data)

inserted_idx = len(self.heap_array) - 1

while self.move_up(inserted_idx):

parent_idx = inserted_idx // 2

self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx] inserted_idx = parent_idx

return True

 

insert()를 사용하면 이진 트리의 구조에 맞게 넣는다 

pop()은 최대값을 빼온다 (root node)

5. 힙 (Heap) 시간 복잡도

  • depth (트리의 높이) 를 h라고 표기한다면,
  • n개의 노드를 가지는 heap 에 데이터 삽입 또는 삭제시, 최악의 경우 root 노드에서 leaf 노드까지 비교해야 하므로 h=log2n 에 가까우므로, 시간 복잡도는 O(logn)
    • 참고: 빅오 표기법에서 logn 에서의 log의 밑은 10이 아니라, 2입니다.
    • 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축시킬 수 있다는 것을 의미함
    • 배열의 경우 100개 중 탐색하면 최악의 경우 100개/ 힙은 50프로씩 줄여나가기 때문에 시간 단축 가능