Skip to content

Latest commit

ย 

History

History
43 lines (28 loc) ยท 1.26 KB

heap.md

File metadata and controls

43 lines (28 loc) ยท 1.26 KB

ํž™

ํž™(Heap)์€ ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์ด๋‚˜ ๊ฐ€์žฅ ํฐ ๊ฐ’์„ ๋น ๋ฅด๊ฒŒ ๊บผ๋‚ด๊ธฐ ์œ„ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค.

ํŒŒ์ด์ฌ์˜ heapq๋Š” ๊ธฐ๋ณธ์ ์œผ๋กœ ์ตœ์†Œ ํž™(min-heap)์ž…๋‹ˆ๋‹ค.

ํ•ต์‹ฌ ์ƒ๊ฐ

  • ์ „์ฒด๋ฅผ ์ •๋ ฌํ•˜์ง€ ์•Š์•„๋„, ์ตœ์†Ÿ๊ฐ’์„ ๋น ๋ฅด๊ฒŒ ๊บผ๋‚ผ ์ˆ˜ ์žˆ๋‹ค.
  • ๊ฐ’์ด ๊ณ„์† ๋“ค์–ด์˜ค๊ณ  ๋น ์ง€๋Š” ์ƒํ™ฉ์—์„œ ์œ ์šฉํ•˜๋‹ค.

์–ธ์ œ ๋– ์˜ฌ๋ฆฌ๋ฉด ์ข‹์€๊ฐ€

  • ํ˜„์žฌ ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’ ๋˜๋Š” ๊ฐ€์žฅ ํฐ ๊ฐ’์„ ๋ฐ˜๋ณตํ•ด์„œ ๊บผ๋‚ด์•ผ ํ•  ๋•Œ
  • ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๊ฐ€์žฅ ๋†’์€ ์ž‘์—…์„ ๊ณ„์† ์ฒ˜๋ฆฌํ•ด์•ผ ํ•  ๋•Œ
  • ์ •๋ ฌ ์ „์ฒด๋ณด๋‹ค "๋งจ ์•ž ์›์†Œ"๊ฐ€ ๋” ์ค‘์š”ํ•  ๋•Œ

ํŒŒ์ด์ฌ ๊ตฌํ˜„ ํฌ์ธํŠธ

import heapq

heap = []  # -> ๋นˆ ์ตœ์†Œ ํž™
heapq.heappush(heap, x)  # -> ๊ฐ’ ์ถ”๊ฐ€
v = heapq.heappop(heap)  # -> ์ตœ์†Ÿ๊ฐ’ ๋ฐ˜ํ™˜

์ตœ๋Œ€ ํž™์ฒ˜๋Ÿผ ์“ฐ๊ณ  ์‹ถ์œผ๋ฉด ๋ถ€ํ˜ธ๋ฅผ ๋ฐ”๊ฟ‰๋‹ˆ๋‹ค.

heapq.heappush(heap, -x)  # -> ์ตœ๋Œ€ ํž™์ฒ˜๋Ÿผ ์‚ฌ์šฉ
v = -heapq.heappop(heap)  # -> ์›๋ž˜ ๊ฐ’์œผ๋กœ ๋ณต์›

์‹ค์ˆ˜ํ•˜๊ธฐ ์‰ฌ์šด ๊ฒƒ

  • heap[0]์ด ์ตœ์†Ÿ๊ฐ’์ด๋ผ๋Š” ์ ์„ ์žŠ๋Š” ๊ฒƒ
  • ์ตœ๋Œ€ ํž™์ด ํ•„์š”ํ•  ๋•Œ ๋ถ€ํ˜ธ ๋ฐ˜์ „์„ ๋นผ๋จน๋Š” ๊ฒƒ
  • ์ •๋ ฌ ํ•œ ๋ฒˆ์ด๋ฉด ๋˜๋Š” ๋ฌธ์ œ์— ๊ตณ์ด ํž™์„ ์“ฐ๋Š” ๊ฒƒ

๊ธฐ์–ตํ•  ๋ฌธ์žฅ

  • "์ „์ฒด ์ •๋ ฌ"์ด ์•„๋‹ˆ๋ผ "๊ฐ€์žฅ ์ž‘์€ ๊ฐ’ ๋ฐ˜๋ณต ์ถ”์ถœ"์ด๋ฉด ํž™์„ ๋จผ์ € ๋– ์˜ฌ๋ฆฐ๋‹ค.