PostsSeriesLabsAlgo

자료구조

힙(우선순위 큐)

가장 급한 것부터 꺼내기

응급실 접수대입니다. 환자 카드의 숫자가 작을수록 급합니다. 가장 급한 환자가 맨 위 자리에 앉아야 합니다.
숫자 1 인 새 환자가 맨 아래 빈자리에 앉았습니다.

새 환자는 몇 번 자리를 바꿔 올라갈까요? 먼저 골라 보세요.

올라간 횟수 0

내 예상 번 · 실제 번 → 달랐어요

6번 자리 → 2번 자리 → 0번 자리새 환자가 올라간 길입니다. 부모보다 급할 때만 한 칸씩 올라갑니다.

  • 맨 위 환자 — 언제나 가장 급한 환자(가장 작은 숫자)입니다
  • 위 칸과 아래 칸 — 위 칸은 바로 아래 두 칸보다 늘 같거나 급합니다
  • 올라간 횟수 — 많아야 나무 높이만큼입니다. 환자가 100,000명이어도 16번입니다

맨 위가 늘 가장 작은 나무 = 힙. 파이썬에서는 heapq 모듈이 이 일을 해 줍니다.

아래 한 줄도 같은 나무입니다. 칸 번호로 읽으면 부모 = (자식 번호 − 1) // 2 입니다.

올 때마다 전부 다시 줄 세우기1,660,964번
힙에 앉히고 올리기 (많아야)16번
환자 한 명이 올 때의 횟수. 100,000명이 차례로 오면 다시 줄 세우기는 5시간, 힙은 1초 안입니다.

왜 맨 위만 믿을 수 있을까

  • 규칙은 하나 — 위 칸은 바로 아래 두 칸보다 늘 같거나 급하다
  • 줄 세운 게 아니다 — 새 환자를 올린 뒤 배열은 [1, 5, 2, 9, 6, 8, 3] 입니다. 앞에서부터 읽으면 작은 순서가 아닙니다. 믿을 수 있는 건 맨 앞 칸뿐입니다
  • 부모가 더 급하면 멈춘다 — 새 환자가 4였다면 부모 3이 더 급해서 첫 비교에서 바로 멈춥니다

1을 부르면맨 끝 환자 3이 빈 맨 위에 앉고, 아래 두 자식 중 더 급한 쪽과 바꾸며 내려갑니다. 결과는 [2, 5, 3, 9, 6, 8] 입니다.

코드는 부모와 견주며 올라가는 반복문이다

다음을 눌러 한 줄씩 넘기세요. 새 환자가 앉은 자리에서 부모와 견주고, 급하면 바꿔 올라갑니다.

다음을 눌러 한 줄씩 넘겨 보세요

x = 1

push.py
  1. 1def push(heap, x):
  2. 2 heap.append(x)
  3. 3 i = len(heap) - 1
  4. 4 while i > 0:
  5. 5 p = (i - 1) // 2
  6. 6 if heap[p] <= heap[i]:
  7. 7 break
  8. 8 heap[p], heap[i] = heap[i], heap[p]
  9. 9 i = p
  10. 10 return heap
0 / 14
  • p = (i - 1) // 2 — 부모 자리 번호
  • if heap[p] <= heap[i]: break — 부모가 같거나 더 급하면 멈춘다
  • heap[p], heap[i] = heap[i], heap[p] — 부모와 자리를 바꾼다
  • i = p — 올라간 자리에서 다시 견준다

파이썬에서는 이 반복문을 직접 쓰지 않습니다. heapq.heappush(heap, x) 한 줄이 같은 일을 합니다.

새 환자가 4 였다면 맨 아래 빈자리에서 몇 번 올라갈까요?

heapq 에서 헷갈리는 자리

  • 가장 작은 것이 먼저다 — heapq 는 최소 힙이다. 큰 것부터 꺼내려면 -x 로 넣고 꺼낸 뒤 다시 - 를 붙인다
  • 리스트는 정렬이 아니다 — 5, 3, 8, 1을 차례로 넣으면 [1, 3, 8, 5] 다. 맨 앞 heap[0] 만 가장 작다
  • 급한 정도와 이름을 같이 — heappush(h, (2, "복통")) 처럼 튜플로 넣는다. 앞 숫자가 같으면 뒤 값끼리 견주는데, 견줄 수 없는 값이면 TypeError 가 난다
  • 한 번에 만들 때 — 이미 있는 리스트는 heapify(arr) 한 번으로 N 에 비례해 만든다. 하나씩 넣으면 N log N 이다

문제에서 이 말이 보이면

매번 가장 작은(큰) 것K번째로 큰 수다익스트라 · 작업 스케줄

다음 장에서는 옆 칸끼리 바꿔 가며 줄을 세우는 버블 정렬을 봅니다.