ํž™ Heap

[2022.09.18] ๋ชจ๊ฐ์ฝ”์—์„œ ํž™์ด ๊ธฐ์–ต๋‚˜๋ƒ๊ณ  ๋ฌผ์—ˆ๋Š”๋ฐ '์ด์ง„ ํŠธ๋ฆฌ..'๋ผ๊ณ  ๋ฐ–์— ์„ค๋ช… ๋ชปํ•ด์„œ ์ž๊ทน ๋ฐ›์Œ.

ํž™ Heap

  • ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ์˜ ์ผ์ข…์œผ๋กœ ์šฐ์„ ์ˆœ์œ„ ํ๋ฅผ ์œ„ํ•˜์—ฌ ๋งŒ๋“ค์–ด์ง„ ์ž๋ฃŒ๊ตฌ์กฐ.
  • ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ํ‚ค ๊ฐ’์ด ์ž์‹ ๋…ธ๋“œ์˜ ํ‚ค ๊ฐ’๋ณด๋‹ค ํ•ญ์ƒ ํฐ(์ž‘์€) ์ด์ง„ ํŠธ๋ฆฌ๋ฅผ ๋งํ•œ๋‹ค.
  • ์ตœ๋Œ“๊ฐ’์ด๋‚˜ ์ตœ์†Ÿ๊ฐ’์„ ๋น ๋ฅด๊ฒŒ ์ฐพ์•„๋‚ด๋„๋ก ๋งŒ๋“ค์–ด์ง.
  • ์ผ์ข…์˜ ๋ฐ˜์ •๋ ฌ ์ƒํƒœ(๋Š์Šจํ•œ ์ •๋ ฌ ์ƒํƒœ)
  • ํฐ ๊ฐ’์ด ์ƒ์œ„ ๋ ˆ๋ฒจ์— ์žˆ๊ณ  ์ž‘์€ ๊ฐ’์ด ํ•˜์œ„ ๋ ˆ๋ฒจ์— ์žˆ๋‹ค๋Š” ์ •๋„
  • ํž™ ํŠธ๋ฆฌ์—์„œ๋Š” ์ค‘๋ณต๋œ ๊ฐ’์„ ํ—ˆ์šฉํ•œ๋‹ค. (์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์—์„œ๋Š” ์ค‘๋ณต๋œ ๊ฐ’์„ ํ—ˆ์šฉํ•˜์ง€ ์•Š๋Š”๋‹ค.)

์‹œ๊ฐ„๋ณต์žก๋„

  • ํƒ์ƒ‰ ๋ฐ ์—ฐ์‚ฐ ์‹œ๊ฐ„๋ณต์žก๋„ : $O(logn)$
    ์ด์ง„ํŠธ๋ฆฌ์˜ ๋ง๋‹จ ๋…ธ๋“œ์— ๊ฐ’์ด ์žˆ๋‹ค๋ฉด ๋†’์ด($h$)๋งŒํผ ํƒ์ƒ‰ํ•ด์•ผ ํ•จ.
    [์•ˆ๋“œ๋กœ์ด๋“œ](์•ˆ๋“œ๋กœ์ด๋“œ Android)

$$
์‹œ๊ฐ„๋ณต์žก๋„ = O(h)
$$
์™„์ „์ด์ง„ํŠธ๋ฆฌ์ด๋ฏ€๋กœ
$$
\begin{align}
(2^{(h-1)}-1) +1 \leq ;&n \leq 2^h-1\\log(n+1) \leq ;&h \leq logn + 1 \\\end{align}
$$
๋”ฐ๋ผ์„œ,
$$
์‹œ๊ฐ„๋ณต์žก๋„ = O(h) = O(logn+1) = O(logn)
$$

  • ํž™ ์ •๋ ฌ ์‹œ๊ฐ„๋ณต์žก๋„ : $O(nlogn)$
    n๊ฐœ์˜ ๋…ธ๋“œ๊ฐ€ ๊ฐ๊ฐ heapifyํ•ด์•ผ ํ•จ.

ํž™์˜ ์ข…๋ฅ˜

ํ™œ์šฉ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ ์œ ํ˜•

  1. N๋ฒˆ์งธ ํฐ ์ˆ˜/์ž‘์€ ์ˆ˜
  2. ์ค‘๊ฐ„๊ฐ’ ๊ตฌํ•˜๊ธฐ (Two heaps)
  3. k๊ฐœ์˜ ๋ฐฐ์—ด ํ•ฉ์น˜๊ธฐ
  4. ์ตœ์†Œ๊ฐ’

References

  • ์œ„ํ‚ค๋ฐฑ๊ณผ - ํž™ (์ž๋ฃŒ ๊ตฌ์กฐ) https://ko.wikipedia.org/wiki/ํž™_(์ž๋ฃŒ_๊ตฌ์กฐ)
  • [์ž๋ฃŒ๊ตฌ์กฐ] ํž™(heap)์ด๋ž€ https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
  • ๋ชจ๊ฐ์ฝ” '์žฌ๊ฐœ๋ฐœ์ฝ”๋”ฉ' annyeong๋‹˜ ๋ฐœํ‘œ์ž๋ฃŒ : <์•ˆํ‚ค์›Œ์š” - JS heap>