Heap

●Heap

 ▷Binary Tree의 일종

 ▷Node에 key값들을 저장한다.

 

 ▶조건

  ▶Heap-Order : key(v) ≥ key(parent(v)) 만족

   ▷최소 Heap - root = 최소 key

   ※ key(v) ≤ key(parent(v)) 인 경우, 최대 Heap

 

  ▶Complete Binary Tree 만족

   ▷높이가 h인 Binary Tree에 대해서, depth i (i < h)에는 2ⁱ 개의 Node가 있다.

   ▷Internal nodes는 External nodes의 왼쪽에 있다.

 

 

 ▶Height of a Heap

  ▷n개의 key를 가지는 Heap의 height : log(n)

  ▷n = 1 + 2 = 4 + ... + 2^h-1 + (1 ~ 2^h) ＜ (2^h+1)

 

 ▶Bottom-up Heap Construction

  ▶Heap Merging 이용

   ▷2개의 Heap과 새로운 key K에 대해

   ▷k를 root로하며, 2개의 Heap을 subtree로 하는 Heap 생성

   ▷downheap - heap order restore

 

  ▶phase i에서

   ▷2ⁱ - 1의 heap 2개를 가지고 2ⁱ⁺¹ - 1인 Heap을 만듬.

   ▷O(log(n))

 

  

 

 ▶Heap - Priotity Queue

  ▷Heap을 이용하여 Priority Queue 구현

  ▷각 Node에 Key, Element 저장

  ▷Insert, removeMin 효율적으로 동작 가능

  ▷Last Node Tracking (마지막 노드)

 

  ▶Insertion

   ▷Last Node 다음에 새로운 element 저장 (key값 저장, Last Node Update)

   ▶Heap Order Restore (Upheap)

    ▷새로운 Node가 Heap order를 만족하지 않을 수 있음.

    ▷부모 노드로 가며 Swaping (key값이 부모 노드보다 작으면 Swap)

    ▷root이거나, 부모 노드보다 클 때 까지 반복

    ▷O(log(n))

 

  ▶Removal

   ▷Root Node의 Key를 제거

   ▷공백을 Last Node로 매꿈 (+Last Node Update)

   ▶Heap Order Restore (Downheap)

    ▷새로운 root Node가 Heap order를 만족하지 않을 수 있음.

    ▷root에서 자식 노드로 가며 Swaping (key값이 자식 노드들보다 크면 자식 중 하나와 Swap)

    ▷최대 height (log(n)) 에 도달하거나, 자식 노드들보다 작을 때 까지 반복

    ▷O(log(n))

 

  ▶Last Node Update

   ▷left child에 도달하거나, root에 도달할 때 까지 위로 감. (부모로 감)

   ▷left child에 도달한다면, right child로 이동

   ▷leaf까지 왼쪽 아래로 이동

   ▷O(log(n))

 

 

○Heap-sort

 ▷Heap으로 구현된 Priority Queue의 Sorting

 ▷차지하는 공간 : O(n)

 

 ▷Insert : O(log n)

 ▷removeMin : O(log(n))

 

 ▷n개의 element : O(n log(n))

 

 

○Vector-based Heap

 ▷Vector로 Heap 구현

 ▷length : n + 1인 Vector 사용 (index 0은 사용하지 않음)

 

 ▶Positioning : rank i의 Node에 대해

  ▷left child : rank 2i

  ▷right child : rank 2i+1

 

 ▷Insert(e) : rank n+1에 insert

 ▷removeMin() : rank n remove

 

 ▶In-place Heap Sort

  ▷1. Vector를 Heap으로 만듬

  ▷2. removeMin()하며 Sorting