[자료구조] Heap힙

Selection / Insertions Sort의 문제점

• 1단계 : 입력 set에서 큐 구축
• 2단계 : 우선순위 큐 구축

---

• Selection sort: Phase 1은 빠르지만 Phase 2는 매우 느리다.
• Insertion sort: Phase 1은 매우 느리지만 Phase 2는 빠르다.

How can we balance the running times of the two phases?:

• 효율적인 우선순위 큐의 구현은 heap이라는 데이터 구조를 사용

Heap Data Structures

Heap(힙): 이진 트리 T는 관계적 속성과 구조적 속성을 만

1. 힙 순서 속성(Heap-order Property): 힙 T에서 루트가 아닌 모든 노드 v에 대해, v에 저장된 키는 v의 부모에 저장된 키보다 크거나 같다.
2. 완전 이진 트리 속성(Complete binary tree property): 높이 h를 가진 힙 T에서
   • T의 레벨 0부터 h-1까지의 각 레벨은 가능한 최대 노드 수를 갖습니다. (레벨 i는 2^i개의 노드를 가집니다, 0 ≤ i ≤ h-1)
   • 레벨 h에서, 모든 내부 노드는 외부 노드의 왼쪽에 있으며, 최대 하나의 자식을 가진 노드가 있다. 이 자식은 왼쪽 자식이어야 함.

• 힙의 마지막 노드는 최대 깊이의 가장 오른쪽 노드

Height of a Heap

정리: 키 n개를 저장하는 힙은 높이 O(log n)

증명: 완전 이진 트리 속성complete binary tree

• 키 n개를 저장하는 힙의 높이를 h라고 둔다.
• i = 0부터 h - 1까지의 각 깊이에는 2^i개의 키가 있고, h 깊이에는 적어도 하나의 키가 존
• 따라서, n ≥ 1 + 2 + 4 + ... + 2^(h-1) + 1
• 따라서, n ≥ 2^h, 즉 h ≤ log n

힙과 우선순위 큐

• 힙을 사용하여 우선순위 큐 구현
• 각 내부 노드에는 (key, element)저장
• 마지막 노드의 위치를 추적(루트 노드 포함)

Insertion into a Heap 힙 삽입

1. 삽입 노드 z를 찾는다. (새로운 마지막 노드)
2. z에 k를 저장
3. 힙 순서 속성 heap - order property 복원

Upheap

• 새로운 키 k가 insert 된 이후에는 heap order에 위배될 수 있다.
• upheap 알고리즘은 삽입 노드로부터 위쪽 경로를 따라 k를 교환
• k가 루트에 도달하거나, parent의 키가 k보다 작거나 같은 노드에 도달할 때까지 실행
• 힙의 높이 = O(log n) ⇒ upheap 실행 시간 : O(log n)

Removal from a Heap 힙에서 제거

1. 루트의 키를 마지막 노드 w로 대체
2. w를 제거
3. 힙 order 복원

Downheap

• 루트 키를 k로 대체하면 힙 order이 깨질 수 있다.
• downheap 알고리즘은 아래쪽 경로를 따라 키 k를 교환
• k가 리프 노드에 도달하거나, child의 키가 k보다 크거나 같은 노드에 도달할 때까지 실행
• 힙의 높이 = O(log n) ⇒ upheap 실행 시간 : O(log n)

Updating the Last Node

• 삽입 노드는 O(log n)노드의 경로를 탐색하여 찾을 수 있다.

---

1. Last node가 left-child인 경우 : Sibling이 insertion 위치
2. Last node가 Right-child인 경우 :
   1. left-child 노드를 만날 때 까지 이동 → Right-child(Sibling)으로 이동→리프노드를 만날 때까지 Left로 이동
   2. 루트를 만날 때까지 이동→ 리프 노드를 만날 때까지 Left로 이동 → Leaf노드가 insertion 위치

Bottom-up Heap Construction

O(n)

Heap-Sort

• 공간 : O(n)
• insert , removeMin : O(logn)
• size, isEmpty, min : O(1)
• 힙 정렬 : O(nlogn)
• 삽입 정렬이나 선택 정렬보다 빠르다

In-Place Heap Sort

• 시퀀스는 배열을 통해 구현된다고 가정
• 힙 정렬을 가속화, 공간 요구 사항을 상수 배로 줄임
• 시퀀스의 원소를 재배열

---

• 힙의 원소는 S의 왼쪽 부분(i-1)에 저장
• 정렬되지 않은 원소는 오른쪽 부분(i부터 n까지)에 저장
• S의 첫 i개의 원소는 힙의 벡터 표현을 제공한다.
• empty heap에서 시작해서 경계를 한칸씩 오른쪽으로 이동
• i단계에서는 i의 원소를 추가하여 힙을 확장

---

Phase 1 : Heap 만들기

• 빈 heap에서 시작하여 힙과 시퀀스의 경계를 오른쪽으로 이동한다.

Phase 2 : Heap 정렬

• 빈 시퀀스에서 시작하여 힙과 시퀀스의 경계를 왼쪽으로 이동한다.

Merging Two Heaps

• 두 개의 Heap과 키 k가 주어진다.
• 루트 노드로 k를 갖고 두 개의 Heap을 sub Tree로 갖는 새 Heap을 생성
• heap - order 특성을 복원하기 위해 downHeap을 사용
  •