heap이란?

최대값이랑 최소값을 빠르게 찾기위해 고안된 구조

• 각 노드의 key값이 해당 노드의 자식노드의 key값보다 작지 않거나 크지 않은 완전 이진트리
• 키 값의 대소관계는 부모-자식 노드 사이 간에만 성립하며 형제 노드 사이에는 영향을 미치지 않음
• 자식노드의 최대 개수는 힙의 종류에 따라 다르지만 이진트리에서는 최대 2개 (완전이진트리를 사용한다고 가정하자.)
• i번째 노드의 자식노드가 2개인데 왼쪽 자식노드는 2i, 오른쪽 자식노드는 2i+1이고, 부모노드는 i/2가 된다.

최대 힙

각 노드의 키 값이 그 자식노드의 키 값보다 작지 않은 힙

최소 힙

각 노드의 키 값이 그 자식노드의 키 값보다 크지 않은 힙

시간복잡도

O(log n)

삭제연산

힙에서는 루트 노드만 삭제가 가능하므로 루트 노드를 제거한다.
가장 마지막 노드를 루트로 이동시킨다.
자식노드와 비교하여 조건이 만족할 때까지 이동시킨다.

삽입연산

삽입하고자 하는 값을 트리의 가장 마지막 원소에 추가한다.
부모노드와의 대소관계를 비교하면서 만족할 때까지 자리 교환을 반복한다.