05-6 힙

※ 힙(heap)

 - 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이가장 작은 노드를 찾기 위해 만든 자료구조.

 - 키값이 가장 큰 노드를 찾기 위한 힙을 최대 힙(Max Heap) : 부모 노드의 키값 >= 자식노드의 키값

 - 키값이 가장 작은 노드를 찾기 위한 힙을 최소 힙(Min Heap) : 부모 노드의 키값 <= 자식노드의 키값

 - 완전 이진 트리로써 일반적인 힙은 최대 힙을 의미하며 같은 키값의 노드가 중복 될 수 있다.

※ 힙에서의 삽입연산

 - 완전 이진트리의 형태를 유지해야 하고 부모노드의 자식 노드간의 크기의 조건도 유지해야 한다.

   일단 완전이진 트리를 만족하기 위해 마지막 노드의 자리에 삽입 연산을 한다. 그런 후 크기 조건이 맞으면 그냥 삽입하      고 크기 조건이 맞지 않으면 키값을 바꾸어 크기 조건에 맞게 정렬을 해주어야 된다.

※ 힙에서의 삭제연산

 - 힙에서 삭제연산은 루트 노드에 있는 원소를 반환하고 삭제한다.

   즉 최대값 아니면 최소값을 반환한다.

   루트 노드를 반환하고 삭제한 후에도 완전 이진트리의 형태와 노드 키값의 조건을 만족해야 된다.

 - 완전 이진트리의 형태를 만족하기 위해서는 루트노드를 삭제한 후에 마지막 노드를 루트노드 자리에 삽입해준다.

   그런 후 노드 키값의 조건을 맞추기위해 정렬을 한다.

※ 순차 자료구조 방식을 이용한 힙의 구현

 - 1차원 배열의 순차 자료구조 방식을 이용하면 배열 인덱스의 관계를 바탕으로 부모노드를 쉽게 찾을 수 있다.