[자료구조] 힙(Heap) (Python)

[자료구조] 힙(Heap) (Python)

반응형

1. 정의

-최댓값과 최솟값을 빠르게 찾기 위해 만들어진 완전 이진트리(complete Binary Tree)

#완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

-종류에는 최대 힙과 최소 힙이 있음

2. 사용하는 이유

-최대값과 최솟값을 빠르게 찾기 위해서

-최댓값 최솟값을 찾을 때

배열을 사용하면 -> 시간 복잡도 O(n)

힙을 사용하면 -> 시간복잡도 O(logn)

3. 구조

-완전 이진 트리 형태

-각 노드의 값이 해당 노드의 자식 노드의 값보다 크거나 같다(최대 힙) -> 최댓값이 rootnode에 담김

-각 노드의 값이 해당 노드의 자식노드의 값보다 작거나 같다(최소 힙) -> 최솟값이 rootnode에 담김

4. Python으로 Maxheap구현

#maxheap코드 짜보기 class Heap: def __init__(self,data): self.heap_array = list() #안 헷갈리려고 index 1부터 시작 self.heap_array.append(None) self.heap_array.append(data) #insert함수에서 바꿔줘야하는 작업 해야하는지 판별하는 함수 def move_up(self,inserted_idx): #root node일 때 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 #delete함수에서 바꿔줘야하는 작업 해야하는지 판별하는 함수 def move_down(self, pop_idx): left_child_pop_idx = pop_idx * 2 right_child_pop_idx = pop_idx * 2 + 1 #1. 왼쪽 자식 노드도 없을 때 if left_child_pop_idx>=len(self.heap_array): return False #2. 왼쪽 자식 노드는 있고 오른쪽 자식 노드는 없을 떄 elif right_child_pop_idx>=len(self.heap_array): if self.heap_array[pop_idx]self.heap_array[right_child_pop_idx]: #자식 노드 중 왼쪽이 더 클 때 if self.heap_array[popped_idx] 맨앞이랑 맨 뒤랑 바꿔줌 pop_data = self.heap_array[1] #추출된 max node가 pop_data #완전한 heap구조가 될 때까지 맨 앞과 맨 뒤를 swap self.heap_array[1] = self.heap_array[-1] del self.heap_array[-1] pop_idx = 1 while self.move_down(pop_idx): left_child_pop_idx = popped_idx * 2 right_child_pop_idx = popped_idx * 2 + 1 #왼쪽 자식노드는 있고, 오른쪽 자식노드 없을 때 if right_child_pop_idx >= len(self.heap_array): if self.heap_array[pop_idx] < self.heap_array[left_child_pop_idx]: self.heap_array[pop_idx], self.heap_array[left_child_pop_idx] = self.heap_array[left_child_pop_idx], self.heap_array[pop_idx] pop_idx = left_child_pop_idx #왼쪽, 오른쪽 모두 자식노드 있을 때 else: if self.heap_array[left_child_pop_idx] > self.heap_array[right_child_pop_idx]: if self.heap_array[pop_idx] < self.heap_array[left_child_pop_idx]: self.heap_array[pop_idx], self.heap_array[left_child_pop_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx] pop_idx = left_child_pop_idx else: if self.heap_array[pop_idx] < self.heap_array[right_child_pop_idx]: self.heap_array[pop_idx], self.heap_array[right_child_pop_idx] = self.heap_array[right_child_popped_idx], self.heap_array[popped_idx] pop_idx = right_child_pop_idx return pop_data

[Insert 함수]

새로운 값을 추가하는 함수

일단 완전 이진 트리처럼 새로운 값을 최하단 왼쪽에 삽입

move_up함수를 통해 parent_node와 swap 해야 되는지 여부를 판별한 후, 구조가 안정화될 때까지 수정해줌

[pop 함수]

맨 위에 있는 max값을 추출한 후, 다시 구조를 짜는 함수

root node가 사라지면 마지막 노드가 그 자리를 일단 채운다.

이후부터는 move_down함수를 통해 child_node와 swap해야되는지 여부를 판별한 후, 구조가 안정화될 때까지 수정해줌

반응형

from http://tipsyziasu.tistory.com/95 by ccl(A) rewrite - 2021-07-29 15:26:24