사용 개념: 최대 힙과 최소 힙의 넣기와 꺼내기. 배열은 1번 칸부터 쓴다. \(i\)번 칸의 부모는 \(\lfloor i/2 \rfloor\)번, 자식은 \(2i\)번과 \(2i + 1\)번이다.

힙에 값을 넣고 꺼내는 과정을 손으로 따라가는 문제는 같은 하위목표의 되풀이다.

  • 넣기: ① 새 칸(구멍)의 번호를 정한다 ② 구멍의 부모가 넣을 값보다 작으면 부모를 내려 적고 구멍을 올린다 ③ 멈춘 자리에 값을 적는다.
  • 꺼내기: ① 뿌리의 값을 돌려줄 값으로 적어 둔다 ② 마지막 칸의 값을 떼어 손에 들고 배열을 한 칸 줄인다 ③ 구멍(뿌리)의 두 자식 가운데 큰 쪽이 손에 든 값보다 크면 그 자식을 올려 적고 구멍을 내린다 ④ 멈춘 자리에 손에 든 값을 적는다.

아래 풀이에서 _는 구멍이다. 최소 힙은 “작으면”과 “크면”, “큰 쪽”과 “작은 쪽”을 서로 바꾼다1.

문제 1 · 완전한 풀이

최대 힙 9 8 7 6 7 2 6 5 1에 20을 넣고, 이어서 15를 넣은 뒤, 두 번 꺼낸다.

20 넣기.

  1. 구멍 정하기: 값이 9개이니 새 칸은 10번이다. 9 8 7 6 7 2 6 5 1 _
  2. 구멍 올리기: 10번의 부모는 5번(7). \(7 < 20\)이라 7을 10번에 적는다. 9 8 7 6 _ 2 6 5 1 7. 5번의 부모는 2번(8). \(8 < 20\)이라 8을 5번에 적는다. 9 _ 7 6 8 2 6 5 1 7. 2번의 부모는 1번(9). \(9 < 20\)이라 9를 2번에 적는다. _ 9 7 6 8 2 6 5 1 7.
  3. 값 적기: 구멍이 뿌리라 멈춘다. 20 9 7 6 8 2 6 5 1 7.

15 넣기.

  1. 구멍 정하기: 새 칸은 11번이다.
  2. 구멍 올리기: 11번의 부모는 5번(8). \(8 < 15\)라 8을 11번에. 5번의 부모는 2번(9). \(9 < 15\)라 9를 5번에. 2번의 부모는 1번(20). \(20 < 15\)가 아니니 멈춘다.
  3. 값 적기: 2번 칸에 15. 20 15 7 6 9 2 6 5 1 7 8.

첫 번째 꺼내기.

  1. 돌려줄 값: 뿌리의 20.
  2. 마지막 값 들기: 11번 칸의 8을 들고 배열을 10칸으로 줄인다. _ 15 7 6 9 2 6 5 1 7
  3. 구멍 내리기: 1번의 자식은 15와 7. 큰 쪽 15가 8보다 크니 15를 1번에. 15 _ 7 6 9 2 6 5 1 7. 2번의 자식은 6과 9. 큰 쪽 9가 8보다 크니 9를 2번에. 15 9 7 6 _ 2 6 5 1 7. 5번의 자식은 10번(7) 하나. 7은 8보다 크지 않으니 멈춘다.
  4. 값 적기: 5번 칸에 8. 15 9 7 6 8 2 6 5 1 7.

두 번째 꺼내기.

  1. 돌려줄 값: 15.
  2. 마지막 값 들기: 10번 칸의 7을 들고 9칸으로 줄인다.
  3. 구멍 내리기: 1번의 자식 9와 7 가운데 9를 올린다. 2번의 자식 6과 8 가운데 8을 올린다. 5번의 자식이 될 10번 칸은 이제 없다. 멈춘다.
  4. 값 적기: 5번 칸에 7. 9 8 7 6 7 2 6 5 1. 처음 힙으로 돌아왔다.
검증 — 27_heap-tracing-ladder_p4.c

문제 2 · 마지막 하위목표만 빈칸

최대 힙 50 30 40 10 20 35에 45를 넣고, 이어서 한 번 꺼낸다.

45 넣기.

  1. 구멍 정하기: 새 칸은 7번이다. 50 30 40 10 20 35 _
  2. 구멍 올리기: 7번의 부모는 3번(40). \(40 < 45\)라 40을 7번에 적는다. 50 30 _ 10 20 35 40. 3번의 부모는 1번(50). \(50 < 45\)가 아니니 멈춘다.
  3. 값 적기: 3번 칸에 45. 50 30 45 10 20 35 40.

