부산대학교자료구조
Scientific Inference Lab

Up and Down One Level

Heap Operations

삽입과 삭제 뒤 힙 성질을 되찾는 이동을 배열로 추적한다.

문제 1

넣고 올리기

문제 1과 2는 0부터 세는 최소 힙 H = [3, 8, 5, 12, 10, 9, 7, 15]에서 각각 따로 시작한다.

  1. 4를 넣을 때 처음 놓이는 인덱스를 적는다.
  2. sift up의 각 단계에서 비교하는 인덱스와 값, 교환 여부를 적고 멈추는 조건을 적는다.
  3. 삽입 뒤의 배열을 적는다.
  4. 교환 횟수의 최댓값을 높이로 적고 삽입 비용을 적는다.
해설 펼치기
  1. 모양 조건을 지키려면 배열 끝, 인덱스 8이다.
  2. 8: 4 ↔ 부모 3: 12 교환. 3: 4 ↔ 부모 1: 8 교환. 1: 4 ↔ 부모 0: 3에서 4 ≥ 3이라 멈춘다.
  3. [3, 4, 5, 8, 10, 9, 7, 15, 12]다.
  4. 한 번에 한 레벨씩 올라가므로 많아야 높이 ⌊log₂ n⌋번이고 O(log n)이다.
문제 2

꺼내고 내리기

문제 1의 원래 최소 힙 H에서 새로 시작한다.

  1. 최솟값 꺼내기로 반환하는 값과 루트 자리에 올리는 값을 적는다.
  2. sift down의 각 단계에서 비교하는 자식과 교환 대상을 적고 멈추는 이유를 적는다.
  3. 삭제 뒤의 배열을 적는다.
  4. 첫 단계에서 더 큰 자식 8과 바꾸면 어떤 문제가 생기는지 적는다.
해설 펼치기
  1. 3을 반환하고 마지막 자리의 15를 루트로 옮긴다.
  2. 0: 15의 자식 8과 5 중 더 작은 5와 교환. 2: 15의 자식 9와 7 중 더 작은 7과 교환. 6: 자식이 없어 멈춘다.
  3. [5, 8, 7, 12, 10, 9, 15]다.
  4. 새 부모 8이 다른 자식 5보다 커져 그 자리에서 힙 성질이 다시 깨진다.
문제 3

heapify 과정

배열 A = [6, 5, 4, 3, 2, 1, 0]을 힙으로 만든다.

  1. heapify가 하향 이동을 시작하는 인덱스와 그 순서를 적는다.
  2. 각 인덱스의 하향 이동 뒤 배열을 적는다.
  3. 같은 값을 빈 힙에 차례로 넣어 만든 배열이 [0, 3, 1, 6, 4, 5, 2]일 때, heapify 결과와 다른데도 둘 다 힙인 이유를 적는다.
  4. n번 삽입과 heapify의 비용을 적고 heapify가 O(n)인 이유를 적는다.
해설 펼치기
  1. 마지막 부모 ⌊7/2⌋ − 1 = 2부터 1, 0 순서로 내려간다. 단말 노드는 이미 힙이다.
  2. 인덱스 2: 4와 0 교환 → [6, 5, 0, 3, 2, 1, 4]. 인덱스 1: 5와 2 교환 → [6, 2, 0, 3, 5, 1, 4]. 인덱스 0: 6과 0 교환 뒤 인덱스 2에서 6과 1 교환 → [0, 2, 1, 3, 5, 6, 4].
  3. 힙 성질은 부모와 자식의 관계만 정하므로 같은 값 집합에도 여러 힙이 가능하다. 두 배열 모두 모든 부모가 자식보다 작거나 같다.
  4. n번 삽입은 O(n log n), heapify는 O(n)이다. 노드가 많은 아래쪽은 내려갈 거리가 짧고 거리가 긴 위쪽은 노드가 적어 합이 n에 비례한다.
문제 4

힙 정렬

  1. heapify와 최솟값 꺼내기 n번으로 이루어진 힙 정렬의 전체 비용을 적는다.
  2. 꺼낸 값을 배열 뒤쪽에 쌓는 제자리 정렬에서 오름차순을 얻으려면 어떤 힙을 쓰는지 적는다.
  3. 키가 같은 두 학생의 입력 순서가 힙 정렬 뒤에 유지되지 않을 수 있는 이유를 적는다.
  4. 최악 시간 복잡도가 O(n log n)인 안정적인 제자리 정렬이 필요할 때, 힙 정렬이 알맞은지 판단한다.
해설 펼치기
  1. O(n) + n × O(log n) = O(n log n)이다.
  2. 최대 힙이다. 큰 값부터 뒤에 쌓여 오름차순이 된다. 최소 힙을 쓰면 내림차순이 되어 뒤집어야 한다.
  3. 힙 정렬은 멀리 떨어진 자리를 교환하므로 안정적이지 않다.
  4. 알맞지 않다. 힙 정렬은 최악 시간 복잡도가 O(n log n)인 제자리 정렬이지만 안정적이지 않다.
문제 5

Python heapq 사용

  1. 빈 리스트에 5, 1, 4를 heappush한 뒤의 리스트와 heappop의 반환값을 적는다.
  2. Python 3.13 환경에서 최댓값부터 꺼내려면 어떻게 하는지 적고, 5, 1, 4에 적용했을 때 처음 꺼내는 값을 적는다.
  3. (2, task_a)와 (2, task_b)를 넣었는데 task 객체끼리 비교할 수 없을 때 생기는 일과 피하는 방법을 적는다.
  4. 힙 리스트가 정렬되어 있지 않아도 힙인지 판정하는 기준을 적는다.
해설 펼치기
  1. [1, 5, 4]가 되고 heappop은 1을 반환한다.
  2. 부호를 뒤집어 −5, −1, −4를 넣고 꺼낸 값의 부호를 다시 뒤집는다. 처음 꺼내는 값은 5다. Python 3.14 이상이면 heappush_max와 heappop_max를 쓸 수 있다.
  3. 우선순위가 같으면 두 번째 원소를 비교하다 예외가 난다. (우선순위, 순번, 작업)처럼 순번을 둘째 자리에 둔다.
  4. 모든 부모가 자식보다 작거나 같은지 확인한다. 배열이 정렬되었는지는 기준이 아니다.