Heap
- 완전 이진 트리 형태의 우선순위 큐를 위하여 만들어진 자료구조
- 최소값(최소 힙) 또는 최대값(최대 힙)을 빠르게 찾아내는데 유용한 자료구조
- 중복 값을 허용(이진 탐색 트리에서는 중복값을 허용하지 않음)
- 반 정렬 상태(큰 값이 상위 레벨에 있고, 작은 값이 하위 레벨에 있다는 정도)
최소힙
key(부모 노드) ≥ key(자식 노드) 의 형태를 가지는 힙
최대힙
key(부모 노드) ≤ key(자식 노드) 의 형태를 가지는 힙
Heap의 구현
- 힙을 저장하는 표준적인 자료구조는 배열이다
- 구현을 쉽게 하기 위하여 인덱스 0은 사용되지 않는다
- 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다
- 힙에서의 부모 노드와 자식 노드의 관계
- 부모 인덱스 = (자식 인덱스) // 2
- 왼쪽 자식 인덱스 = (부모 인덱스) * 2
- 오른쪽 자식 인덱스 = (부모 인덱스) * 2 + 1
Heap의 삽입 (시간 복잡도 : O(logn))
- 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다
- 해당 힙의 규칙(부모 노드 이하이거나 이상이거나)을 만족할 때까지 새로운 노드를 부모 노드와 교환한다
Heap의 삭제 (시간 복잡도 : O(logn))
- 최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제 된다
- 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다
- 힙을 재구성한다
구현
참고 블로그
Heap 삽입
# 힙 노드 삽입
def insert(self, n):
self.queue.append(n)
last_index = len(self.queue) - 1
while 0 <= last_index:
parent_index = self.parent(last_index)
if 0 <= parent_index and self.queue[parent_index] < self.queue[last_index]:
self.swap(last_index, parent_index)
last_index = parent_index
else:
break
def swap(self, i, parent_index):
self.queue[i], self.queue[parent_index] = self.queue[parent_index], self.queue[i]
def parent(self, index):
return (index - 1) // 2
Heap 삭제
# 힙 노드 삭제
def delete(self):
last_index = len(self.queue) - 1
if last_index < 0 :
return -1
self.swap(0, last_index) # 루트노드와 끝노드 교환
max_value = self.queue.pop() # 끝노드(이전의 루트 노드 삭제)
self.maxHeapify(0) # root에서부터 재정렬
print(max_value)
return max_value
def maxHeapify(self, i):
left_index = self.leftChild(i)
right_index = self.rightChild(i)
max_index = i
# max_index 보다 자식노드가 있는지 확인
if left_index <= len(self.queue) - 1 and self.queue[max_index] < self.queue[left_index]:
max_index = left_index
if right_index <= len(self.queue) -1 and self.queue[max_index] < self.queue[right_index]:
max_index = right_index
if max_index != i :
self.swap(i, max_index)
self.maxHeapify(max_index)
def leftChild(self, index):
return index * 2 + 1
def rightChild(self, index):
return index * 2 + 2
전체
class MaxHeap(object):
def __init__(self):
self.queue = []
# 힙 노드 삽입
def insert(self, n):
self.queue.append(n)
last_index = len(self.queue) - 1
while 0 <= last_index:
parent_index = self.parent(last_index)
if 0 <= parent_index and self.queue[parent_index] < self.queue[last_index]:
self.swap(last_index, parent_index)
last_index = parent_index
else:
break
def swap(self, i, parent_index):
self.queue[i], self.queue[parent_index] = self.queue[parent_index], self.queue[i]
def parent(self, index):
return (index - 1) // 2
# 힙 노드 삭제
def delete(self):
last_index = len(self.queue) - 1
if last_index < 0 :
return -1
self.swap(0, last_index) # 루트노드와 끝노드 교환
max_value = self.queue.pop() # 끝노드(이전의 루트 노드 삭제)
self.maxHeapify(0) # root에서부터 재정렬
print(max_value)
return max_value
def maxHeapify(self, i):
left_index = self.leftChild(i)
right_index = self.rightChild(i)
max_index = i
# max_index 보다 자식노드가 있는지 확인
if left_index <= len(self.queue) - 1 and self.queue[max_index] < self.queue[left_index]:
max_index = left_index
if right_index <= len(self.queue) -1 and self.queue[max_index] < self.queue[right_index]:
max_index = right_index
if max_index != i :
self.swap(i, max_index)
self.maxHeapify(max_index)
def leftChild(self, index):
return index * 2 + 1
def rightChild(self, index):
return index * 2 + 2