๋ฐ˜์‘ํ˜•

ํž™์˜ ํŠน์ง•


์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ์ฐพ์„ ๋•Œ ๋„๋ฆฌ ์‚ฌ์šฉํ•˜๋Š” ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€, ํƒ์ƒ‰ ํ์˜ ์ž๋ฃŒ๊ตฌ์กฐ๊ฐ€ ์ „์ฒด ์„ฑ๋Šฅ์— ๊ฒฐ์ •์ ์ธ ์˜ํ–ฅ์„ ๋ฏธ์นœ๋‹ค. ๋•Œ๋ฌธ์— ์ถ”๊ฐ€/์‚ญ์ œ๋ฅผ ๋น ๋ฅด๊ฒŒ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์žˆ๋Š” ์šฐ์„ ์ˆœ์œ„ ํ๋ฅผ ์ฃผ๋กœ ์‚ฌ์šฉํ•œ๋‹ค.

 

์šฐ์„ ์ˆœ์œ„ ํ๋Š” ์ผ๋ฐ˜ ํ์™€ ๋น„์Šทํ•˜์ง€๋งŒ, ๊ฐ ์š”์†Œ๊ฐ€ ์šฐ์„ ์ˆœ์œ„๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ์œผ๋ฉฐ, ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๋†’์€ ์š”์†Œ๊ฐ€ ๋จผ์ € ์ถœ๋ ฅ๋œ๋‹ค๋Š” ์ ์ด ๋‹ค๋ฅด๋‹ค. ์šฐ์„ ์ˆœ์œ„ ํ๋Š” ํฌ๊ฒŒ ๋ฐฐ์—ด, ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ, ํž™ ์ด๋ ‡๊ฒŒ ์„ธ ๊ฐ€์ง€ ๋ฐฉ๋ฒ•์œผ๋กœ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค. ๊ทธ์ค‘ ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ ๊ตฌ์กฐ๋ฅผ ๊ฐ–๋Š” ํž™์œผ๋กœ ๊ตฌํ˜„ํ•˜๋ฉด ์ถ”๊ฐ€/์ œ๊ฑฐ์˜ ํšจ์œจ์„ฑ์ด ํฌ๊ฒŒ ํ–ฅ์ƒ๋œ๋‹ค.

 

๊ตฌํ˜„ ๋ฐฉ๋ฒ• ์‚ฝ์ž… ์‚ญ์ œ
์ˆœ์„œ ์—†๋Š” ๋ฐฐ์—ด O(1) O(n)
์ˆœ์„œ ์—†๋Š” ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ O(1) O(n)
์ •๋ ฌ๋œ ๋ฐฐ์—ด O(n) O(1)
์ •๋ ฌ๋œ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ O(n) O(1)
ํž™ O(log n) O(log n)

 

์ด์ง„ ํŠธ๋ฆฌ๋Š” ๊ฐ ๋ถ€๋ชจ ๋…ธ๋“œ๊ฐ€ ์™ผ์ชฝ/์˜ค๋ฅธ์ชฝ ์ตœ๋Œ€ 2๊ฐœ์˜ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋Š” ๊ตฌ์กฐ๋ฅผ ๊ฐ€๋ฆฌํ‚จ๋‹ค. ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ๋Š” ๋งˆ์ง€๋ง‰ ๋ ˆ๋ฒจ์„ ์ œ์™ธํ•œ ๋ชจ๋“  ๋ ˆ๋ฒจ์„ ์™„์ „ํžˆ ์ฑ„์›Œ์ง„ ์ƒํƒœ๋กœ ์œ ์ง€ํ•ด์•ผ ํ•œ๋‹ค. ๋•Œ๋ฌธ์— ์ž์‹ ๋…ธ๋“œ๋ฅผ ์ถ”๊ฐ€ํ•  ๋• ์™ผ์ชฝ๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ์ฑ„์›Œ์•ผ ํ•œ๋‹ค. ์•„๋ž˜ ์ด๋ฏธ์ง€ ์™ผ์ชฝ์— ์žˆ๋Š” ํŠธ๋ฆฌ๋Š” 31๋ฒˆ ๋…ธ๋“œ์˜ ์ž์‹์„ ์˜ค๋ฅธ์ชฝ๋ถ€ํ„ฐ ์ฑ„์› ๊ธฐ ๋•Œ๋ฌธ์— ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ๊ฐ€ ์•„๋‹ˆ๋‹ค.

 

 