꺼내기.

  1. 돌려줄 값: 50.
  2. 마지막 값 들기: 7번 칸의 40을 들고 6칸으로 줄인다. _ 30 45 10 20 35
  3. 구멍 내리기와 4. 값 적기: __
답

1번의 자식은 30과 45. 큰 쪽 45가 40보다 크니 45를 1번에 적는다. 45 30 _ 10 20 35. 3번의 자식은 6번(35) 하나다(7번 칸은 없어졌다). 35는 40보다 크지 않으니 멈추고 3번 칸에 40을 적는다. 결과는 45 30 40 10 20 35다.
흔한 실수는 3번의 자식으로 방금 뗀 7번 칸의 40을 다시 보는 것이다. 배열은 이미 6칸이다.

문제 3 · 하위목표 절반이 빈칸

최대 힙 90 70 80 30 60 50 20 10에 85를 넣고, 이어서 두 번 꺼낸다.

85 넣기.

  1. 구멍 정하기: 새 칸은 9번이다.
  2. 구멍 올리기: __
  3. 값 적기: 90 85 80 70 60 50 20 10 30.

첫 번째 꺼내기.

  1. 돌려줄 값: 90.
  2. 마지막 값 들기: __
  3. 구멍 내리기: 1번의 자식 85와 80 가운데 85를 올린다. 2번의 자식 70과 60 가운데 70을 올린다. 4번의 자식은 8번(10) 하나이고, 10은 손에 든 값보다 크지 않으니 멈춘다.
  4. 값 적기: __

두 번째 꺼내기.

  1. 돌려줄 값: 85.
  2. 마지막 값 들기: 8번 칸의 10을 들고 7칸으로 줄인다.
  3. 구멍 내리기: __
  4. 값 적기: 80 70 50 30 60 10 20.
답

85 넣기 2. 9번의 부모는 4번(30). \(30 < 85\)라 30을 9번에 적는다. 4번의 부모는 2번(70). \(70 < 85\)라 70을 4번에 적는다. 2번의 부모는 1번(90). \(90 < 85\)가 아니니 멈춘다. 구멍은 2번이다.
첫 번째 꺼내기 2. 9번 칸의 30을 들고 8칸으로 줄인다. _ 85 80 70 60 50 20 10
첫 번째 꺼내기 4. 4번 칸에 30을 적는다. 85 70 80 30 60 50 20 10.
두 번째 꺼내기 3. 1번의 자식 70과 80 가운데 큰 쪽 80이 10보다 크니 올린다. 3번의 자식 50과 20 가운데 큰 쪽 50이 10보다 크니 올린다. 6번의 자식이 될 12번 칸은 없으니 멈춘다. 구멍은 6번이다.

검증 — 27_heap-tracing-ladder_p4.c

문제 4 · 독립 문제

빈 최소 힙에 8, 3, 6, 1, 5, 2를 차례로 넣는다. 값을 하나 넣을 때마다의 배열을 쓰라. 이어서 두 번 꺼낼 때 나오는 값과 꺼낸 뒤의 배열을 쓰라. 같은 값들을 최대 힙에 넣었다면 배열은 어떻게 되는가?

답

넣기: 8 → 3 8 → 3 8 6 → 1 3 6 8 → 1 3 6 8 5 → 1 3 2 8 5 6.

  • 3을 넣을 때 부모 8이 더 커서 8이 내려온다.
  • 1을 넣을 때 구멍이 4번 → 2번 → 1번으로 올라가며 8과 3이 한 칸씩 내려온다.
  • 5는 부모 3보다 작지 않아 5번 칸에 그대로 놓인다.
  • 2를 넣을 때 부모 6(3번 칸)이 더 커서 내려오고, 그 위의 1은 2보다 크지 않아 멈춘다.

첫 번째 꺼내기: 1이 나온다. 마지막 값 6을 들고, 뿌리의 자식 3과 2 가운데 작은 쪽 2를 올린다. 3번 칸에는 이제 자식이 없으니 6을 적는다. 2 3 6 8 5.
두 번째 꺼내기: 2가 나온다. 마지막 값 5를 들고, 뿌리의 자식 3과 6 가운데 작은 쪽 3을 올린다. 2번의 자식은 4번(8) 하나이고 8은 5보다 작지 않으니 멈춘다. 3 5 6 8.

최대 힙에 같은 차례로 넣으면 8 5 6 1 3 2다. 같은 값들이라도 방향에 따라 배열이 전혀 다르고, 어느 쪽도 정렬된 배열은 아니다.

검증 — 27_heap-tracing-ladder_p4.c

  1. 모든 단계의 배열은 문제 코드가 찍은 것과 같다. ↩