Data Structure

[Data Structure] Priority_queue(์šฐ์„ ์ˆœ์œ„ ํ) ์‚ฌ์šฉ๋ฒ•

An effort will never betray ๐Ÿ˜Ž 2020. 3. 16. 20:55
๋ฐ˜์‘ํ˜•
  • C++ STL์ค‘ ํ•˜๋‚˜์ธ Priority_queue์— ๋Œ€ํ•œ ์„ค๋ช…์ž…๋‹ˆ๋‹ค.

Priority queue ์ด๋ž€?

  • priority queue๋Š” Compare(์šฐ์„ ์ˆœ์œ„)์— ๋งž๊ฒŒ ์„ค๊ณ„๋œ container ์ž…๋‹ˆ๋‹ค.
  • priority queue๋Š” heap๊ณผ ์œ ์‚ฌํ•ฉ๋‹ˆ๋‹ค.
  • #include < queue > ๋ฅผ ์„ ์–ธํ•ด์•ผ priority queue๋ฅผ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  • prioirty_queue < T, container< T >, compare > ํ˜•ํƒœ
  • ์ œ๋„ˆ๋ฆญํ•˜๊ฒŒ ๊ตฌํ˜„๋˜์–ด ์–ด๋– ํ•œ type์ด๋ผ๋„ ์›์†Œ๊ฐ€ ๋  ์ˆ˜ ์žˆ์œผ๋ฉฐ, ๊ธฐ๋ณธ container๋Š” vector ์ž…๋‹ˆ๋‹ค.
  • compare๋Š” ๋น„๊ต ํด๋ž˜์Šค๋กœ struct๋ฅผ ์ƒˆ๋กญ๊ฒŒ ๊ตฌํ˜„ํ•˜์—ฌ ๋น„๊ต ํด๋ž˜์Šค๋ฅผ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ( ๊ธฐ๋ณธ๊ฐ’์œผ๋กœ ๋‚ด๋ฆผ์ฐจ์ˆœ )

๊ธฐ๋ณธ ํ•จ์ˆ˜

empty( )

  • ํ๊ฐ€ ๋น„์–ด์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋Š” ํ•จ์ˆ˜
  • if priority queue is empty, then return 1 else 0

size( )

  • ํ์˜ ํฌ๊ธฐ๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋Š” ํ•จ์ˆ˜
  • return size_type (unsigned int )

top( )

  • ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๊ฐ€์žฅ ํฐ ์›์†Œ๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋Š” ํ•จ์ˆ˜
  • return reference top element

push( element )

  • ์šฐ์„ ์ˆœ์œ„ ํ์— ์›์†Œ๋ฅผ ์ถ”๊ฐ€ํ•˜๋Š” ํ•จ์ˆ˜
  • heap ๊ตฌ์กฐ์ด๊ธฐ ๋•Œ๋ฌธ์— ์‹œ๊ฐ„ ๋ณต์žก๋„ O(log n)

pop( )

  • ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๊ฐ€์žฅ ํฐ ์›์†Œ๋ฅผ ์‚ญ์ œํ•˜๋Š” ํ•จ์ˆ˜
  • heap ๊ตฌ์กฐ์ด๊ธฐ ๋•Œ๋ฌธ์— ์‹œ๊ฐ„ ๋ณต์žก๋„ O(log n)

swap( queue )

  • ์šฐ์„ ์ˆœ์œ„ ํ๋ฅผ ๋ฐ”๊พธ๋Š” ํ•จ์ˆ˜

์ฃผ์˜์‚ฌํ•ญ!!

  • Compare์— ๋“ค์–ด๊ฐ€๋Š” ๊ฒƒ์€ ๋น„๊ต ํ•จ์ˆ˜๊ฐ€ ์•„๋‹Œ ๋น„๊ต ํด๋ž˜์Šค๊ฐ€ ๋“ค์–ด๊ฐ€์•ผ ํ•ฉ๋‹ˆ๋‹ค.
  • less< int > => ๋น„๊ต ํด๋ž˜์Šค, less< int >( ) => ๋น„๊ต ํ•จ์ˆ˜
  • less< int >( )๋Š” ์˜ค๋ฆ„์ฐจ์ˆœ์ด๋‹ค.
  • ๊ทธ๋Ÿฌ๋‚˜, priority_queue์—์„œ ์‚ฌ์šฉํ•  ๊ฒฝ์šฐ๋Š” less< int >๋กœ ์‚ฌ์šฉํ•˜๊ณ  ๋‚ด๋ฆผ์ฐจ์ˆœ์ด๋‹ค!! (์ค‘์š”)

์‹ค์Šต

๊ฒฐ๊ณผ

  • ์ถ”๊ฐ€๋กœ ๊ถ๊ธˆํ•œ ์ ์ด๋‚˜ ์ˆ˜์ •ํ•  ๋ถ€๋ถ„ ์žˆ์œผ๋ฉด ๋Œ“๊ธ€๋กœ ๋‚จ๊ฒจ์ฃผ์„ธ์š”.
๋ฐ˜์‘ํ˜•