ํž™์€ ํฌ๊ฒŒ ์ตœ๋Œ€ ํž™(Max Heap), ์ตœ์†Œ ํž™(Min Heap)์œผ๋กœ ๋ถ„๋ฅ˜๋œ๋‹ค. ์ตœ๋Œ€ ํž™์€ ๋ถ€๋ชจ ๋…ธ๋“œ๊ฐ€ ํ•ญ์ƒ ์ž์‹ ๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , ์ตœ์†Œ ํž™์€ ๋ถ€๋ชจ ๋…ธ๋“œ๊ฐ€ ํ•ญ์ƒ ์ž์‹๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™๋‹ค. ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๊ฑฐ๋ฆฌ ๊ฐ’์ด ๋‚ฎ์€ ๋…ธ๋“œ์— ๋†’์€ ์šฐ์„ ์ˆœ์œ„๋ฅผ ๋ถ€์—ฌํ•˜๋ฏ€๋กœ, ๋ฃจํŠธ ๋…ธ๋“œ๊ฐ€ ๊ฐ€์žฅ ์งง์€ ๊ฑฐ๋ฆฌ ๊ฐ’(์šฐ์„ ์ˆœ์œ„๊ฐ€ ๋†’์€)์„ ๊ฐ–๋Š” ์ตœ์†Œ ํž™์„ ์‚ฌ์šฉํ•˜๋Š” ๊ฒƒ์ด ์ ์ ˆํ•˜๋‹ค.

 

 

 

๋ฐฐ์—ด๋กœ ํ‘œํ˜„ํ•˜๋Š” ์ตœ์†Œ ํž™


 

์œ„์—์„œ ์‚ดํŽด๋ณธ ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ ํŠน์„ฑ์„ ์ด์šฉํ•˜๋ฉด ๊ฐ ๋…ธ๋“œ์˜ ์ธ๋ฑ์Šค๋ฅผ ์•„๋ž˜ ๊ณต์‹์œผ๋กœ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ๋‹ค.

 

  • ์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ ์ธ๋ฑ์Šค : ๋ถ€๋ชจ ๋…ธ๋“œ ์ธ๋ฑ์Šค × 2 + 1
  • ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ ์ธ๋ฑ์Šค : ๋ถ€๋ชจ ๋…ธ๋“œ ์ธ๋ฑ์Šค × 2 + 2
  • ๋ถ€๋ชจ ๋…ธ๋“œ ์ธ๋ฑ์Šค : (์ž์‹ ๋…ธ๋“œ ์ธ๋ฑ์Šค - 1) / 2

 

์˜ˆ๋ฅผ๋“ค์–ด ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ์ธ๋ฑ์Šค๊ฐ€ 2๋ผ๋ฉด ์™ผ์ชฝ ์ž์‹ ์ธ๋ฑ์Šค๋Š” 5, ์˜ค๋ฅธ์ชฝ ์ž์‹ ์ธ๋ฑ์Šค๋Š” 6์ด ๋œ๋‹ค. ์ด์ฒ˜๋Ÿผ ํ•œ ๋…ธ๋“œ์˜ ์ธ๋ฑ์Šค๋งŒ ์•Œ๋ฉด ํ•ด๋‹น ๋…ธ๋“œ์˜ ๋ถ€๋ชจ/์ž์‹ ๋…ธ๋“œ์˜ ์ธ๋ฑ์Šค๋„ ํ™•์ธํ•  ์ˆ˜ ์žˆ์–ด์„œ ๋ฐฐ์—ด ๊ตฌ์กฐ๋กœ๋„ ํŠธ๋ฆฌ๋ฅผ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.

 

 

Enqueue


