힙 ADT

내부노드에 key를 저장하고 외부노드에는 key가 없는 이진트리
다음을 만족해야 한다.

• 힙 순서 : 루트를 제외한 모든 내부노드 v에 대해
  • 최소힙이면 key(v) ≥ key(parent(v))
  • 최대힙이면 key(v) ≤ key(parent(v))
• 완전이진트리 : 각 깊이(0, 1, 2, ..., h-1)에는 노드가 $2^{깊이값}$개 존재 (h-1깊이는 1개 이상)
  • 이 성질에 따라 n개의 키를 저장한 힙의 높이는 $O(\log{n})$이다.
  • 깊이 h-1에서 내부노드들은 외부노드들의 왼쪽에 위치한다.

힙은 last node를 관리한다.

• 깊이 h-1의 가장 오른쪽 내부노드를 last node라 부른다.
• last node는 후진(retreatLast), 전진(advanceLast)할 수 있다.

 [최대힙 예시]        [최소힙 예시]
      10                  1 
    /   \               /   \
  7       8            3      5
 / \     / \          / \    / \
1   3   5   X       10   X  X   X
** 5는 last node     ** 10은 last node
** X는 외부 노드     

힙 삽입/삭제

삽입/삭제 설명에서 힙은 최소힙이라고 가정한다.

삽입

1. last node위치를 한 칸 전진시킨다.
2. 새로운 위치의 last node를 내부노드로 만든다.
3. 새로운 위치의 last node에 키값을 넣는다.
4. Upheap을 통해 힙순서를 복구한다.
   Upheap은 삽입된 키가 힙순서가 복구될 때 까지 위로 올라가는 과정이다.

Alg insertItem(k)
  input 키 k, 노드 last
  output none

1. advanceLast()
2. z ← last     # z는 advance로 지정된 새로운 lastnode다.
3. set node z to k
4. expandExternal(z)
5. upHeap(z)
6. return
------------------
Alg upHeap(v)
  input node v
  output none

1. if(isRoot(v))
     return
