10. 힙(Heap)
완전 이진 트리의 일종으로, 부모 노드와 자식 노드 간에 특정한 순서를 유지하는 자료구조.
힙은 일반적으로 배열로 구현되며, 해당 노드의 자식 노드들의 값보다 크거나 작은 순서를 가짐.
이를 힙 속성(Heap Property)이라고 함.
힙은 보통 최대 힙(Max Heap) 또는 최소 힙(Min Heap)으로 사용됨.
최대 힙은 부모 노드의 값이 자식 노드의 값보다 큰 순서를 가지며,
최소 힙은 부모 노드의 값이 자식 노드의 값보다 작은 순서를 가짐.
힙은 주로 다음과 같은 연산을 지원함:
삽입(Insert): 힙에 새로운 요소를 추가.
삭제(Delete): 힙에서 최대 또는 최소 값을 제거.
최대 값 또는 최소 값 확인: 힙의 최대 또는 최소 값을 반환하거나 확인.
힙은 주로 우선순위 큐(Priority Queue) 구현이나 힙 정렬(Heap Sort) 알고리즘에 사용됨.
우선순위 큐는 가장 높은 우선순위를 가진 요소에 접근하기 위해 힙을 활용하며,
힙 정렬은 힙을 사용하여 정렬을 수행하는 알고리즘.
힙은 데이터의 삽입과 삭제에 대해 O(log n)의 시간 복잡도를 가지며,
최대 또는 최소 값에 대한 접근은 O(1)의 시간 복잡도를 가지는 효율적인 자료구조임.
O(log n) 시간 복잡도: 효율적인 시간복잡도로, 데이터의 크기가 n일 때, 힙의 높이인 log n에 비례하는 시간이 소요됨을 의미. O(1) 시간 복잡도: 가장 효율적인 시간 복잡도로 간주됨. 해당 작업의 실행 시간이 입력의 크기에 영향을 받지 않으며, 항상 일정한 시간만큼 소요된다는 것을 의미. |
10-1. 조건
1. 완전 이진 트리
2. 모든 노드는 값을 가지며, 부모노드의 값이 자식노드의 값보다 크거나 같다(최대힙)
10-2. 구성
1) 필수요소
list() : 힙을 저장할 리스트
2) 메서드
.build_heap(): 주어진 리스트를 힙으로 만듦. 주어진 리스트의 원소들을 순서에 맞게 힙으로 조정하여
힙의 각 노드가 부모 노드보다 크거나 작은 값을 가지도록 함.
일반적으로 Bottom-up 방식으로 구현되며, 리스트의 마지막 원소부터 시작하여 각 노드를 부모 노드와
비교하고 조건에 맞게 위치를 조정함.
.insert(x): 힙에 새로운 원소 x를 삽입. 힙의 가장 마지막 위치에 새로운 원소를 추가하고 힙을 재조정함.
.delete(): 힙에서 최대 원소를 제거하고 해당 최대 원소를 반환.
일반적으로는 힙의 루트 노드에 위치한 최대 원소를 삭제하고, 삭제 후 힙을 재조정함.
.max(): 힙의 루트 노드에 위치한 최대 원소를 반환함.
최대 원소는 힙의 구조와 조건에 의해 항상 루트 노드에 위치하게 됨.
.is_empty(): 힙이 비어있는지 확인함. 힙이 비어있으면 True를 반환하고, 비어있지 않으면 False를 반환함.
.clear(): 힙을 비움. 즉, 힙에 있는 모든 원소를 제거하여 빈 상태로 만듦.
10-3. 작업 알고리즘
10-3-1. 힙 생성
1) 상향식(heapify-up): 새로운 원소가 힙의 맨 끝에 삽입될 때 사용되는 방법.
2) 삽입식(heapify-insert): 초기에 무작위로 구성된 리스트나 배열을 힙으로 만들 때 사용되는 방법.
class Heap:
def __init__(self, alist):
if alist == None:
self.heap_list = list()
else:
self.heap_list = alist
10-3-2. 힙 원소 삽입 : 비재귀
heap_list[0....n-1] insert(x): # x가 삽입할 원소 i <- n # 힙 크기(n)의 마지막 인덱스 heap_list[i] <- x # 일단 맨 마지막에 삽입 : list -> append parent <- (i - 1) // 2 # 부모 인덱스 찾기 while i > 0 and heap_list[i] > heap_list[parent]: # 조건 2 X -> 교체 조건 heap_list[i] <-> heap_list[parent] i <- parent parent <- (i-1) // 2 k++ # 힙 크기 1 증가 |
heap_list = [ ]
def insert(self, x):
self.heap_list.append(x)
i = len(heap_list) - 1
parent = (i-1) // 2
while i > 0 and heap_list[i] > heap_list[parent]:
self.heap_list[i], self.heap_list[parent] = self.heap_list[parent], self.heap_list[i]
i = parent
parent = (i - 1) // 2
10-3-3. 힙 원소 삽입 : 재귀
insert(x): heap_list[n] <- x # 자식 노드와 부모노드를 반복해 바꿀 재귀함수 percolate_up(n) k++ percolate_up(i): parent <- (i-1) // 2 if i > 0 and heap_list[i] > heap_list[parent]: heap_list[i] <-> heap_list[parent] # i가 parent, parent는 다시 매개변수로 들어가서 윗 레벨 감소 percolate(parent) |
def insert(self, x):
self.heap_list.append(x)
self.percolate_up(len(self.heap_list) - 1) # 증가한 갯수 - 1 = 마지막 인덱스
def percolate_up(self, i:int): # percolate_up(): 주어진 인덱스 i의 원소를 힙 상위로 이동시키는 역할
parent = (i-1) // 2 # 현재 원소의 부모 인덱스를 계산
if i > 0 and self.heap_list[i] > self.heap_list[parent]:
self.heap_list[i], self.heap_list[parent] = self.heap_list[parent], self.heap_list[i]
self.percolate_up(parent)
# self.percolate_up(parent)를 재귀적으로 호출하여 부모 위치로 이동된 원소에 대해 동일한 과정을 반복.
이는 삽입된 원소가 계속해서 상위로 이동하여 힙의 조건을 만족하도록 함.
10-3-4. 힙 원소 삭제 : 재귀
# 힙 heap_list[0...n-1] delete_max(): # 기존의 가장 큰 원소(0번 인덱스)를 삭제하기 위한 예비작업, 변수에 저장 heap_max <- heap_list[0] # 가장 뒤의 원소를 힙 루트 노드로 heap_list[0] <- heap_list[n-1] # 힙 크기 1 감소 : 조건1 만족, n-- # 루트노드부터 교체작업을 차례로 진행 -> 조건 2 만족 percolate_down(0) return heap_max # 스며내리기 : 부모노도와 자식노드를 교체하여 조건2 충족시키는 작업 percolate_down(k): # 왼쪽 자식 노드 : 완전 이진트리 <= 왼쪽부터 차례로 채운다. child <- 2k + 1 # 오른쪽 자식 right <- 2k + 2 if child <= n - 1: if right <= n - 1 and heap_list[child] < heap_list[right]: # 둘 중 큰 원소의 인덱스가 우선순위 child <- right # 조건 2를 불충족시킬 경우 작업 진행 if heap_list[k] < heap_list[child]: # 부모노드와 자식노드를 맞바꾼다 heap_list[k] <-> heap_list[child] percolate_down(child) |
def delete_max(self): # 힙 자료구조에서 가장 큰 원소를 삭제하는 메서드
# 예외 처리 : 비어있지 않다면 실행
if not self.is_empty():
heap_max = self.heap_list[0]
self.heap_list[0] = self.heap_list.pop()
self.percolate_down(0)
return max
else:
return None
def percolate_down(self, i:int): # 스며내리기 연산. 부모 노드와 자식 노드를 교체하여 조건 2를 충족시키는 작업을 수행하는 함수. (조건2: 부모 노드의 값이 자식 노드의 값보다 항상 크거나 작은 순서를 유지해야 함)
child = 2*i + 1
right_child = 2*i + 2
if child <= (len(self.heap_list) - 1):
# child == right_child 일 경우, 뒷 조건 -> False가 되면서 기존 child가 기준이 된다.
if right_child <= (len(self.heap_list) - 1) and heap_list[child] < heap_list[right_child]:
child = right_child # child를 right_child로 변경
if self.heap_list[i] < self.heap_list[child]:
self.heap_list[i], self.heap_list[child] = self.heap_list[child], self.heap_list[i] # 부모노드와 자식노드 교체
self.percolate_down(child)
10-3-5. 힙 생성
heap_list[0...n-1] build_heap: for i <- ((n-1) - 1 // 2) to 0: percolate_down(i) |
def build_heap(self): # 주어진 배열 heap_list를 힙으로 만들기 위해 사용.
last_index = len(self.heap_list) - 1
last_parent = (last_index - 1) // 2
# range(초기값, 종료값직전, 증감값)
for index in range(last_parent, -1, -1):
self.percolate_down(index)
10-3-6. 기타 작업
.max() : 최대값 확인(검색)
.is_empty() : 비었는지를 확인
.clear() : 비우기
10-4. 힙 구현
class Heap:
def __init__(self, *args): # *args: 인자의 개수가 가변적일 수 있음.
if len(args) != 0:
self.heap = args[0] # 전달된 인자(args)의 개수가 0이 아니면, args의 첫 번째 요소를 self.heap에 할당.
else:
self.heap = list() # 전달된 인자의 개수가 0이면, 빈 리스트를 self.heap에 할당.
def insert(self, x):
self.heap.append(x)
self.percolate_up(len(self.heap) - 1)
def percolate_up(self, i:int):
parent = (i-1) // 2
if i > 0 and self.heap[i] > self.heap[parent]:
self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
self.percolate_up(parent)
def delete_max(self):
if not self.is_empty():
max = self.heap[0]
self.heap[0] = self.heap.pop()
self.percolate_down(0)
return max
else:
return None
def percolate_down(self, i:int):
child = 2 * i + 1
right_child = 2 * i + 2
if child <= len(self.heap) - 1:
# 바꿀 대상이 될 child 선정 작업
if right_child <= len(self.heap) - 1 and self.heap[child] < self.heap[right_child]:
child = right_child
# 교환 작업
if self.heap[i] < self.heap[child]:
self.heap[i], self.heap[child] = self.heap[child], self.heap[i]
self.percolate_down(child)
def max(self):
return self.heap[0]
def build_heap(self):
for index in range((len(self.heap) - 2) // 2, -1, -1):
self.percolate_down(index)
def is_empty(self) -> bool:
return len(self.heap) == 0
def clear(self):
self.heap = [ ]
def size(self) -> int:
return len(self.heap)
def print_heap(self):
for i in self.heap:
print(i, end = ' ')
print()
10-4-1. 테스트
hp = Heap([1,9,11,2,4,7])
hp.build_heap()
hp.print_heap()
hp.clear()
hp.print_heap()
hp.insert(6)
hp.insert(13)
hp.insert(21)
hp.insert(3)
hp.insert(11)
hp.insert(4)
hp.insert(19)
hp.insert(8)
hp.insert(17)
hp.print_heap()
print(hp.delete_max()) # 가장 큰 원소인 21이 삭제됨
hp.print_heap()
# 1부터 30까지의 임의의 숫자를 13개 선정하여 Heap에 삽입하려는 경우
import random
hpp = Heap()
for i in range(13):
hpp.insert(random.randint(1,30))
hpp.print_heap()