๋…ธ๋“œ ์ถ”๊ฐ€๋Š” ์ตœ์†Œ ํž™ ์†์„ฑ(๋ถ€๋ชจ ๋…ธ๋“œ ≤ ์ž์‹ ๋…ธ๋“œ)์„ ๋งŒ์กฑํ•  ๋•Œ๊นŒ์ง€ ๋ถ€๋ชจ ๋…ธ๋“œ์™€ ๋น„๊ตํ•˜๋ฉฐ ์œ„์น˜๋ฅผ ๊ตํ™˜ํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ์ด๋ค„์ง„๋‹ค. ๋…ธ๋“œ ์œ„์น˜๋ฅผ ๊ตํ™˜ํ•˜๋Š” ๊ณผ์ •์€ heapify-up์ด๋ผ๊ณ  ๋ถ€๋ฅธ๋‹ค. heapify-up์€ ์ตœ์•…์˜ ๊ฒฝ์šฐ ํŠธ๋ฆฌ ๋†’์ด ๋งŒํผ ๋ฐ˜๋ณต๋˜๊ณ , ํŠธ๋ฆฌ ๋†’์ด๋Š” $\log_{2}V$์ด๋ฏ€๋กœ ๋…ธ๋“œ ์ถ”๊ฐ€์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„ ์—ญ์‹œ $\log_{2}V$๋ฅผ ๊ฐ–๋Š”๋‹ค.

 

  1. ์ƒˆ๋กœ์šด ๋…ธ๋“œ๋ฅผ ํž™์˜ ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰์— ์ถ”๊ฐ€ํ•œ๋‹ค — heap.push(node)
  2. ์ƒˆ๋กœ ์ถ”๊ฐ€ํ•œ ๋…ธ๋“œ๋ฅผ ๋ถ€๋ชจ ๋…ธ๋“œ์™€ ๋น„๊ตํ•˜์—ฌ ๋” ์ž‘๋‹ค๋ฉด ์œ„์น˜๋ฅผ ๋ฐ”๊พผ๋‹ค — heapify-up
  3. ์ƒˆ๋กœ ์ถ”๊ฐ€ํ•œ ๋…ธ๋“œ๊ฐ€ ๋ถ€๋ชจ ๋…ธ๋“œ๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜, ๋ฃจํŠธ์— ๋„๋‹ฌํ•  ๋•Œ๊นŒ์ง€ ์ด ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•œ๋‹ค

 

๐Ÿ’ก ํŠธ๋ฆฌ์—์„œ ๋†’์ด๋Š” ๋ฃจํŠธ ๋…ธ๋“œ(๊นŠ์ด 0)์—์„œ ๋ฆฌํ”„ ๋…ธ๋“œ๊นŒ์ง€์˜ ๊ฑฐ๋ฆฌ๋ฅผ ์˜๋ฏธํ•œ๋‹ค. ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ์—์„œ ๊ฐ ๋ ˆ๋ฒจ์˜ ๋…ธ๋“œ ์ˆ˜๋Š” ์ด์ „ ๋ ˆ๋ฒจ ๋…ธ๋“œ ์ˆ˜์˜ 2๋ฐฐ๋กœ ์ฆ๊ฐ€ํ•œ๋‹ค. ๋”ฐ๋ผ์„œ ๋†’์ด๊ฐ€ $h$์ธ ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ๋Š” ์ตœ์†Œ $2^{h}$์—์„œ ์ตœ๋Œ€ $2^{h+1}-1$๊ฐœ์˜ ๋…ธ๋“œ๋ฅผ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ๋†’์ด๊ฐ€ 2์ธ ํŠธ๋ฆฌ๋Š” ์ตœ๋Œ€ $2^{2+1}-1=7$๊ฐœ์˜ ๋…ธ๋“œ๋ฅผ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋‹ค. ์ฆ‰, $V$๊ฐœ์˜ ๋…ธ๋“œ๋ฅผ ๊ฐ€์ง„ ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ์˜ ๋†’์ด๋Š” $\log_{2}V$๋กœ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ๋‹ค.

 

 

 

Dequeue


