- 23,765
- 46
- 8 Ноя 2022
Информатика доказала, что сваливать задачи в «кучу» выгоднее, чем вести идеальные списки.
В мире цифровых данных нет универсального способа всё «разложить по полкам». То, как компьютер хранит информацию, всегда связано с компромиссами: где-то важнее скорость записи, где-то — скорость поиска, а где-то — экономия памяти. Именно этим и занимаются разработчики структур данных : они проектируют такие схемы хранения, которые по-разному балансируют между скоростью добавления, удаления, поиска и объёмом используемой памяти.
Даже простое действие вроде создания нового файла — это уже задача для системы хранения. Компьютеру нужно быстро найти место, куда записать информацию. Если файл потом удаляют, система должна так же быстро найти нужные участки памяти и освободить их. Чем больше данных, тем сложнее становится эта логистика.
Принцип можно объяснить на бытовом примере с книгами. Если расставить их на одной длинной полке строго по алфавиту, любую книгу легко найти. Но каждая новая покупка превращается в проблему: нужно найти правильное место и сдвигать остальные тома. Если же просто ставить книги туда, где есть свободное место, всё добавляется быстро, но поиск превращается в хаос. Такой выбор между удобством добавления и удобством поиска кажется мелочью в маленькой библиотеке, но становится серьёзной проблемой, когда речь идёт о тысячах объектов.
Другой вариант — не одна полка, а набор ящиков. Например, 26 контейнеров по буквам алфавита. Тогда по первой букве фамилии автора сразу понятно, куда положить книгу и где её искать. В некоторых ситуациях это действительно ускоряет и добавление, и поиск.
<!--'start_frame_cache_Zg1Ab0'--><div class="banner-detailed"><div class="banner-detailed__shell"><div class="banner-detailed__title">Цифровой контроль неизбежен. Инструкция, как сохранить свободу. <span>Подпишитесь на нас</span><div class="banner-detailed__arrow"><svg viewBox="0 0 40 40" fill="none" xmlns="http://www.w3.org/2000/svg"><path d="M20.5375 34.4392L22.465 31.7392C22.5739 31.5872 22.7145 31.4607 22.8772 31.3684C23.0399 31.2762 23.2207 31.2205 23.407 31.2052C23.5934 31.1898 23.7809 31.2152 23.9564 31.2796C24.132 31.344 24.2915 31.4458 24.4237 31.578L29.6025 36.758C30.0787 37.2333 30.724 37.5002 31.3969 37.5002C32.0697 37.5002 32.715 37.2333 33.1912 36.758L36.7575 33.1917C37.2328 32.7155 37.4998 32.0702 37.4998 31.3973C37.4998 30.7245 37.2328 30.0792 36.7575 29.603L31.5775 24.4242C31.4453 24.2919 31.3435 24.1325 31.2791 23.9569C31.2147 23.7814 31.1893 23.5939 31.2047 23.4075C31.22 23.2211 31.2757 23.0404 31.368 22.8777C31.4602 22.715 31.5867 22.5743 31.7387 22.4655L34.4387 20.538C34.6405 20.3939 34.7965 20.1947 34.8878 19.9641C34.9791 19.7336 35.0018 19.4816 34.9534 19.2385C34.9049 18.9953 34.7873 18.7713 34.6146 18.5934C34.442 18.4155 34.2216 18.2912 33.98 18.2355L13.5112 13.5117L18.235 33.9805C18.2907 34.2221 18.415 34.4425 18.5929 34.6151C18.7708 34.7878 18.9948 34.9054 19.238 34.9539C19.4812 35.0023 19.7331 34.9795 19.9637 34.8882C20.1942 34.7969 20.3934 34.641 20.5375 34.4392Z" fill="#FFD98C"></path><path d="M34.0751 37.6413C33.3582 38.3389 32.3973 38.7293 31.397 38.7293C30.3966 38.7293 29.4358 38.3389 28.7189 37.6413L23.4826 32.4663L21.5539 35.165C21.2699 35.5626 20.8773 35.8698 20.423 36.0497C19.9688 36.2295 19.4723 36.2744 18.9931 36.179C18.514 36.0836 18.0726 35.8518 17.7219 35.5117C17.3713 35.1715 17.1263 34.7373 17.0164 34.2613L12.2926 13.7925C12.2447 13.5858 12.2502 13.3702 12.3086 13.1662C12.367 12.9622 12.4764 12.7764 12.6264 12.6263C12.7765 12.4763 12.9623 12.3669 13.1663 12.3085C13.3703 12.2501 13.5859 12.2446 13.7926 12.2925L34.2614 17.0175C34.7374 17.1271 35.1717 17.3719 35.512 17.7225C35.8523 18.073 36.0841 18.5144 36.1795 18.9935C36.275 19.4726 36.23 19.9691 36.0501 20.4233C35.8701 20.8775 35.5628 21.27 35.1651 21.5538L32.4614 23.54L37.6414 28.7188C38.3498 29.43 38.7476 30.393 38.7476 31.3969C38.7476 32.4008 38.3498 33.3637 37.6414 34.075L34.0751 37.6413ZM35.8751 30.4863L30.6951 25.3075C30.4344 25.047 30.2336 24.7328 30.1068 24.3868C29.9799 24.0407 29.9299 23.6712 29.9604 23.3039C29.9908 22.9366 30.101 22.5804 30.2831 22.26C30.4653 21.9396 30.7151 21.6628 31.0151 21.4488L33.6989 19.4488L15.1851 15.1763L19.5001 33.7275L19.5139 33.7113L21.4414 31.0125C21.6555 30.7124 21.9325 30.4626 22.253 30.2805C22.5735 30.0983 22.9298 29.9882 23.2972 29.9577C23.6646 29.9272 24.0342 29.9772 24.3803 30.1041C24.7264 30.231 25.0407 30.4318 25.3014 30.6925L30.4864 35.875C30.728 36.1163 31.0555 36.2518 31.397 36.2518C31.7385 36.2518 32.066 36.1163 32.3076 35.875L35.8751 32.3075C36.1161 32.0657 36.2514 31.7383 36.2514 31.3969C36.2514 31.0555 36.1161 30.728 35.8751 30.4863ZM8.14636 9.385C7.98292 9.38706 7.82069 9.35675 7.66901 9.29583C7.51733 9.2349 7.37921 9.14455 7.26261 9.03L4.58011 6.3475C4.35242 6.11175 4.22643 5.796 4.22927 5.46825C4.23212 5.1405 4.36358 4.82699 4.59534 4.59523C4.8271 4.36347 5.14062 4.23201 5.46836 4.22916C5.79611 4.22631 6.11186 4.3523 6.34761 4.58L9.03012 7.2625C9.20107 7.43787 9.31674 7.65959 9.36277 7.90013C9.4088 8.14068 9.38315 8.38944 9.28901 8.61553C9.19487 8.84162 9.03639 9.03508 8.83325 9.17188C8.63011 9.30867 8.39126 9.38278 8.14636 9.385ZM17.9726 9.03C17.7362 9.26044 17.419 9.3894 17.0889 9.3894C16.7587 9.3894 16.4416 9.26044 16.2051 9.03C15.9708 8.79559 15.8391 8.47771 15.8391 8.14625C15.8391 7.8148 15.9708 7.49691 16.2051 7.2625L18.8876 4.58C19.0029 4.46061 19.1409 4.36538 19.2934 4.29987C19.4459 4.23436 19.6099 4.19988 19.7759 4.19844C19.9418 4.197 20.1064 4.22862 20.2601 4.29147C20.4137 4.35432 20.5532 4.44714 20.6706 4.56451C20.788 4.68187 20.8808 4.82144 20.9436 4.97506C21.0065 5.12868 21.0381 5.29328 21.0367 5.45925C21.0352 5.62523 21.0008 5.78925 20.9352 5.94176C20.8697 6.09426 20.7745 6.23219 20.6551 6.3475L17.9726 9.03ZM6.34761 20.655C6.11146 20.886 5.79423 21.0154 5.46386 21.0154C5.1335 21.0154 4.81627 20.886 4.58011 20.655C4.34578 20.4206 4.21413 20.1027 4.21413 19.7713C4.21413 19.4398 4.34578 19.1219 4.58011 18.8875L7.26261 16.205C7.37792 16.0856 7.51585 15.9904 7.66836 15.9249C7.82086 15.8594 7.98489 15.8249 8.15086 15.8234C8.31684 15.822 8.48144 15.8536 8.63506 15.9165C8.78868 15.9793 8.92824 16.0721 9.04561 16.1895C9.16297 16.3069 9.25579 16.4464 9.31864 16.6001C9.38149 16.7537 9.41312 16.9183 9.41168 17.0843C9.41024 17.2502 9.37575 17.4143 9.31024 17.5668C9.24473 17.7193 9.1495 17.8572 9.03012 17.9725L6.34761 20.655ZM12.6176 7.54375C12.2861 7.54375 11.9682 7.41205 11.7337 7.17763C11.4993 6.94321 11.3676 6.62527 11.3676 6.29375V2.5C11.3676 2.16848 11.4993 1.85054 11.7337 1.61612C11.9682 1.3817 12.2861 1.25 12.6176 1.25C12.9491 1.25 13.2671 1.3817 13.5015 1.61612C13.7359 1.85054 13.8676 2.16848 13.8676 2.5V6.29375C13.8676 6.62527 13.7359 6.94321 13.5015 7.17763C13.2671 7.41205 12.9491 7.54375 12.6176 7.54375ZM2.50011 11.3675H6.29387C6.62539 11.3675 6.94333 11.4992 7.17775 11.7336C7.41217 11.968 7.54387 12.286 7.54387 12.6175C7.54387 12.949 7.41217 13.267 7.17775 13.5014C6.94333 13.7358 6.62539 13.8675 6.29387 13.8675H2.50011C2.16859 13.8675 1.85065 13.7358 1.61623 13.5014C1.38181 13.267 1.25011 12.949 1.25011 12.6175C1.25011 12.286 1.38181 11.968 1.61623 11.7336C1.85065 11.4992 2.16859 11.3675 2.50011 11.3675Z" fill="#272727"></path></svg> <!--'end_frame_cache_Zg1Ab0'--> Но и тут есть свои ограничения. Если в ящике лежит не одна книга, а десятки, поиск внутри него снова занимает время. А если большинство авторов начинается на одну и ту же букву, часть контейнеров будет переполнена, а другие останутся пустыми, занимая место без пользы.
В информатике похожую логику используют хеш-таблицы . Это структуры данных, где каждому объекту заранее вычисляется адрес хранения на основе его ключа. В случае с книгами ключом может быть имя автора, название или другой параметр. Специальная математическая функция превращает этот ключ в номер ячейки памяти. Такая функция называется хеш-функцией. Хорошая хеш-функция распределяет данные равномерно, чтобы одни области памяти не перегружались, а другие не простаивали.
Если увеличить количество ячеек, поиск становится быстрее, но растёт расход памяти, потому что часть ячеек может оставаться пустой. В итоге снова возникает компромисс — скорость против объёма. Даже спустя десятилетия после появления хеш-таблиц учёные продолжают находить новые свойства этих структур. Недавно были получены модели, которые дают почти идеальный баланс между скоростью работы и расходом памяти. А в прошлом году студент опроверг одну из старых теоретических гипотез о том, сколько времени в принципе нужно для поиска элемента в почти заполненной хеш-таблице.
Но бывают ситуации, где вообще не важно, где именно лежат данные, пока они не становятся приоритетными. Простой пример — список задач с разными сроками. Новые задачи добавляются постоянно, но искать любую из них не нужно. Важна только самая срочная.
Для таких сценариев используют другую структуру данных — кучу (heap). Это неупорядоченное на первый взгляд хранилище, где элементы расположены слоями, и самый важный всегда находится сверху. Всё остальное может лежать как угодно, потому что доступ к ним не нужен, пока они не поднимаются в приоритетах.
Одна из базовых реализаций кучи строится на бинарном дереве. В нём есть верхний узел, от которого вниз отходят два подузла, от них — ещё по два и так далее. Каждый узел хранит одну задачу с числовым приоритетом. Чем меньше число, тем выше срочность. Новая задача добавляется в свободное место на нижнем уровне. После этого система сравнивает её приоритет с тем, что находится уровнем выше. Если новая задача важнее, элементы меняются местами. Этот процесс повторяется до тех пор, пока задача не окажется под элементом с более высоким приоритетом. В результате самая срочная задача всегда оказывается наверху.
Даже при большом количестве задач такая схема работает очень быстро. Например, при тысяче задач новой записи потребуется всего несколько перестановок, чтобы попасть на нужное место. Когда верхний элемент удаляется, система так же быстро подтягивает следующую по приоритету задачу снизу. Кучи широко применяются в алгоритмах поиска кратчайших путей в сетях, навигации, логистике, маршрутизации и других задачах, где важно быстро получать самый «важный» элемент из множества.
В итоге информатика приходит к тому же выводу, что и в быту: идеального способа хранения не существует. Любая схема — это компромисс между скоростью, памятью и удобством доступа. Иногда лучше порядок, иногда — скорость, иногда — приоритет. И если какие-то данные важнее других, система может быть неидеально организованной в целом, но при этом работать максимально эффективно там, где это действительно нужно.
В мире цифровых данных нет универсального способа всё «разложить по полкам». То, как компьютер хранит информацию, всегда связано с компромиссами: где-то важнее скорость записи, где-то — скорость поиска, а где-то — экономия памяти. Именно этим и занимаются разработчики структур данных : они проектируют такие схемы хранения, которые по-разному балансируют между скоростью добавления, удаления, поиска и объёмом используемой памяти.
Даже простое действие вроде создания нового файла — это уже задача для системы хранения. Компьютеру нужно быстро найти место, куда записать информацию. Если файл потом удаляют, система должна так же быстро найти нужные участки памяти и освободить их. Чем больше данных, тем сложнее становится эта логистика.
Принцип можно объяснить на бытовом примере с книгами. Если расставить их на одной длинной полке строго по алфавиту, любую книгу легко найти. Но каждая новая покупка превращается в проблему: нужно найти правильное место и сдвигать остальные тома. Если же просто ставить книги туда, где есть свободное место, всё добавляется быстро, но поиск превращается в хаос. Такой выбор между удобством добавления и удобством поиска кажется мелочью в маленькой библиотеке, но становится серьёзной проблемой, когда речь идёт о тысячах объектов.
Другой вариант — не одна полка, а набор ящиков. Например, 26 контейнеров по буквам алфавита. Тогда по первой букве фамилии автора сразу понятно, куда положить книгу и где её искать. В некоторых ситуациях это действительно ускоряет и добавление, и поиск.
<!--'start_frame_cache_Zg1Ab0'--><div class="banner-detailed"><div class="banner-detailed__shell"><div class="banner-detailed__title">Цифровой контроль неизбежен. Инструкция, как сохранить свободу. <span>Подпишитесь на нас</span><div class="banner-detailed__arrow"><svg viewBox="0 0 40 40" fill="none" xmlns="http://www.w3.org/2000/svg"><path d="M20.5375 34.4392L22.465 31.7392C22.5739 31.5872 22.7145 31.4607 22.8772 31.3684C23.0399 31.2762 23.2207 31.2205 23.407 31.2052C23.5934 31.1898 23.7809 31.2152 23.9564 31.2796C24.132 31.344 24.2915 31.4458 24.4237 31.578L29.6025 36.758C30.0787 37.2333 30.724 37.5002 31.3969 37.5002C32.0697 37.5002 32.715 37.2333 33.1912 36.758L36.7575 33.1917C37.2328 32.7155 37.4998 32.0702 37.4998 31.3973C37.4998 30.7245 37.2328 30.0792 36.7575 29.603L31.5775 24.4242C31.4453 24.2919 31.3435 24.1325 31.2791 23.9569C31.2147 23.7814 31.1893 23.5939 31.2047 23.4075C31.22 23.2211 31.2757 23.0404 31.368 22.8777C31.4602 22.715 31.5867 22.5743 31.7387 22.4655L34.4387 20.538C34.6405 20.3939 34.7965 20.1947 34.8878 19.9641C34.9791 19.7336 35.0018 19.4816 34.9534 19.2385C34.9049 18.9953 34.7873 18.7713 34.6146 18.5934C34.442 18.4155 34.2216 18.2912 33.98 18.2355L13.5112 13.5117L18.235 33.9805C18.2907 34.2221 18.415 34.4425 18.5929 34.6151C18.7708 34.7878 18.9948 34.9054 19.238 34.9539C19.4812 35.0023 19.7331 34.9795 19.9637 34.8882C20.1942 34.7969 20.3934 34.641 20.5375 34.4392Z" fill="#FFD98C"></path><path d="M34.0751 37.6413C33.3582 38.3389 32.3973 38.7293 31.397 38.7293C30.3966 38.7293 29.4358 38.3389 28.7189 37.6413L23.4826 32.4663L21.5539 35.165C21.2699 35.5626 20.8773 35.8698 20.423 36.0497C19.9688 36.2295 19.4723 36.2744 18.9931 36.179C18.514 36.0836 18.0726 35.8518 17.7219 35.5117C17.3713 35.1715 17.1263 34.7373 17.0164 34.2613L12.2926 13.7925C12.2447 13.5858 12.2502 13.3702 12.3086 13.1662C12.367 12.9622 12.4764 12.7764 12.6264 12.6263C12.7765 12.4763 12.9623 12.3669 13.1663 12.3085C13.3703 12.2501 13.5859 12.2446 13.7926 12.2925L34.2614 17.0175C34.7374 17.1271 35.1717 17.3719 35.512 17.7225C35.8523 18.073 36.0841 18.5144 36.1795 18.9935C36.275 19.4726 36.23 19.9691 36.0501 20.4233C35.8701 20.8775 35.5628 21.27 35.1651 21.5538L32.4614 23.54L37.6414 28.7188C38.3498 29.43 38.7476 30.393 38.7476 31.3969C38.7476 32.4008 38.3498 33.3637 37.6414 34.075L34.0751 37.6413ZM35.8751 30.4863L30.6951 25.3075C30.4344 25.047 30.2336 24.7328 30.1068 24.3868C29.9799 24.0407 29.9299 23.6712 29.9604 23.3039C29.9908 22.9366 30.101 22.5804 30.2831 22.26C30.4653 21.9396 30.7151 21.6628 31.0151 21.4488L33.6989 19.4488L15.1851 15.1763L19.5001 33.7275L19.5139 33.7113L21.4414 31.0125C21.6555 30.7124 21.9325 30.4626 22.253 30.2805C22.5735 30.0983 22.9298 29.9882 23.2972 29.9577C23.6646 29.9272 24.0342 29.9772 24.3803 30.1041C24.7264 30.231 25.0407 30.4318 25.3014 30.6925L30.4864 35.875C30.728 36.1163 31.0555 36.2518 31.397 36.2518C31.7385 36.2518 32.066 36.1163 32.3076 35.875L35.8751 32.3075C36.1161 32.0657 36.2514 31.7383 36.2514 31.3969C36.2514 31.0555 36.1161 30.728 35.8751 30.4863ZM8.14636 9.385C7.98292 9.38706 7.82069 9.35675 7.66901 9.29583C7.51733 9.2349 7.37921 9.14455 7.26261 9.03L4.58011 6.3475C4.35242 6.11175 4.22643 5.796 4.22927 5.46825C4.23212 5.1405 4.36358 4.82699 4.59534 4.59523C4.8271 4.36347 5.14062 4.23201 5.46836 4.22916C5.79611 4.22631 6.11186 4.3523 6.34761 4.58L9.03012 7.2625C9.20107 7.43787 9.31674 7.65959 9.36277 7.90013C9.4088 8.14068 9.38315 8.38944 9.28901 8.61553C9.19487 8.84162 9.03639 9.03508 8.83325 9.17188C8.63011 9.30867 8.39126 9.38278 8.14636 9.385ZM17.9726 9.03C17.7362 9.26044 17.419 9.3894 17.0889 9.3894C16.7587 9.3894 16.4416 9.26044 16.2051 9.03C15.9708 8.79559 15.8391 8.47771 15.8391 8.14625C15.8391 7.8148 15.9708 7.49691 16.2051 7.2625L18.8876 4.58C19.0029 4.46061 19.1409 4.36538 19.2934 4.29987C19.4459 4.23436 19.6099 4.19988 19.7759 4.19844C19.9418 4.197 20.1064 4.22862 20.2601 4.29147C20.4137 4.35432 20.5532 4.44714 20.6706 4.56451C20.788 4.68187 20.8808 4.82144 20.9436 4.97506C21.0065 5.12868 21.0381 5.29328 21.0367 5.45925C21.0352 5.62523 21.0008 5.78925 20.9352 5.94176C20.8697 6.09426 20.7745 6.23219 20.6551 6.3475L17.9726 9.03ZM6.34761 20.655C6.11146 20.886 5.79423 21.0154 5.46386 21.0154C5.1335 21.0154 4.81627 20.886 4.58011 20.655C4.34578 20.4206 4.21413 20.1027 4.21413 19.7713C4.21413 19.4398 4.34578 19.1219 4.58011 18.8875L7.26261 16.205C7.37792 16.0856 7.51585 15.9904 7.66836 15.9249C7.82086 15.8594 7.98489 15.8249 8.15086 15.8234C8.31684 15.822 8.48144 15.8536 8.63506 15.9165C8.78868 15.9793 8.92824 16.0721 9.04561 16.1895C9.16297 16.3069 9.25579 16.4464 9.31864 16.6001C9.38149 16.7537 9.41312 16.9183 9.41168 17.0843C9.41024 17.2502 9.37575 17.4143 9.31024 17.5668C9.24473 17.7193 9.1495 17.8572 9.03012 17.9725L6.34761 20.655ZM12.6176 7.54375C12.2861 7.54375 11.9682 7.41205 11.7337 7.17763C11.4993 6.94321 11.3676 6.62527 11.3676 6.29375V2.5C11.3676 2.16848 11.4993 1.85054 11.7337 1.61612C11.9682 1.3817 12.2861 1.25 12.6176 1.25C12.9491 1.25 13.2671 1.3817 13.5015 1.61612C13.7359 1.85054 13.8676 2.16848 13.8676 2.5V6.29375C13.8676 6.62527 13.7359 6.94321 13.5015 7.17763C13.2671 7.41205 12.9491 7.54375 12.6176 7.54375ZM2.50011 11.3675H6.29387C6.62539 11.3675 6.94333 11.4992 7.17775 11.7336C7.41217 11.968 7.54387 12.286 7.54387 12.6175C7.54387 12.949 7.41217 13.267 7.17775 13.5014C6.94333 13.7358 6.62539 13.8675 6.29387 13.8675H2.50011C2.16859 13.8675 1.85065 13.7358 1.61623 13.5014C1.38181 13.267 1.25011 12.949 1.25011 12.6175C1.25011 12.286 1.38181 11.968 1.61623 11.7336C1.85065 11.4992 2.16859 11.3675 2.50011 11.3675Z" fill="#272727"></path></svg> <!--'end_frame_cache_Zg1Ab0'--> Но и тут есть свои ограничения. Если в ящике лежит не одна книга, а десятки, поиск внутри него снова занимает время. А если большинство авторов начинается на одну и ту же букву, часть контейнеров будет переполнена, а другие останутся пустыми, занимая место без пользы.
В информатике похожую логику используют хеш-таблицы . Это структуры данных, где каждому объекту заранее вычисляется адрес хранения на основе его ключа. В случае с книгами ключом может быть имя автора, название или другой параметр. Специальная математическая функция превращает этот ключ в номер ячейки памяти. Такая функция называется хеш-функцией. Хорошая хеш-функция распределяет данные равномерно, чтобы одни области памяти не перегружались, а другие не простаивали.
Если увеличить количество ячеек, поиск становится быстрее, но растёт расход памяти, потому что часть ячеек может оставаться пустой. В итоге снова возникает компромисс — скорость против объёма. Даже спустя десятилетия после появления хеш-таблиц учёные продолжают находить новые свойства этих структур. Недавно были получены модели, которые дают почти идеальный баланс между скоростью работы и расходом памяти. А в прошлом году студент опроверг одну из старых теоретических гипотез о том, сколько времени в принципе нужно для поиска элемента в почти заполненной хеш-таблице.
Но бывают ситуации, где вообще не важно, где именно лежат данные, пока они не становятся приоритетными. Простой пример — список задач с разными сроками. Новые задачи добавляются постоянно, но искать любую из них не нужно. Важна только самая срочная.
Для таких сценариев используют другую структуру данных — кучу (heap). Это неупорядоченное на первый взгляд хранилище, где элементы расположены слоями, и самый важный всегда находится сверху. Всё остальное может лежать как угодно, потому что доступ к ним не нужен, пока они не поднимаются в приоритетах.
Одна из базовых реализаций кучи строится на бинарном дереве. В нём есть верхний узел, от которого вниз отходят два подузла, от них — ещё по два и так далее. Каждый узел хранит одну задачу с числовым приоритетом. Чем меньше число, тем выше срочность. Новая задача добавляется в свободное место на нижнем уровне. После этого система сравнивает её приоритет с тем, что находится уровнем выше. Если новая задача важнее, элементы меняются местами. Этот процесс повторяется до тех пор, пока задача не окажется под элементом с более высоким приоритетом. В результате самая срочная задача всегда оказывается наверху.
Даже при большом количестве задач такая схема работает очень быстро. Например, при тысяче задач новой записи потребуется всего несколько перестановок, чтобы попасть на нужное место. Когда верхний элемент удаляется, система так же быстро подтягивает следующую по приоритету задачу снизу. Кучи широко применяются в алгоритмах поиска кратчайших путей в сетях, навигации, логистике, маршрутизации и других задачах, где важно быстро получать самый «важный» элемент из множества.
В итоге информатика приходит к тому же выводу, что и в быту: идеального способа хранения не существует. Любая схема — это компромисс между скоростью, памятью и удобством доступа. Иногда лучше порядок, иногда — скорость, иногда — приоритет. И если какие-то данные важнее других, система может быть неидеально организованной в целом, но при этом работать максимально эффективно там, где это действительно нужно.
- Источник новости
- www.securitylab.ru
