Lecture7~8

• Heapsort

  • 러닝 타임 : O(nlgn) like merge sort

  • In place sort : like insertion sort

  • Perfect Binary Tree 포화 이진 트리

    

    • 2개의 자식노드를 항상 갖고 있으며, 모든레벨의 노드까지 완전히 다 차있는 트리구조

  • Complete Binary Tree 완전 이진 트리

    

    • 2개의 자식노드를 항상 갖고 있으며, 마지막 레벨을 제외한 모든 레벨의 노드가 차있고, 마지막 레벨의 노드는 다 채워질 수도, 아닐 수도 있다. (왼쪽에서 오른쪽 순, 위쪽에서 아래쪽 순으로 노드가 채워짐)

  • Heap

    • 2개의 특성

      • 완전 이진 트리이다.
      • 노드의 값이 자식노드보다 항상 크거나 항상 작아야한다. (일관성있게)
      • 힙은 이진트리의 일종, 부모 → 자식노드로 갈 때 일관성있게 계속 작아지거나 커지거나 해야됌

    • Max heap 최대힙

      • 부모에서 자식노드로 갈때 값이 계속 작아져야함 → 루트노드(맨꼭대기)가 제일 큰 값
      • 천장과 바닥
        • Floor x ⇒ x / ceiling x ⇒ x+1

      

      • floor 2i/2 = floor (2i+1)/2 = i 둘다 i가 되므로 자식노드에 /2를 해주면 부모노드가 된다!

    • Heap height 힙의 높이 = floor(lgn) lgn을 내림한 수랑 같다

      • 리프노드(가장 말단 노드)까지 가장 긴 엣지의 수!
        • 아래 그림에서 왼쪽은 3 오른쪽은 2이므로 높이는 3!

      

    • Heap procedures 힙의 순서

      • Max-Heapify(A, i) → A는 배열, i는 부모노드(내가 정렬하고 싶은 노드)
        • 최대힙의 특성을 유지하면서 최대힙을 만드는 함수
        • O(lgn) : 부모노드에서 자식노드로 내려가면서 교체하므로 (높이측정방법과 일치)
        • 부모노드, 자식노드2개를 비교하여 부모노드값이 작다면 밑으로 내려서 저장하기 → 재귀나 반복을 통해 밑으로 간 노드를 계속 자식노드와 비교해서 최대힙의 특성이 유지되는 위치에 보내는 과정
      • Build-Max-Heap

        • 정렬되지 않은 배열을 갖고 최대힙을 만드는 함수

        • 첫번째로 리프노드가 아닌 노드부터 루트노드까지 Max-heapify 함수 실행

        • O(n) : O(nlgn)이 아니라 왜 **O(n)**일까?

          

        • h높이에는 n/2^h+1개의 노드가 있고, h 높이 만큼만 최대로 움직이니까 O(h)

        • Loop Invariant 루프에서 불변의 성질

          • 리프노드들도 최대힙, 자식노드들도 최대힙을 유지해야 함
      • Heapsort
        • 최대힙에서 하나씩 요소를 꺼내어 배열에 다시 정렬하는 함수
        • O(nlgn)
        • 가장 말단의 리프노드를 루트노드와 값을 바꾸면 가장 말단의 리프노드에 가장 큰 값이 들어가게 되고, 그 노드를 제외시켜 추출시켜 배열에 저장하고, 바뀐 루트노드(최솟값이 들어있음)를 루트노드에 대해 Maxheapify시켜 그 다음 최댓값을 루트노드에 앉힌다.
          • 그렇게 되면, N-1개에 대해 최대힙이 구성되고, 또 이 과정을 반복하면 정렬된 배열을 얻을 수 있다.

    • Priority Queues ADT(추상적 데이터) with heap

      • Maximum(A) : 가장 큰 요소를 리턴
      • Extract-Max(A) : 가장 큰 요소를 리턴, 그리고 삭제
      • Increase-Key(A, i, key) : i번째 노드의 값을 key로 증가 → 값이 증가하면 최대힙때문에 교환 일어남
      • Insert(A, key) : A에 key라는 값을 삽입