๋…ธ๋“œ ์ œ๊ฑฐ ์—ญ์‹œ ํž™ ์†์„ฑ์„ ๋งŒ์กฑํ•  ๋•Œ๊นŒ์ง€ ์ž์‹ ๋…ธ๋“œ์™€ ๋น„๊ตํ•˜๋ฉฐ ์œ„์น˜๋ฅผ ๊ตํ™˜ํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ์ด๋ค„์ง„๋‹ค. ๋…ธ๋“œ ์œ„์น˜๋ฅผ ๊ตํ™˜ํ•˜๋Š” ๊ณผ์ •์€ heapify-down์ด๋ผ๊ณ  ๋ถ€๋ฅธ๋‹ค. heapify-down์€ heapify-up๊ณผ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ์ตœ์•…์˜ ๊ฒฝ์šฐ ํŠธ๋ฆฌ ๋†’์ด ๋งŒํผ ๋ฐ˜๋ณต๋˜๊ณ , ํŠธ๋ฆฌ ๋†’์ด๋Š” $\log_{2}V$์ด๋ฏ€๋กœ ๋…ธ๋“œ ์ œ๊ฑฐ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” $\log_{2}V$๋ฅผ ๊ฐ–๋Š”๋‹ค.

 

  1. ํž™์˜ ๋ฃจํŠธ ๋…ธ๋“œ๋ฅผ ์ œ๊ฑฐํ•˜๊ณ , ๋งˆ์ง€๋ง‰ ๋…ธ๋“œ๋ฅผ ๋ฃจํŠธ๋กœ ์ด๋™ ์‹œํ‚จ๋‹ค — heap[0]=heap.pop()
  2. ๋ฃจํŠธ๋กœ ์ด๋™ํ•œ ๋…ธ๋“œ๋ณด๋‹ค ์ž์‹ ๋…ธ๋“œ๊ฐ€ ๋” ์ž‘๋‹ค๋ฉด ์œ„์น˜๋ฅผ ๋ฐ”๊พผ๋‹ค — heapify-down
  3. ๋ฃจํŠธ๋กœ ์ด๋™ํ•œ ๋…ธ๋“œ๊ฐ€ ์ž์‹ ๋…ธ๋“œ๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜, ๋ฆฌํ”„ ๋…ธ๋“œ์— ๋„๋‹ฌํ•  ๋•Œ๊นŒ์ง€ ์ด ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•œ๋‹ค

 

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

 

 

 

์ฝ”๋“œ ๊ตฌํ˜„


๋”๋ณด๊ธฐ
class MinHeap {
  constructor() {
    this.heap = [];
  }

  // ์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ ์ธ๋ฑ์Šค = ๋ถ€๋ชจ ๋…ธ๋“œ ์ธ๋ฑ์Šค * 2 + 1
  getLeftChildIndex(parentIdx) {
    return 2 * parentIdx + 1;
  }

  // ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ ์ธ๋ฑ์Šค = ๋ถ€๋ชจ ๋…ธ๋“œ ์ธ๋ฑ์Šค * 2 + 2
  getRightChildIndex(parentIdx) {
    return 2 * parentIdx + 2;
  }

  // ๋ถ€๋ชจ ๋…ธ๋“œ ์ธ๋ฑ์Šค = (์ž์‹ ๋…ธ๋“œ ์ธ๋ฑ์Šค - 1) / 2
  getParentIndex(childIdx) {
    return Math.floor((childIdx - 1) / 2);
  }

  // ์ฃผ์–ด์ง„ ์ธ๋ฑ์Šค์— ์œ„์น˜ํ•œ (๋ถ€๋ชจ)๋…ธ๋“œ์— ์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์žˆ๋Š”์ง€ ํ™•์ธ
  // ์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ์˜ ์ธ๋ฑ์Šค๊ฐ€ ์ „์ฒด ๋…ธ๋“œ ๊ฐฏ์ˆ˜๋ณด๋‹ค ์ž‘์„ ๊ฒฝ์šฐ์—๋งŒ ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์กด์žฌํ•œ๋‹ค๊ณ  ๊ฐ„์ฃผ
  hasLeftChild(idx) {
    return this.getLeftChildIndex(idx) < this.heap.length;
  }

  // Checks if a right child exists for the given idx
  hasRightChild(idx) {
    return this.getRightChildIndex(idx) < this.heap.length;
  }

  // Checks if a parent exists for the given idx
  hasParent(idx) {
    return this.getParentIndex(idx) >= 0;
  }

  // Retrieves the left child's value for the given idx
  leftChild(idx) {
    return this.heap[this.getLeftChildIndex(idx)];
  }

  // Retrieves the right child's value for the given idx
  rightChild(idx) {
    return this.heap[this.getRightChildIndex(idx)];
  }

  // Retrieves the parent's value for the given idx
  parent(idx) {
    return this.heap[this.getParentIndex(idx)];
  }

  // Swaps the elements at the two given indexes
  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

  // Returns the minimum element without removing it
  peek() {
    return this.heap.length === 0 ? null : this.heap[0];
  }

