[파이썬 | 자료구조] 8. 힙(Heap)

8. 힙(Heap)

8.1 힙의 개념

힙 역시 트리 구조를 가진 자료구조의 형태이다.

힙은 BST와 비슷하면서 다른 특징을 가지고 있다.

1. root의 값은 항상 최대/최소 이다.
2. 트리는 항상 완전이진트리이다.
3. 어떤 서브 트리 역시 힙의 특성을 그대로 가진다.

BST는 모든 원소들이 Inorder로 탐색했을시 정렬되어서 표현된다. 즉 모든 자료들이 정렬되어 있는 형태로, 탐색에 유리하다.

하지만 힙은 root의 값이 최대/최소임은 보장하지만 다른 원소들은 정렬되어 있지 않다. 따라서 BST에 비해 탐색에는 불리한 구조이다.

하지만 모든 삽입과 삭제가 맨 마지막에서 일어나므로 삽입, 삭제 연산에 있어서 장점이 있으며 부모와 자식간의 간선 정보를 수식으로 나타낼 수 있으므로, node를 사용한 연결리스트가 아닌 배열의 형태로 구현할 수 있어서 구현에 있어 장점이 있다.

일단 삽입의 경우에는 그냥 배열의 맨 마지막에 추가하면 되므로 append로 간단히 구현가능하다.

삭제의 경우에는 일단 삭제할 데이터의 index를 모두 탐색하고나서, 해당 index의 데이터와 맨 마지막의 데이터를 교환하고, 맨 마지막 데이터를 pop한다.

하지만 이렇게 하면 Heap 규칙이 깨지므로, heapify를 수행해서 max heap을 다시 구현한다.

	class myHeap:
	def __init__(self):
	self.arr = [None]
	def insert(self, item):
	self.arr.append(item)
	idx = len(self.arr)-1
	while idx > 1:
	if self.arr[idx] > self.arr[idx//2]:
	self.arr[idx], self.arr[idx//2] = self.arr[idx//2], self.arr[idx]
	idx //= 2
	else:
	break
	def search(self, target):
	return self.arr.index(target)
	def delete(self, target):
	targetIdx = self.search(target)
	# 삭제하려는 타겟이 가장 마지막인 경우 오류방지
	if targetIdx != len(self.arr) - 1:
	self.arr[targetIdx] = self.arr.pop()
	else:
	self.arr.pop()
	for i in range(targetIdx, 0, -1):
	# 삭제한 targetIdx 부터 root까지 모두 heapify를 한다.
	self.maxHeapify(i)
	def maxHeapify(self, idx):
	# idx 번째 아래 자식은 모두 heapify를 재귀적으로 수행한다.
	left = 2 * idx
	right = 2 * idx + 1
	smallest = idx
	if left < len(self.arr) and self.arr[idx] < self.arr[left]:
	smallest = left
	if right < len(self.arr) and self.arr[idx] < self.arr[right]:
	smallest = right
	if smallest != idx:
	self.arr[idx], self.arr[smallest] = self.arr[smallest], self.arr[idx]
	self.maxHeapify(smallest)
	def popRoot(self):
	ret = self.arr[1]
	self.arr[1] = self.arr.pop()
	self.maxHeapify(1)
	return ret
	def showAll(self):
	print(self.arr)
	h = myHeap()
	h.insert(20); h.insert(4); h.insert(8);
	h.insert(17); h.insert(15); h.insert(40);
	h.showAll()
	print(h.popRoot())
	h.delete(20)
	h.showAll()
	h.delete(4)
	h.showAll()
	print(h.popRoot())

view raw heap.py hosted with ❤ by GitHub