ํž™ ์ •๋ ฌ 1

[์ž๋ฃŒ๊ตฌ์กฐ] ํž™(heap) ์ž๋ฃŒ๊ตฌ์กฐ

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

CS 2021.09.30