with with

Heap Heap은 complete binary tree의 일종으로 추가로 아래의 조건을 만족하는 tree이다. 모든 노드는 그 자식노드(나아가 Descendant)보다 반드시 크거나 같아야 한다. 즉, 데이터를 넣을 때 마다 루트노드쪽으로 갈수록 큰 값이 저장되도록 정렬되는데, 이런 특징일 이용해 priority queue를 구현할 때 heap 구조가 사용된다. 데이터의 추가와 삭제를 살펴보자. push() 1. 일단 complete binary tree가 되게끔 노드를 맨 아래 왼쪽에 추가한다. 2. heap을 만족하는 적절한 위치가 될 때까지 부모노드와 위치를 바꾸며 올라간다. (reheapification upward) pop() heap에서 특정 값 pop은 생략한다. 가장 큰 값, 즉, 루트노..