힙이란?
힙은 더미를 의미하는데 여래 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 완전 이진트리를 말한다. 힙의 종류로는2가지가 있다.
최대 힙(max heap)
보모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리를 말한다. 가장 큰 요소가 루트노드에 있으며, 이를 통해 요소 중 가장 큰 값을 O(1)만에 찾을 수 있다.
우선 순위에 따라 요소가 배치되며 N개의 노드를 가지고 있는 힙의 높이는 O(logn)이다. 마지막 레벨을 제외하고 각 레벨 i에 2^i개의 노드가 존재한다.
최소 힙(min heap)
부모 노드의 키 값이 자식노드의 키 값보다 작거나 같은 완전 이진 트리를 말한다. 가장 작은 요소가 루트노드에 있으며, 이를 통해 요소 중 가장 작은 값을 O(1)만에 찾을 수 있다. 
힙(heap)의 ADT
힙의 데이터 삽입
(1)힙의 새로운 요소가 들어오면 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
(2)삽입 후에 새로운 노드를 부모 노드와 서로 비교한다.
(3)힙의 성질에 만족한다면 그대로 두고, 그렇지 않으면 부모노드와 교환한다.
(4) 힙의 성질에 만족할때까지 3번 과정을 반복한다.
최소힙의 삽입 과정
최대힙의 삽입 과정
힙의 데이터 삭제
루트노드만을 제거할 수 있으며, 순서는 다음과 같다.
(1) 루트노드를 제거한다.
(2) 루트노드 자리에 가장 마지막 노드를 삽입한다.
(3) 올라간 노드와 그의 자식 노드와 비교한다.
(4) 힙의 성질과 만족한다면 그대로 두고, 그렇지 않다면 자식노드와 교환한다.
최소힙의 삭제과정
최대힙의 삭제과정
힙과 이진탐색 트리와의 차이점?
이진 탐색트리는 탐색을 쉽게 하기 위해 왼쪽이 더 작고 오른쪽이 큰값으로 꼭 구성이 되어야 하지만 힙은 그렇지 않다, 또한, 최소힙을 기반으로 설명하자면 이진탐색트리는 왼쪽자식노드가 부모노드보다 더 작은 값을 가지는데 최소힙은 그렇지 않다.
힙의 시간복잡도
- 참조(최대또는최소값을참조):O(1) -> 루트노드
- 탐색:O(n) -> 해당하는 노드를 찾을때까지 돌아야 하기 때문
- 삽입/삭제:O(logn) -->완전 이진트리이고 높이가 logn이기 때문
