코드 11-3
def push(self, item):
if self.is_full():
raise IndexError("the heap is full!!")
# 완전 이진 트리를 유지하기 위해
# 마지막 원소의 다음 인덱스
self.heapsize += 1
cur_idx = self.heapsize
# cur_idx가 루트가 아니고
# item의 key가 cur_idx 부모의 키보다 크면
while cur_idx != 1 and item.key > self.arr[self.parent(cur_idx)].key:
self.arr[cur_idx] = self.arr[self.parent(cur_idx)]
cur_idx = self.parent(cur_idx)
self.arr[cur_idx] = item
코드 11-3은 push 메서드를 구현한 것입니다. 완전 이진 트리를 유지하고자 heapsize를 이용하고 아이템의 키와 부모의 키 값을 비교해서 위치를 찾게 됩니다. 그림 11-7과 비교하면 쉽게 이해할 수 있을 것입니다.
이제 pop 연산을 알아보겠습니다. 최대 힙은 pop 연산에서 힙에서 가장 큰 키를 가진 요소를 삭제하며 반환합니다. 힙에서 가장 큰 키는 루트 노드에 있지요.