힙

• Heap tree or Heap 은 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 완전 이진 트리를 말한다.
• 여러 개의 값들 중에서 최댓값이나 최소값을 빠르게 찾아내도록 만들어진 자료구조이다.
  • 최대 heap : 부모노드의 값은 자식 노드의 값보다 항상 큰 규칙을 지키는 힙을 의미한다. 이를 통해 요소 중 가장 큰 값을 O(1)만에 찾을 수 있다.
  • 최소 heap : 부모노드의 값은 자식 노드의 값보다 항상 작은 규칙을 지키는 힙을 의미한다. 이를 통해 요소 중 가장 작은 값을 O(1)만에 찾을 수 있다.
• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
• 힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다.
  • 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
  • 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
• 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

힙의 데이터 삽입

여기서 규칙이란 최소힙, 최대힙의 규칙을 말합니다.

1. 리프노드에 삽입할 노드를 삽입한다.
2. 해당노드와 부모노드를 서로 비교한다.
3. “규칙”에 맞으면 그대로 두고, 그렇지 않으면 부모노드와 교환한다.
4. 규칙에 맞을 때까지 3번 과정을 반복한다.

최소힙의 삽입과정