  // Removes and returns the minimum element from the heap
  remove() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();
    const rootNode = this.heap[0];
    this.heap[0] = this.heap.pop(); // ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰์— ์žˆ๋Š” ๋…ธ๋“œ๋ฅผ ๋ฃจํŠธ ๋…ธ๋“œ๋กœ ๋งŒ๋“ค๊ณ 
    this.heapifyDown(); // ๋‹ค์‹œ Min Heap ์†์„ฑ์„ ๊ฐ–๋„๋ก ์กฐ์ •
    return rootNode;
  }

  // Adds a new element to the heap
  add(priority, value) {
    this.heap.push({ priority, value: !value ? priority : value });
    this.heapifyUp();
  }

  // Moves the last element up to its correct position in the heap
  heapifyUp() {
    let idx = this.heap.length - 1;

    // ๋ถ€๋ชจ ๋…ธ๋“œ๊ฐ€ ์—†์œผ๋ฉด ์˜ต์…”๋„ ์ฒด์ด๋‹์œผ๋กœ ์ธํ•ด undefined ๋ฐ˜ํ™˜ -> while๋ฌธ ์กฐ๊ฑด ํ†ต๊ณผ X
    while (this.parent(idx)?.priority > this.heap[idx].priority) {
      const parentIdx = this.getParentIndex(idx);

      this.swap(parentIdx, idx);
      idx = parentIdx;
    }
  }

  // Moves the root element down to its correct position in the heap
  heapifyDown() {
    let idx = 0;

    while (this.hasLeftChild(idx)) {
      let smallestIdx = this.getLeftChildIndex(idx);
      // ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์—†์œผ๋ฉด ์˜ต์…”๋„ ์ฒด์ด๋‹์œผ๋กœ ์ธํ•ด undefined ๋ฐ˜ํ™˜ -> while๋ฌธ ์กฐ๊ฑด ํ†ต๊ณผ X
      if (this.rightChild(idx)?.priority < this.leftChild(idx).priority) {
        // ์™ผ์ชฝ/์˜ค๋ฅธ์ชฝ ์ž์‹ ์ค‘ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๋” ๋†’์€(priority ๊ฐ’์ด ๋” ์ž‘์€) ๋…ธ๋“œ ์„ ํƒ
        smallestIdx = this.getRightChildIndex(idx);
      }
      // ๋ถ€๋ชจ ๋…ธ๋“œ๊ฐ€ ์ž์‹ ๋…ธ๋“œ๋ณด๋‹ค ๋” ์ž‘์œผ๋ฉด heapifyDown ์ค‘์ง€
      if (this.heap[idx].priority <= this.heap[smallestIdx].priority) break;

      this.swap(idx, smallestIdx);
      idx = smallestIdx;
    }
  }

  // Prints all elements in the heap
  printHeap(property = 'priority') {
    console.log(this.heap.map((element) => element[property]).join(' '));
  }
}

export default MinHeap;

 

๊ธฐ๋ณธ ๊ตฌ์กฐ

๋…ธ๋“œ์˜ ์ธ๋ฑ์Šค๋ฅผ ๊ณ„์‚ฐํ•˜๋Š” ๋กœ์ง ๋“ฑ์€ ์ž์ฃผ ์‚ฌ์šฉํ•˜๋ฏ€๋กœ ๋ฉ”์„œ๋“œ๋กœ ๋ฏธ๋ฆฌ ๊ตฌํ˜„ํ•ด๋‘”๋‹ค. has*Child ๊ฐ™์€ ๋ฉ”์„œ๋“œ๋Š” ์ฃผ์–ด์ง„ ์ธ๋ฑ์Šค์— ์œ„์น˜ํ•œ ๋…ธ๋“œ์— ์™ผ์ชฝ/์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์žˆ๋Š”์ง€ ํ™•์ธํ•œ๋‹ค.

 