2. if(key(v)≥key(parent(v)) # 최소힙 속성을 만족하는지 확인
     return
3. swapElements(v, parent(v))
4. upHeap(parent(v))
------------------
Alg expandExternal(z)
  input external node z
  output none

1. l ← getNode()
   r ← getNode()
2. l.left ← ø     # l, r의 자식은 없음
   l.right ← ø
   r.left ← ø
   r.right ← ø
3. l.parent ← z   # l, r의 부모는 z
   r.parent ← z
4. z.left ← l     # z의 자식은 l, r
   z.right ← r
5. return
------------------
Alg advanceLast()
  input lastnode last
  output 전진할 위치의 노드
  
1. z ← last
   if(isRoot(z))
     return z.left
2. while(z = (z.parent).right)
     z ← z.parent
3. while(z = (z.parent).left)
     z ← z.sibling
4. while(isInternal(z))
     z ← z.left
5. return z

힙 삭제

최소힙으로 가정했기에 removeMin()은 root노드를 삭제한다.

1. 루트 키값을 k에 저장해둔다. (마지막에 리턴하기 위해)
2. last node 키값을 루트에 넣고, last node 한 칸 후진
3. 후진하기 전 기존 last node를 외부노드로 축소
4. downHeap으로 힙순서 복구
   downHeap은 힙순서가 복구될 때 까지 루트를 밑으로 내리는 작업이다.
5. 저장해뒀던 k 리턴

Alg removeMin()
  input node last
  output key

1. k ← key(root())
2. w ← last            # last노드 값을 root로 보낸 뒤 last노드 후퇴
   set root to key(w) 
   retreatLast()
3. z ← w.right         # last는 후퇴했지만 이전 last는 여전히 내부노드이다.
   reduceExternal(z)     외부노드로 만들어서 정리해야 한다.
4. downHeap(root())
5. return k
---------------------
Alg downHeap(v)
  input node v (부트리가 모두 힙인 노드)
  output 힙순서를 만족하는 힙

1. if(isExternal(v.left) & isExternal(v.right))
     return
2. smaller ← v.left
   if(isInternal(v.right))
     if(key(v.right) < key(smaller))
       smaller ← v.right
3. if(key(v) ≤ key(smaller))
     return
4. swapElement(v, smaller)
5. downHeap(smaller)
---------------------
Alg reduceExternal(z)
  input external node z
  output z의 부모를 대체할 노드

1. w ← z.parent
   zs ← z.sibling
2. if(isRoot(w))
     root ← zs
     zs.parent ← ø
   else
     g ← w.parent
     zs.parent ← g
     if(w = g.left)
       g.left ← zs
     else
       g.right ← zs
3. putnode(z)
   putnode(w)
4. return zs
---------------------
Alg retreatLast()
  input lastnode last
  output 후진할 노드의 위치

1. z ← last
2. while(z = (z.parent).left)
     z ← z.parent
3. while(z = (z.parent).right)
     z ← z.sibling
4. while(isInternal(z))
     z ← z.right

배열 기반 힙 구현

배열의 첨자 i에 대해

• 0번 인덱스는 사용하지 않는다.
• 1번 인덱스는 루트 노드
• 2*i번 인덱스는 왼쪽자식
• 2*i+1번 인덱스는 오른쪽자식
• i/2번 인덱스는 부모

     10
   /    \
  5      6
 / \    / \
1   2  3   X

  0   1   2   3   4   5   6   index
+---+---+---+---+---+---+---+
|   | 10| 5 | 6 | 1 | 2 | 3 | key
+---+---+---+---+---+---+---+

힙 정렬

여기서는 '최대 힙'을 구현한다.
(루트는 가장 큰 키, removeMin대신 removeMax)

일반 힙 정렬

Alg heapSort(L)
   input 무순리스트 L
   output 정렬된 리스트 L
   
1. H ← 비어있는 힙
2. while(!L.isEmpty())
     k ← L.removeFirst()
     H.insertItem(k)
3. while(!H.isEmpty())
     k ← H.removeMax()
     L.addFirst(k)
4. return

제자리 힙정렬

입력으로 주어진 무순리스트 L이 배열일 때 제자리 정렬할 수 있다.
heapSort알고리즘의 제 2의 공간 H가 필요없어져 공간 사용을 줄일 수 있다.

만약 L이 n개의 원소를 갖고 있다면 배열크기는 n+1이다.
(0번 인덱스는 사용하지 않기 때문에, 인덱스 0~n-1이 아닌 1~n을 사용)

Alg inplaceHeapSort(A)
  input n개 키를 가진 배열 A
  output 정렬된 배열 A
  
1. buildHeap(A)
2. for i ← n downto 2
     A[1] ←→ A[i]
     downHeap(1, i-1)
3. return
--------------------------
Alg buildHeap(A)
  input n개 키를 가진 배열 A
  output 사이즈 n의 힙 A

for i ← 1 to n
  insertItem(A, i)
return
--------------------------
Alg insertItem(A, i)
  input 부분적으로 힙인 배열 A, index i
  output i번 인덱스까지 힙인 배열 A

1. upHeap(A, i)
2. return
--------------------------
Alg upHeap(A, i)

1. if(i = 1)        # root
     return
2. if(A[i] <= A[i/2])  # 자신의 키값 <= 부모의 키값 이면
     return
3. A[i] ←→ A[i/2]
4. upHeap(A, i/2)  *** modified (20.Oct.2023)
--------------------------
Alg downHeap(i, last)
  input 크기가 last인 최대 힙 A의 인덱스 i, last 인덱스
  output none
  
1. left ← 2i
   right ← 2i+1
2. if(left > last)
     return
3. greater ← left
   if(right <= last)
     if(A[right] > A[greater])
       greater ← right
4. if(A[i] >= A[greater])
     return
5. A[i] ←→ A[greater]
6. downHeap(greater, last)

상향식 힙 생성

위에서 계속해서 수행한 insertItem을 사용한 힙 생성은 '삽입식 힙 생성' 이라고 한다.
그 대신 상향식 힙 생성 방법을 사용하면 heapSort알고리즘의 힙 생성 시간을 단축할 수 있다.

힙의 키값이 모두 주어진 경우에만 사용할 수 있다.

• 재귀적 상향식 힙 생성

Alg buildHeap(L)
  input n개 키를 저장하는 리스트 L
  output 리스트L의 키를 저장한 힙 T
  
1. T ← convertToCompleteBinaryTree(L)
2. rBuildHeap(T.root())
3. return
---------------------------
Alg rBuildHeap(v)
  input node v
  output root v를 갖는 힙

1. if(isInternal(v))
     rBuildHeap(v.left)
     rBuildHeap(v.right)
     downHeap(v)
2. return

• 비재귀적 상향식 힙 생성
  • 주어지는 리스트가 배열일 때만 사용할 수 있다.

Alg buildHeap(A)
  input n개 키를 가진 배열 A
  output 사이즈가 n인 힙 A

1. for i ← ⌊ n/2 ⌋ downto 1
     downHeap(i, n)
2. return