Heap 힙

힙 ( Heap )
 : 최소값, 최대값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조

 힙을 공부하기전에 '이진트리'에대해 한번 더 보고 시작하자.

     이진 트리는
     트리에서 모든 노드의 차수를 2로 제한한 것이다.
     차수는 특정 노드가 하위 노드와 연결 된 개수이다.

     완전 이진 트리는
     마지막 레벨을 제외한 모든 노드가 채워져 있으며, 모든 노드가 왼쪽부터 채워져 있어야 한다.
     물론 이진 트리의 요건을 포함한다.

     포화 이진 트리는
     마지막 레벨을 제외한 모든 노드는 두 개의 자식을 갖는다. 라는 조건이다.

      힙 ( Heap )은 어떻게 최대값, 최소값을 빠르게 찾아낼 수 있을까
      정렬을 이용해서 할 경우에는 매번 새 원소가 들어올 때 마다 기존의 원소들과 비교해 재정렬이 발생하게 된다.
      그래서 힙은 트리를 이용해, 
      '부모 노드는 자식 노드보다 항상 우선순위가 높다.'
      라는 조건을 갖고 완전 이진 트리 형태로 트리를 만들게된다.

      즉, 루트 노드는 항상 우선순위가 가장 높은 노드이다.
      최소값, 최대값의 경우 O(1)의 시간 복잡도로 찾을 수 있다는 장점이 있고,
      삽입, 삭제 연산시에도 부모 노드가 자식 노드보다 우선 순위만 높으면 되므로
      트리의 깊이만큼만 비교를 하면 되기 때문에 O(log n)의 시간복잡도를 가져 빠르게 수행할 수 있다.

      추가로, 부모-자식 노드간의 관계만 신경쓰면 되기 때문에 형제간 우선순위는 고려되지 않는다.
      이러한 정렬상태를 '반 정렬 상태', '느슨한 정렬 상태', '약한 힙(week heap)'이라고 칭한다.

      ( 최소힙 : 부모 노드의 값(key값) <= 자식 노드의 값(key값)
        최대힙 : 부모 노드의 값(key값) >= 자식 노드의 값(key값) )

      ( 출처 : https://st-lab.tistory.com/205 )
     
      이 내용을 정리하고 좀 직관적으로 와닿지 않았던 것이 삽입, 삭제 연산시 시간복잡도 부분이였다.
      그래서 구현해보고 내용을 추가해보았다.
      해당 트리 구조는 배열을 통해 구현해볼 것이며, 특정 인덱스에 바로 접근할 수 있어 용이하며, 
      특정 노드의 검색, 이동과정이 연결리스트로 구현시 과정이 좀 더 복잡하기 때문이다.

      배열로 구현하게되면 나타나는 특징이 있다.
      [ 특징 ]
      1. 시간 인덱스는 0부터 시작하도록 하겠다. 많은 글에서 1부터 시작해 직관성을 부여한다고 하는데
         나는 0부터 하는게 구현과 읽는게 같아 덜 헷갈린다.
      2. 각 노드와 대응되는 배열의 인덱스는 불변.

      [ 성질 ]
      많이 등장했던 공식이 나온다.
      1. 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 X 2
      2. 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 X 2 = 왼쪽 노드 + 1
      3. 부모 노드 인덱스 = 자식 노드 인덱스 / 2


 : Heap에서 삽입은 크게 두 가지로 나뉜다. 
     1. 사용자가 Comparator를 사용해 정렬 방법을 Heap 생성 단계에서 넘겨받은 경우 ( comparator가 null이 아닌 경우 )
     2. 클래스 내에 정렬 방식을 Comparable로 구현했거나 기본 정렬 방식을 따르는 경우 ( comparotor가 null인 경우 )

     배열의 마지막 부분에 원소를 넣고, 부모노드를 찾아가면서 부모 노드가 삽입 노드보다 작을 때 까지 요소를 교환해가면서 올라간다.
     위로 올라가며 선별한다고 하여, sift-up ( 상향 선별 )이라고 불린다.

     값을 추가 할 때는 size+1 위치에 새로운 값을 추가하고 상향 선별 과정을 거쳐 재배치 한다.
     재배치 되는 삽입된 요소(노드)를 타겟노드라고 생각하면 된다.

 : Heap에서 삭제 ( 추출 ) 은 반대 방향이라 생각하면 된다.
     자료구조가 익숙치 않아 삭제라고 설명되어있는 글을 처음 읽었을때, 아 그래서 뭘 삭제한다는 건데?
     라고 생각했었는데
     추출이라고 생각하면 될 것 같다.
     최소 Heap의 경우에는 최소값을 최대 Heap의 경우에는 최대값을 배출하고, 트리에서는 삭제되는 것이다.

     루트에 있는 값을 반환하고, 가장 마지막의 노드를 루트노드에 놓고 하향 선별과정을 거쳐 배치하는 것이다.
     자식과의 크기를 비교해 자식과 위치를 바꾸고, 더 이상 위치를 바꿀 곳이 없게되면 종료되는 것으로
     레벨만큼의 비교연산이 발생하게 되어 삽입과 동일하게 O(log n)의 시간복잡도를 갖는다.