์ฃผ์˜ํ•  ์ ์€ ๊ณ„์‚ฐํ•œ ์ž์‹ ๋…ธ๋“œ์˜ ์ธ๋ฑ์Šค๊ฐ€ ์ „์ฒด ๋…ธ๋“œ ๊ฐฏ์ˆ˜(heap.length)๋ณด๋‹ค ์ž‘์„ ๊ฒฝ์šฐ์—๋งŒ ์กด์žฌํ•œ๋‹ค๊ณ  ๊ฐ„์ฃผํ•ด์•ผ ํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ํŠธ๋ฆฌ์— ๋ฃจํŠธ ๋…ธ๋“œ 1๊ฐœ๋ฐ–์— ์—†๋‹ค๋ฉด ๋ฐฐ์—ด ๊ธธ์ด๋Š” 1์ด ๋œ๋‹ค. ์ด๋•Œ ๋ฃจํŠธ ๋…ธ๋“œ์— ๋Œ€ํ•œ ์™ผ์ชฝ/์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ์˜ ์ธ๋ฑ์Šค๋Š” ๊ฐ๊ฐ 1, 2๋กœ ๋ฐฐ์—ด ๊ธธ์ด์™€ ๊ฐ™๊ฑฐ๋‚˜ ํฌ๊ธฐ ๋•Œ๋ฌธ์— ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์—†๋Š” ๊ฑธ๋กœ ์ฒ˜๋ฆฌํ•ด์•ผ ํ•œ๋‹ค.

class MinHeap {
  constructor() {
    this.heap = []; // [{ priority: number, value: any }, ...]
  }

  // ์œ ํ‹ธ๋ฆฌํ‹ฐ ํ•จ์ˆ˜
  getLeftChildIndex(parentIdx) {
    return 2 * parentIdx + 1;
  }
  getRightChildIndex(parentIdx) {
    return 2 * parentIdx + 2;
  }
  getParentIndex(childIdx) {
    return Math.floor((childIdx - 1) / 2);
  }

  hasLeftChild(idx) {
    return this.getLeftChildIndex(idx) < this.heap.length;
  }
  hasRightChild(idx) {
    return this.getRightChildIndex(idx) < this.heap.length;
  }
  hasParent(idx) {
    return this.getParentIndex(idx) >= 0;
  }

  leftChild(idx) {
    return this.heap[this.getLeftChildIndex(idx)];
  }
  rightChild(idx) {
    return this.heap[this.getRightChildIndex(idx)];
  }
  parent(idx) {
    return this.heap[this.getParentIndex(idx)];
  }

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

  // ...
}

 

์ถ”๊ฐ€ (Enqueue)

์ƒˆ๋กœ์šด ๋…ธ๋“œ๋ฅผ ๋ฐ›์•„ heap ๋ฐฐ์—ด ๊ฐ€์žฅ ๋์— ์ถ”๊ฐ€ํ•œ๋‹ค. ๊ทธ ํ›„ heapifyUp ๋ฉ”์„œ๋“œ๋ฅผ ํ˜ธ์ถœํ•ด์„œ ํž™ ์†์„ฑ์„ ๋งŒ์กฑํ•  ๋•Œ๊นŒ์ง€ ๋ถ€๋ชจ ๋…ธ๋“œ์™€ ๋น„๊ตํ•˜๋ฉฐ ์œ„์น˜๋ฅผ ๊ตํ™˜ํ•œ๋‹ค.

class MinHeap {
  // ...

  add(priority, value) {
    this.heap.push({ priority, value: !value ? priority : value });
    this.heapifyUp();
  }

  heapifyUp() {
    let idx = this.heap.length - 1;

    // ๋ถ€๋ชจ ๋…ธ๋“œ๊ฐ€ ์—†์œผ๋ฉด ์˜ต์…”๋„ ์ฒด์ด๋‹์œผ๋กœ ์ธํ•ด undefined ๋ฐ˜ํ™˜ -> while๋ฌธ ์กฐ๊ฑด ํ†ต๊ณผ X
    while (this.parent(idx)?.priority > this.heap[idx].priority) {
      const parentIdx = this.getParentIndex(idx);
      this.swap(parentIdx, idx);
      idx = parentIdx;
    }
  }
}

 

์‚ญ์ œ (Dequeue)

remove ๋ฉ”์„œ๋“œ๋ฅผ ํ˜ธ์ถœํ•˜๋ฉด ํŠธ๋ฆฌ์—์„œ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๊ฐ€์žฅ ๋†’์€ ๋ฃจํŠธ ๋…ธ๋“œ๋ฅผ ์ž„์‹œ ์ €์žฅํ•˜๊ณ , heap ๋ฐฐ์—ด ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰ ๋…ธ๋“œ๋ฅผ ๋ฃจํŠธ ๋…ธ๋“œ๋กœ ๋ณ€๊ฒฝํ•œ๋‹ค. ๊ทธ ํ›„ ๋‹ค์‹œ ํž™ ์†์„ฑ์„ ์œ ์ง€ํ•˜๊ธฐ ์œ„ํ•ด heapifyDown ๋ฉ”์„œ๋“œ๋ฅผ ํ˜ธ์ถœํ•œ ํ›„ ์ž„์‹œ ์ €์žฅํ–ˆ๋˜ ๋ฃจํŠธ ๋…ธ๋“œ๋ฅผ ๋ฐ˜ํ™˜ํ•œ๋‹ค. heapifyDown์€ ๋…ธ๋“œ ์ถ”๊ฐ€์™€ ๋ฐ˜๋Œ€๋กœ ์ž์‹ ๋…ธ๋“œ์™€ ๋น„๊ตํ•˜๋ฉฐ ์œ„์น˜๋ฅผ ๊ตํ™˜ํ•œ๋‹ค. ์ž์‹ ๋…ธ๋“œ๊ฐ€ 2๊ฐœ ์žˆ๋‹ค๋ฉด ๋‘˜ ์ค‘ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๋†’์€(priority ๊ฐ’์ด ์ž‘์€) ๋…ธ๋“œ๋ฅผ ์„ ํƒํ•ด์„œ ๋น„๊ตํ•œ๋‹ค.

class MinHeap {
  // ...

  remove() {
    if (this.heap.length === 0) return null; // ํž™์— ๋…ธ๋“œ๊ฐ€ ์—†์„ ๋•Œ
    if (this.heap.length === 1) return this.heap.pop(); // ํž™์— ๋ฃจํŠธ ๋…ธ๋“œ๋งŒ ์žˆ์„ ๋•Œ
    const rootNode = this.heap[0]; // ํ˜„์žฌ ๋ฃจํŠธ ๋…ธ๋“œ ์ž„์‹œ ์ €์žฅ
    this.heap[0] = this.heap.pop(); // ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰์— ์žˆ๋Š” ๋…ธ๋“œ๋ฅผ ๋ฃจํŠธ ๋…ธ๋“œ๋กœ ๋งŒ๋“ค๊ณ 
    this.heapifyDown(); // ๋‹ค์‹œ Min Heap ์†์„ฑ์„ ๊ฐ–๋„๋ก ์กฐ์ •
    return rootNode; // ์ž„์‹œ ์ €์žฅํ•œ ๋ฃจํŠธ ๋…ธ๋“œ ๋ฐ˜ํ™˜
  }

  heapifyDown() {
    let idx = 0;

    while (this.hasLeftChild(idx)) {
      let smallestIdx = this.getLeftChildIndex(idx);
      // ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์—†์œผ๋ฉด ์˜ต์…”๋„ ์ฒด์ด๋‹์œผ๋กœ ์ธํ•ด undefined ๋ฐ˜ํ™˜ -> while๋ฌธ ์กฐ๊ฑด ํ†ต๊ณผ X
      if (this.rightChild(idx)?.priority < this.leftChild(idx).priority) {
        // ์™ผ์ชฝ/์˜ค๋ฅธ์ชฝ ์ž์‹ ์ค‘ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๋” ๋†’์€(priority ๊ฐ’์ด ๋” ์ž‘์€) ๋…ธ๋“œ ์„ ํƒ
        smallestIdx = this.getRightChildIndex(idx);
      }
      // ๋ถ€๋ชจ ๋…ธ๋“œ๊ฐ€ ์ž์‹ ๋…ธ๋“œ๋ณด๋‹ค ๋” ์ž‘์œผ๋ฉด heapifyDown ์ค‘์ง€
      if (this.heap[idx].priority <= this.heap[smallestIdx].priority) break;

      this.swap(idx, smallestIdx);
      idx = smallestIdx;
    }
  }
}

 

๋””๋ฒ„๊น… ๋ฉ”์„œ๋“œ

์ตœ์†Œ ํž™์„ ์‚ฌ์šฉํ•  ๋•Œ ์ž์ฃผ ์‚ฌ์šฉํ•˜๋Š” ๋””๋ฒ„๊น…์šฉ ๋ฉ”์„œ๋“œ๋ฅผ ์ถ”๊ฐ€ํ•œ๋‹ค. ์ฝ๊ธฐ์ „์šฉ ๋ฉ”์„œ๋“œ peek์€ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๊ฐ€์žฅ ๋†’์€ ๋…ธ๋“œ ์ •๋ณด๋ฅผ ๋ฐ˜ํ™˜ํ•œ๋‹ค. ์ตœ์†Œ ํž™์—์„  ํ•ญ์ƒ ๋ฃจํŠธ๋…ธ๋“œ์˜ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๊ฐ€์žฅ ๋†’์œผ๋ฏ€๋กœ $O(1)$ ์ƒ์ˆ˜ ์‹œ๊ฐ„์œผ๋กœ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์žˆ๋‹ค.

class MinHeap {
  // ...

  peek() {
    return this.heap.length === 0 ? null : this.heap[0];
  }

  printHeap(property = 'priority') {
    console.log(this.heap.map((element) => element[property]).join(' '));
  }
}

export default MinHeap;

 

  • peek: ํž™ ์ƒํƒœ ๋ณ€๊ฒฝ ์—†์ด ํ˜„์žฌ ๋ฃจํŠธ ๋…ธ๋“œ(๋‹ค์Œ์— ๋ฐ˜ํ™˜๋  ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๊ฐ€์žฅ ๋†’์€ ๋…ธ๋“œ)์˜ ์ •๋ณด๋งŒ ๋ฐ˜ํ™˜
  • printHeap : ํ˜„์žฌ ํž™์— ์ €์žฅ๋œ ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ์ฝ˜์†”๋กœ ์ถœ๋ ฅ

 

์šฐ์„ ์ˆœ์œ„ ํ

MinHeap ํด๋ž˜์Šค๋ฅผ ํ™•์žฅํ•ด์„œ ์šฐ์„ ์ˆœ์œ„ ํ ๊ธฐ๋Šฅ์— ํŠนํ™”๋œ ์—ฌ๋Ÿฌ ๋ฉ”์„œ๋“œ๋ฅผ ์ถ”๊ฐ€ํ•œ๋‹ค. ์ฐธ๊ณ ๋กœ ์„œ๋ธŒ ํด๋ž˜์Šค์˜ ์ƒ์„ฑ์ž(constructor)๋ฅผ ์ƒ๋žตํ•˜๋ฉด ๋‚ด๋ถ€์ ์œผ๋กœ ๋ถ€๋ชจ ํด๋ž˜์Šค์˜ ์ƒ์„ฑ์ž ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•œ๋‹ค(super()). ๋ถ€๋ชจ/์„œ๋ธŒ ํด๋ž˜์Šค ์ƒ์„ฑ์ž๊ฐ€ ๋ฐ›๋Š” ํŒŒ๋ผ๋ฏธํ„ฐ๊ฐ€ ๋™์ผํ•˜๊ฑฐ๋‚˜ ์—†๋‹ค๋ฉด ์ƒ๋žตํ•ด๋„ ๋ฌด๋ฐฉํ•˜๋‹ค.

class PriorityQueue extends MinHeap {
  get size() {
    return this.heap.length;
  }
  get isEmpty() {
    return this.size === 0;
  }

  enqueue(priority, value) {
    this.add(priority, value);
  }
  dequeue() {
    return this.remove();
  }

  clear() {
    this.heap = [];
  }
  contains(value) {
    return this.heap.some((element) => element.value === value);
  }

  // ...
}

 

 

๋ ˆํผ๋Ÿฐ์Šค


JavaScript๋กœ Heap | Priority Queue ๊ตฌํ˜„ํ•˜๊ธฐ | jun-choi-4928

Min Heap in JavaScript | GeeksforGeeks

 


๊ธ€ ์ˆ˜์ •์‚ฌํ•ญ์€ ๋…ธ์…˜ ํŽ˜์ด์ง€์— ๊ฐ€์žฅ ๋น ๋ฅด๊ฒŒ ๋ฐ˜์˜๋ฉ๋‹ˆ๋‹ค. ๋งํฌ๋ฅผ ์ฐธ๊ณ ํ•ด ์ฃผ์„ธ์š”
๋ฐ˜์‘ํ˜•