{"id":190474,"date":"2013-08-28T15:01:03","date_gmt":"2013-08-28T11:01:03","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=190474"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=190474","title":{"rendered":"<span class=\"post_title\">\u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445, PHP. \u0427\u0430\u0441\u0442\u044c \u0432\u0442\u043e\u0440\u0430\u044f<\/span>"},"content":{"rendered":"<div class=\"content html_format\">       \u041f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u044e \u0441\u043e\u0432\u043c\u0435\u0449\u0430\u0442\u044c \u043f\u0440\u0438\u044f\u0442\u043d\u043e\u0435 \u0441 \u043f\u043e\u043b\u0435\u0437\u043d\u044b\u043c \u0438 \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0438\u0442\u044c. \u0421\u0435\u0433\u043e\u0434\u043d\u044f \u0440\u0435\u0447\u044c \u0437\u0430\u0439\u0434\u0435\u0442 \u043e \u043a\u0443\u0447\u0430\u0445 (heaps) \u0438 \u0433\u0440\u0430\u0444\u0430\u0445. \u041a\u0430\u043a \u043e\u0431\u044b\u0447\u043d\u043e, \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b \u0441\u043a\u043e\u0440\u0435\u0435 \u043f\u043e\u0434\u043e\u0439\u0434\u0435\u0442 \u043d\u043e\u0432\u0438\u0447\u043a\u0430\u043c \u2014 \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438, \u0435\u0441\u043b\u0438 \u043d\u0435 \u0432\u0441\u044f, \u0443\u0436\u0435 \u0433\u0434\u0435-\u0442\u043e \u0442\u0430\u043a \u0438\u043b\u0438 \u0438\u043d\u0430\u0447\u0435 \u043e\u0441\u0432\u0435\u0449\u0430\u043b\u0430\u0441\u044c.<\/p>\n<p>  \u0412 \u043a\u043e\u043d\u0446\u0435 <a href=\"http:\/\/habrahabr.ru\/post\/190176\/\">\u043f\u0440\u043e\u0448\u043b\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0438<\/a> \u0437\u0430\u0442\u0440\u0430\u0433\u0438\u0432\u0430\u043b\u0438\u0441\u044c \u0434\u0435\u0440\u0435\u0432\u044c\u044f, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043d\u0430\u0447\u043d\u0435\u043c \u0441 \u043a\u0443\u0447\u0438, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043c\u0435\u0436\u0434\u0443 \u043a\u0443\u0447\u0435\u0439 \u0438 \u0434\u0435\u0440\u0435\u0432\u044c\u044f\u043c\u0438 \u0435\u0441\u0442\u044c \u043e\u0431\u0449\u0438\u0435 \u043a\u043e\u0440\u043d\u0438. \u0417\u0430\u0442\u0435\u043c \u043f\u0435\u0440\u0435\u0439\u0434\u0435\u043c \u043a \u0433\u0440\u0430\u0444\u0430\u043c \u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b.<\/p>\n<p>  <a name=\"habracut\"><\/a><br \/>  \u041a\u0443\u0447\u0430 \u2014 \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u0430\u044f, \u0434\u0435\u0440\u0435\u0432\u043e\u043f\u043e\u0434\u043e\u0431\u043d\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430, \u0443 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0435\u0441\u0442\u044c \u043e\u0434\u043d\u043e \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e \u2014 \u043b\u044e\u0431\u043e\u0439 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0439 \u0443\u0437\u0435\u043b \u0432\u0441\u0435\u0433\u0434\u0430 \u0431\u043e\u043b\u044c\u0448\u0435 \u043b\u0438\u0431\u043e \u0440\u0430\u0432\u0435\u043d \u0441\u0432\u043e\u0438\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u0430\u043c. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043f\u0440\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0438 \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0443\u0441\u043b\u043e\u0432\u0438\u044f, \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043a\u0443\u0447\u0438 \u0432\u0441\u0435\u0433\u0434\u0430 \u0431\u0443\u0434\u0435\u0442 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c. \u0414\u0430\u043d\u043d\u044b\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 (\u043f\u043e\u043b\u043d\u043e\u0439) \u043a\u0443\u0447\u0435\u0439 \u0438\u043b\u0438 maxheap. \u041a\u0443\u0447\u0430, \u0433\u0434\u0435 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u0435\u043d, \u0430 \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0439 \u0443\u0437\u0435\u043b \u043c\u0435\u043d\u044c\u0448\u0435 \u0438\u043b\u0438 \u0440\u0430\u0432\u0435\u043d \u0441\u0432\u043e\u0438\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u0430\u043c \u2014 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u043a\u0443\u0447\u0430 \u0438\u043b\u0438 minheap. <\/p>\n<p>  \u0414\u0432\u043e\u0438\u0447\u043d\u0443\u044e \u043a\u0443\u0447\u0443 (maxheap) \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:<\/p>\n<p>  <img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/338\/db4\/4bf\/338db44bfbd1b0f507bb360202252e86.png\" alt=\"image\"\/><\/p>\n<p>  \u041e\u043d\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u043f\u043e\u0442\u043e\u043c\u0443, \u0447\u0442\u043e \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c \u0438\u043c\u0435\u0435\u0442 \u0434\u0432\u0430 \u043f\u043e\u0442\u043e\u043c\u043a\u0430.<br \/>  \u0421\u0442\u043e\u0438\u0442 \u043e\u0442\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u043a\u0443\u0447\u0438 \u0445\u043e\u0442\u044c \u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e\u0442\u0441\u044f \u043a\u0430\u043a \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f, \u043d\u043e \u0443 \u043d\u0438\u0445 \u043d\u0435\u0442 \u0442\u0430\u043a\u043e\u0433\u043e \u043f\u043e\u043d\u044f\u0442\u0438\u044f \u043a\u0430\u043a \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0438\u0432\u0430\u043d\u0438\u0435 \u0438 \u043d\u0435\u0442 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u0434\u043b\u044f \u043e\u0431\u0445\u043e\u0434\u0430. \u041a\u0443\u0447\u0430 \u2014 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0442\u0430\u0431\u043b\u0438\u0447\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043a \u043d\u0435\u0439 \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c\u044b \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u0431\u0430\u0437\u043e\u0432\u044b\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438:<\/p>\n<ol>\n<li>create \u2013 \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u043f\u0443\u0441\u0442\u0443\u044e \u043a\u0443\u0447\u0443.<\/li>\n<li>isEmpty \u2013 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c, \u043f\u0443\u0441\u0442\u0430 \u043b\u0438 \u043a\u0443\u0447\u0430 \u0438\u043b\u0438 \u043d\u0435\u0442.<\/li>\n<li>insert \u2013 \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432 \u043a\u0443\u0447\u0443.<\/li>\n<li>extract \u2013 \u0438\u0437\u0432\u043b\u0435\u0447\u044c \u0438 \u0443\u0434\u0430\u043b\u0438\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 (\u043a\u043e\u0440\u0435\u043d\u044c, \u0432\u0435\u0440\u0448\u0438\u043d\u0443) \u0438\u0437 \u043a\u0443\u0447\u0438.<\/li>\n<\/ol>\n<p>  \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f \u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0441\u043e\u0432\u043c\u0435\u0449\u0435\u043d\u044b \u0432 \u043e\u0434\u043d\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0438\u0437\u0432\u043b\u0435\u0447\u0435\u043d\u0438\u044f, \u0442\u043e \u0434\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u0435\u0435 \u0438 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c.<\/p>\n<p>  \u041f\u0440\u0430\u0432\u0438\u043b\u043e \u0434\u043b\u044f \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0438\u0437 \u043a\u0443\u0447\u0438 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0443\u0434\u0430\u043b\u044f\u0442\u044c \u043c\u043e\u0436\u043d\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442. \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u043c\u044b \u0443\u0434\u0430\u043b\u0438\u043b\u0438 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0438\u0437 \u043f\u0440\u0438\u043c\u0435\u0440\u0430 \u0432\u044b\u0448\u0435 (100). \u041f\u043e\u0441\u043b\u0435 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u043c\u044b \u043e\u0441\u0442\u0430\u043d\u0435\u043c\u0441\u044f \u0441 \u0434\u0432\u0443\u043c\u044f \u0440\u0430\u0437\u0434\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u043a\u0443\u0447\u0430\u043c\u0438 \u0438 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043a\u0430\u043a-\u0442\u043e \u043f\u0435\u0440\u0435\u0441\u043e\u0431\u0440\u0430\u0442\u044c \u0432\u0441\u0435 \u044d\u0442\u043e \u0432 \u043e\u0434\u043d\u0443 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u0443\u044e \u043a\u0443\u0447\u0443. \u041b\u0435\u0433\u0447\u0435 \u0432\u0441\u0435\u0433\u043e \u044d\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0435\u043d\u0438\u0435\u043c \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u0443\u0437\u043b\u0430 \u0432 \u043a\u043e\u0440\u0435\u043d\u044c, \u043e\u0434\u043d\u0430\u043a\u043e \u0432 \u0442\u0430\u043a\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0442\u0430\u043a\u0430\u044f \u043a\u0443\u0447\u0430 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u0434\u0445\u043e\u0434\u0438\u0442\u044c \u043f\u043e \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u043c\u0443 \u0443\u0441\u043b\u043e\u0432\u0438\u044e. \u0422\u0430\u043a\u0430\u044f \u043a\u0443\u0447\u0430 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f semiheap:<\/p>\n<p>  <img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/6e2\/28f\/d11\/6e228fd119fd5b3ad5f1513dd67243a7.png\" alt=\"image\"\/><\/p>\n<p>  \u0422\u0435\u043f\u0435\u0440\u044c \u043d\u0430\u0434\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0438\u0437 \u043f\u043e\u043b\u0443\u043a\u0443\u0447\u0438 \u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u0443\u044e \u043a\u0443\u0447\u0443. \u041e\u0434\u043d\u043e \u0438\u0437 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u044d\u0442\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u2014 \u0441\u043f\u0443\u0441\u043a\u0430\u0442\u044c \u043d\u043e\u0432\u044b\u0439 \u043a\u043e\u0440\u0435\u043d\u044c \u0432\u043d\u0438\u0437, \u043f\u043e\u043f\u0443\u0442\u043d\u043e \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u044f \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0441 \u0435\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430\u043c\u0438 \u0438 \u043c\u0435\u043d\u044f\u044f \u0435\u0433\u043e \u043c\u0435\u0441\u0442\u0430\u043c\u0438 \u0441 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043c\u044b \u0432\u0435\u0440\u043d\u0435\u043c \u0432 \u043a\u043e\u0440\u0435\u043d\u044c \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u043e\u043f\u0443\u0441\u0442\u0438\u0432 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u0432\u043d\u0438\u0437.<\/p>\n<p>  \u041c\u044b \u043c\u043e\u0436\u0435\u043c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c maxheap \u043a\u0430\u043a \u043c\u0430\u0441\u0441\u0438\u0432. \u0423\u0437\u0435\u043b \u0432 \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u0435 \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0438\u043c\u0435\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u0434\u0432\u0443\u0445 \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0443\u0437\u043b\u043e\u0432 n \u0431\u0438\u043d\u0430\u0440\u043d\u0430\u044f \u043a\u0443\u0447\u0430 \u0431\u0443\u0434\u0435\u0442 \u0438\u043c\u0435\u0442\u044c 2n+1 \u0443\u0437\u0435\u043b.<\/p>\n<p>  \u0420\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u043a\u0443\u0447\u0443 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:<\/p>\n<pre><code class=\"php\">&lt;?php class BinaryHeap {     protected $heap;       public function __construct() {         $this-&gt;heap  = array();     }       public function isEmpty() {         return empty($this-&gt;heap);     }       public function count() {         \/\/ \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u0440\u0430\u0437\u043c\u0435\u0440 \u043a\u0443\u0447\u0438         return count($this-&gt;heap) - 1;     }       public function extract() {         if ($this-&gt;isEmpty()) {             throw new RunTimeException('\u041a\u0443\u0447\u0430 \u043f\u0443\u0441\u0442\u0430!');         }           \/\/ \u0438\u0437\u0432\u043b\u0435\u0447\u0435\u043c \u043f\u0435\u0440\u0432\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0438\u0437 \u043a\u0443\u0447\u0438 \u0438 \u043f\u0440\u0438\u0441\u0432\u043e\u0438\u043c \u0435\u0433\u043e \u043a\u0430\u043a \u043a\u043e\u0440\u0435\u043d\u044c         $root = array_shift($this-&gt;heap);           if (!$this-&gt;isEmpty()) {             \/\/ \u043f\u0435\u0440\u0435\u043c\u0435\u0441\u0442\u0438\u043c \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043a\u0443\u0447\u0438 \u043d\u0430 \u0435\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u0443             \/\/ \u0447\u0442\u043e\u0431\u044b \u0438\u0437\u0431\u0430\u0432\u0438\u0442\u044c\u0441\u044f \u043e\u0442 \u0434\u0432\u0443\u0445 \u0440\u0430\u0437\u0434\u0435\u043b\u0435\u043d\u043d\u044b\u0445 \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0431\u043e\u0439 \u0432\u0435\u0442\u0432\u0435\u0439             $last = array_pop($this-&gt;heap);             array_unshift($this-&gt;heap, $last);               \/\/ \u043f\u0440\u0435\u0432\u0440\u0430\u0442\u0438\u043c \u043f\u043e\u043b\u0443\u043a\u0443\u0447\u0443 \u0432 \u043a\u0443\u0447\u0443             $this-&gt;adjust(0);         }           return $root;     }       public function compare($item1, $item2) {         if ($item1 === $item2) {             return 0;         }         \/\/ \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u0435 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u0434\u0430\u0441\u0442 \u043d\u0430\u043c minheap         return ($item1 &gt; $item2 ? 1 : -1);     }       protected function isLeaf($node) {         \/\/ \u0437\u0434\u0435\u0441\u044c \u0432\u0441\u0435\u0433\u0434\u0430 \u0431\u0443\u0434\u0435\u0442 2n + 1 \u0443\u0437\u0435\u043b \u0432 &quot;\u043f\u043e\u0434\u043a\u0443\u0447\u0435&quot;         return ((2 * $node) + 1) &gt; $this-&gt;count();     }       protected function adjust($root) {         \/\/ \u0441\u043f\u0443\u0441\u043a\u0430\u0435\u043c\u0441\u044f \u043a\u0430\u043a \u043c\u043e\u0436\u043d\u043e \u043d\u0438\u0436\u0435         if (!$this-&gt;isLeaf($root)) {             $left  = (2 * $root) + 1; \/\/ \u043b\u0435\u0432\u044b\u0439 \u043f\u043e\u0442\u043e\u043c\u043e\u043a             $right = (2 * $root) + 2; \/\/ \u043f\u0440\u0430\u0432\u044b\u0439 \u043f\u043e\u0442\u043e\u043c\u043e\u043a                           $h = $this-&gt;heap;             \/\/ \u0435\u0441\u043b\u0438 \u043a\u043e\u0440\u0435\u043d\u044c \u043c\u0435\u043d\u044c\u0448\u0435 \u0441\u0432\u043e\u0438\u0445 \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432             if (               (isset($h[$left]) &&                 $this-&gt;compare($h[$root], $h[$left]) &lt; 0)               || (isset($h[$right]) &&                 $this-&gt;compare($h[$root], $h[$right]) &lt; 0)             ) {                 \/\/ \u043d\u0430\u0445\u043e\u0434\u0438\u043c \u0441\u0442\u0430\u0440\u0448\u0435\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430                 if (isset($h[$left]) && isset($h[$right])) {                   $j = ($this-&gt;compare($h[$left], $h[$right]) &gt;= 0)                       ? $left : $right;                 }                 else if (isset($h[$left])) {                   $j = $left; \/\/ \u043b\u0435\u0432\u044b\u0439 \u043f\u043e\u0442\u043e\u043c\u043e\u043a                 }                 else {                   $j = $right; \/\/ \u043f\u0440\u0430\u0432\u044b\u0439 \u043f\u043e\u0442\u043e\u043c\u043a                 }                   \/\/ \u043c\u0435\u043d\u044f\u0435\u043c \u043c\u0435\u0441\u0442\u0430\u043c\u0438 \u0441 \u043a\u043e\u0440\u043d\u0435\u043c                 list($this-&gt;heap[$root], $this-&gt;heap[$j]) =                    array($this-&gt;heap[$j], $this-&gt;heap[$root]);                   \/\/ \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0435\u043c \u043a\u0443\u0447\u0443 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e                 \/\/ \u043d\u043e\u0432\u043e\u0433\u043e \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430 $j                 $this-&gt;adjust($j);             }         }     } } <\/code><\/pre>\n<p>  \u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u0436\u0435 \u043d\u0430\u043e\u0431\u043e\u0440\u043e\u0442, \u043f\u043e\u043b\u043d\u0430\u044f \u043f\u0440\u043e\u0442\u0438\u0432\u043e\u043f\u043e\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0438\u0437\u0432\u043b\u0435\u0447\u0435\u043d\u0438\u044e: \u043c\u044b \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432\u043d\u0438\u0437 \u043a\u0443\u0447\u0438 \u0438 \u043f\u043e\u0434\u043d\u0438\u043c\u0430\u0435\u043c \u0435\u0435 \u0434\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 \u044d\u0442\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0433\u043b\u0430\u0432\u043d\u043e\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u0435. \u0422\u0430\u043a \u043a\u0430\u043a \u043c\u044b \u0437\u043d\u0430\u0435\u043c, \u0447\u0442\u043e \u043f\u043e\u043b\u043d\u043e\u0435 \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 n\/2 + 1 \u0443\u0437\u0435\u043b, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043e\u0431\u0445\u043e\u0434\u0438\u0442\u044c \u043a\u0443\u0447\u0443 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a.<\/p>\n<pre><code class=\"php\">public function insert($item) {     \/\/ \u0432\u0441\u0442\u0430\u0432\u0438\u043c \u043d\u043e\u0432\u044b\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0432 \u043a\u043e\u043d\u0435\u0446 \u043a\u0443\u0447\u0438     $this-&gt;heap[] = $item;       \/\/ \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u0438\u043c \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u0435 \u043c\u0435\u0441\u0442\u043e     $place = $this-&gt;count();     $parent = floor($place \/ 2);     \/\/ \u043f\u043e\u043a\u0430 \u043d\u0435 \u043d\u0430 \u0432\u0435\u0440\u0448\u0438\u043d\u0435 \u0438 \u0431\u043e\u043b\u044c\u0448\u0435 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f     while (       $place &gt; 0 && $this-&gt;compare(         $this-&gt;heap[$place], $this-&gt;heap[$parent]) &gt;= 0     ) {         \/\/ \u043c\u0435\u043d\u044f\u0435\u043c \u043c\u0435\u0441\u0442\u0430\u043c\u0438         list($this-&gt;heap[$place], $this-&gt;heap[$parent]) =             array($this-&gt;heap[$parent], $this-&gt;heap[$place]);         $place = $parent;         $parent = floor($place \/ 2);     } } <\/code><\/pre>\n<p>  \u041f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0447\u0442\u043e \u0443 \u043d\u0430\u0441 \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u043e\u0441\u044c \u0438 \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u0432\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0432 \u043a\u0443\u0447\u0443:<\/p>\n<pre><code class=\"php\">&lt;?php $heap = new BinaryHeap(); $heap-&gt;insert(19); $heap-&gt;insert(36); $heap-&gt;insert(54); $heap-&gt;insert(100); $heap-&gt;insert(17); $heap-&gt;insert(3); $heap-&gt;insert(25); $heap-&gt;insert(1); $heap-&gt;insert(67); $heap-&gt;insert(2); $heap-&gt;insert(7); <\/code><\/pre>\n<p>  \u0415\u0441\u043b\u0438 \u043c\u044b \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u0432\u0441\u0435 \u044d\u0442\u043e, \u0442\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435:<\/p>\n<pre><code class=\"php\">Array (     [0] =&gt; 100     [1] =&gt; 67     [2] =&gt; 54     [3] =&gt; 36     [4] =&gt; 19     [5] =&gt; 7     [6] =&gt; 25     [7] =&gt; 1     [8] =&gt; 17     [9] =&gt; 2     [10] =&gt; 3 ) <\/code><\/pre>\n<p>  \u041a\u0430\u043a \u0432\u0438\u0434\u043d\u043e, \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u043d\u0435 \u0441\u043e\u0431\u043b\u044e\u0434\u0435\u043d \u0438 \u0432\u043e\u043e\u0431\u0449\u0435 \u044d\u0442\u043e \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0434\u0440\u0443\u0433\u043e\u0435, \u0447\u0442\u043e \u043c\u044b \u043e\u0436\u0438\u0434\u0430\u043b\u0438. \u041e\u0434\u043d\u0430\u043a\u043e \u0435\u0441\u043b\u0438 \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u043f\u043e-\u043e\u0447\u0435\u0440\u0435\u0434\u0438 \u0438\u0437\u0432\u043b\u0435\u043a\u0430\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0438\u0437 \u043a\u0443\u0447\u0438, \u0442\u043e \u0432\u0441\u0435 \u0431\u0443\u0434\u0435\u0442 \u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e:<\/p>\n<pre><code class=\"php\">&lt;?php while (!$heap-&gt;isEmpty()) {     echo $heap-&gt;extract() . &quot;n&quot;; } <\/code><\/pre>\n<pre><code class=\"html\">100 67 54 36 25 19 17 7 3 2 1 <\/code><\/pre>\n<h5>SplMaxHeap \u0438 SplMinHeap<\/h5>\n<p>  \u041a \u0441\u0447\u0430\u0441\u0442\u044c\u044e, \u0434\u043b\u044f \u043d\u0430\u0441 \u0443\u0436\u0435 \u0435\u0441\u0442\u044c \u0433\u043e\u0442\u043e\u0432\u044b\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 SplHeap, SplMaxHeap \u0438 SplMinHeap. \u0412\u0441\u0435 \u0447\u0442\u043e \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u044d\u0442\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u0443\u043d\u0430\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u044c \u0438\u0445 \u0438 \u043f\u0435\u0440\u0435\u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043c\u0435\u0442\u043e\u0434 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0442\u0430\u043a:<\/p>\n<pre><code class=\"php\">&lt;?php class MyHeap extends SplMaxHeap {     public function compare($item1, $item2) {         return (int) $item1 - $item2;     } } <\/code><\/pre>\n<p>  \u0414\u0430\u043d\u043d\u044b\u0439 \u043c\u0435\u0442\u043e\u0434 \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442 \u043b\u044e\u0431\u043e\u0435 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u0434\u0432\u0443\u0445 \u0443\u0437\u043b\u043e\u0432 \u0438 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 SplMaxHeap \u043e\u043d \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0435\u0441\u043b\u0438 $item1 \u0431\u043e\u043b\u044c\u0448\u0435 $item2, 0 \u0435\u0441\u043b\u0438 \u043e\u043d\u0438 \u0440\u0430\u0432\u043d\u044b \u0434\u0440\u0443\u0433 \u0434\u0440\u0443\u0433\u0443 \u0438 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0435, \u0435\u0441\u043b\u0438 $item2 \u0431\u043e\u043b\u044c\u0448\u0435 $item1. \u0415\u0441\u043b\u0438 \u043c\u044b \u043d\u0430\u0441\u043b\u0435\u0434\u0443\u0435\u043c SplMinHeap, \u0442\u043e \u043e\u043d \u0432\u0435\u0440\u043d\u0435\u0442 \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u0435\u0441\u043b\u0438 $item1 \u043c\u0435\u043d\u044c\u0448\u0435 $item2.<\/p>\n<p>  \u041d\u0435 \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0443\u0435\u0442\u0441\u044f \u043f\u043e\u043c\u0435\u0449\u0430\u0442\u044c \u0432 \u043a\u0443\u0447\u0443 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0438\u0445 \u043f\u043e\u0437\u0438\u0446\u0438\u044e \u0431\u0443\u0434\u0435\u0442 \u0442\u0440\u0443\u0434\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c<\/p>\n<h5>SplPriorityQueue \u2014 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u043d\u0430\u044f \u043e\u0447\u0435\u0440\u0435\u0434\u044c<\/h5>\n<p>  \u041f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u043d\u0430\u044f \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u044d\u0442\u043e \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0439 \u0430\u0431\u0441\u0442\u0440\u0430\u043a\u0442\u043d\u044b\u0439 \u0442\u0438\u043f \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0432\u0435\u0434\u0435\u0442 \u0441\u0435\u0431\u044f \u043a\u0430\u043a \u043e\u0447\u0435\u0440\u0435\u0434\u044c, \u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u0442\u0441\u044f \u043a\u0430\u043a \u043a\u0443\u0447\u0430. \u0412 \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0438 SplPriorityQueue \u044d\u0442\u043e \u0431\u0443\u0434\u0435\u0442 maxheap. \u041f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u043d\u0430\u044f \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0438\u043c\u0435\u0435\u0442 \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u043c\u043d\u043e\u0433\u043e \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0439, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0441\u0438\u0441\u0442\u0435\u043c\u0430 \u0442\u0438\u043a\u0435\u0442\u043e\u0432 \u0438\u043b\u0438 \u0441\u043f\u0440\u0430\u0432\u043e\u0447\u043d\u0430\u044f \u0441\u043b\u0443\u0436\u0431\u0430.<\/p>\n<p>  \u041a\u0430\u043a \u0438 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 SplHeap, \u043d\u0443\u0436\u043d\u043e \u043b\u0438\u0448\u044c \u0443\u043d\u0430\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u044c SplPriorityQueue \u0438 \u043f\u0435\u0440\u0435\u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043c\u0435\u0442\u043e\u0434 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f:<\/p>\n<pre><code class=\"php\">&lt;?php class PriQueue extends SplPriorityQueue {     public function compare($p1, $p2) {         if ($p1 === $p2) return 0;         \/\/ \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0432\u043e\u0437\u0440\u0430\u0441\u0442\u0430\u043d\u0438\u044f \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u0430, \u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435         \/\/ \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u0438\u0439 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442         return ($p1 &lt; $p2) ? 1 : -1;    } } <\/code><\/pre>\n<p>  \u041e\u0441\u043d\u043e\u0432\u043d\u043e\u0435 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u0432 SplPriorityQueue \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043f\u0440\u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0435, \u043f\u043e\u043c\u0438\u043c\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430, \u043e\u0436\u0438\u0434\u0430\u0435\u0442\u0441\u044f \u0435\u0449\u0435 \u0438 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442 \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430. \u041e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u0442\u044c \u043a\u0443\u0447\u0443, \u043e\u0441\u043d\u043e\u0432\u044b\u0432\u0430\u044f\u0441\u044c \u043d\u0430 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0432\u0430\u0448 \u043a\u043e\u043c\u043f\u0430\u0440\u0430\u0442\u043e\u0440.<\/p>\n<p>  \u041f\u0440\u043e\u0432\u0435\u0440\u0438\u043c \u0440\u0430\u0431\u043e\u0442\u0443 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u043d\u043e\u0439 \u043e\u0447\u0435\u0440\u0435\u0434\u0438, \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0447\u0438\u0441\u0435\u043b \u0437\u0430\u0434\u0430\u0434\u0438\u043c \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442:<\/p>\n<pre><code class=\"php\">&lt;?php $pq = new PriQueue(); $pq-&gt;insert('A', 4); $pq-&gt;insert('B', 3); $pq-&gt;insert('C', 5); $pq-&gt;insert('D', 8); $pq-&gt;insert('E', 2); $pq-&gt;insert('F', 7); $pq-&gt;insert('G', 1); $pq-&gt;insert('H', 6); $pq-&gt;insert('I', 0);    while ($pq-&gt;valid()) {     print_r($pq-&gt;current());     echo &quot;n&quot;;     $pq-&gt;next(); } <\/code><\/pre>\n<p>  \u0427\u0442\u043e \u0432 \u0438\u0442\u043e\u0433\u0435 \u0432\u044b\u0434\u0430\u0441\u0442 \u043d\u0430\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435:<\/p>\n<pre><code class=\"html\">I G E B A C H F D  <\/code><\/pre>\n<p>  \u0412 \u0434\u0430\u043d\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043d\u0430\u0448\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0438\u0434\u0443\u0442 \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0443\u0431\u044b\u0432\u0430\u043d\u0438\u044f \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u0430 \u2014 \u043e\u0442 \u0441\u0430\u043c\u043e\u0433\u043e \u0432\u044b\u0441\u043e\u043a\u043e\u0433\u043e \u043a \u0441\u0430\u043c\u043e\u043c\u0443 \u043d\u0438\u0437\u043a\u043e\u043c\u0443 (\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u2014 \u0431\u043e\u043b\u044c\u0448\u0438\u0439 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442). \u041c\u043e\u0436\u043d\u043e \u043f\u043e\u043c\u0435\u043d\u044f\u0442\u044c \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u0432\u044b\u0434\u0430\u0447\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043f\u0440\u043e\u0441\u0442\u043e \u0438\u0437\u043c\u0435\u043d\u0438\u0432 \u043c\u0435\u0442\u043e\u0434 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f, \u0447\u0442\u043e\u0431\u044b \u0442\u043e\u0442 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u043b \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u0435\u0441\u043b\u0438 $p1 \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0435\u043c $p2.<\/p>\n<p>  \u041f\u043e-\u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e, \u0438\u0437\u0432\u043b\u0435\u043a\u0430\u0435\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430. \u0415\u0441\u043b\u0438 \u043d\u0443\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0430\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u0430, \u0438\u043b\u0438 \u0436\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0438 \u0438\u0445 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442, \u043d\u0443\u0436\u043d\u043e \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u0444\u043b\u0430\u0433 \u0438\u0437\u0432\u043b\u0435\u0447\u0435\u043d\u0438\u044f:<\/p>\n<pre><code class=\"php\">&lt;?php \/\/ \u0438\u0437\u0432\u043b\u0435\u0447\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442 $pq-&gt;setExtractFlags(SplPriorityQueue::EXTR_PRIORITY);   \/\/ \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0438 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442 (\u0432\u043e\u0437\u0432\u0440\u0430\u0442\u0438\u0442 \u0430\u0441\u0441\u043e\u0446\u0438\u0430\u0442\u0438\u0432\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \/\/ \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430) $pq-&gt;setExtractFlags(SplPriorityQueue::EXTR_BOTH); <\/code><\/pre>\n<h5>\u0413\u0440\u0430\u0444\u044b<\/h5>\n<p>  \u0417\u0430 \u0433\u0440\u0430\u0444\u0430\u043c\u0438 \u0441\u0442\u043e\u0438\u0442 \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u043c\u043d\u043e\u0433\u043e \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0439 \u2014 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0441\u0435\u0442\u0435\u0439, \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0438\u0437\u0430\u0446\u0438\u044f \u0438\u043b\u0438 \u0436\u0435 \u0430\u043d\u0430\u043b\u0438\u0437 \u0441\u043e\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0445 \u0441\u0435\u0442\u0435\u0439. Google PageRank, \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0446\u0438\u0438 \u043e\u0442 Amazon \u2014 \u0432\u043e\u0442 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u0440\u0438\u043c\u0435\u0440\u044b \u0438\u0445 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f. \u0412 \u044d\u0442\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u0441\u0442\u0430\u0442\u044c\u0438 \u044f \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u044e \u043e\u0431\u044a\u044f\u0441\u043d\u0438\u0442\u044c \u0434\u0432\u0435 \u0437\u0430\u0434\u0430\u0447\u0438, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043e\u043d\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u2014 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u043f\u043e\u0438\u0441\u043a\u0430 \u043a\u043e\u0440\u043e\u0442\u043a\u043e\u0433\u043e \u043f\u0443\u0442\u0438 \u0438 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0447\u0438\u0441\u043b\u043e \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043e\u043a.<\/p>\n<p>  \u0413\u0440\u0430\u0444 \u2014 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u044f, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0430\u044f \u0434\u043b\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0439 \u043c\u0435\u0436\u0434\u0443 \u043f\u0430\u0440\u0430\u043c\u0438 \u043a\u043b\u044e\u0447-\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u0413\u0440\u0430\u0444 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u043d\u0430\u0431\u043e\u0440\u0430 \u0432\u0435\u0440\u0448\u0438\u043d (\u0443\u0437\u043b\u043e\u0432) \u0438 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0441\u0432\u044f\u0437\u0435\u0439 \u043c\u0435\u0436\u0434\u0443 \u0443\u0437\u043b\u0430\u043c\u0438, \u0441\u043e\u0435\u0434\u0438\u043d\u044f\u044e\u0449\u0438\u0445 \u0438\u0445 \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0431\u043e\u0439. \u042d\u0442\u0438 \u0441\u0432\u044f\u0437\u0438 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u043c\u0438 (\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c\u0438) \u0438 \u043d\u0435\u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u043c\u0438. \u041d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u0430\u044f \u0441\u0432\u044f\u0437\u044c \u044d\u0442\u043e \u0441\u0432\u044f\u0437\u044c \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u0443\u0437\u043b\u0430\u043c\u0438 \u0438 \u0441\u0432\u044f\u0437\u044c A\u2192B \u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0442\u0435\u043c \u0436\u0435 \u0441\u0430\u043c\u044b\u043c, \u0447\u0442\u043e \u0438 B\u2192A. \u041d\u0435\u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u0430\u044f \u0436\u0435 \u0441\u0432\u044f\u0437\u044c \u043d\u0435 \u0438\u043c\u0435\u0435\u0442 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f, \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0441\u0432\u044f\u0437\u0438 A-B \u0438 B-A \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0438\u0434\u0435\u043d\u0442\u0438\u0447\u043d\u044b\u043c\u0438. \u041e\u0441\u043d\u043e\u0432\u044b\u0432\u0430\u044f\u0441\u044c \u043d\u0430 \u044d\u0442\u0438\u0445 \u043f\u0440\u0430\u0432\u0438\u043b\u0430\u0445 \u043c\u043e\u0436\u043d\u043e \u0441\u043a\u0430\u0437\u0430\u0442\u044c, \u0447\u0442\u043e \u0434\u0435\u0440\u0435\u0432\u044c\u044f \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043e\u0434\u043d\u0438\u043c \u0438\u0437 \u043d\u0435\u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0445 \u0433\u0440\u0430\u0444\u043e\u0432, \u0433\u0434\u0435 \u043a\u0430\u0436\u0434\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0441\u043e\u0435\u0434\u0438\u043d\u0435\u043d\u0430 \u0441 \u043e\u0434\u043d\u0438\u043c \u0438\u0437 \u0443\u0437\u043b\u043e\u0432 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0441\u0432\u044f\u0437\u044c\u044e.<\/p>\n<p>  \u0413\u0440\u0430\u0444\u044b \u0442\u0430\u043a\u0436\u0435 \u043c\u043e\u0433\u0443\u0442 \u0438\u043c\u0435\u0442\u044c \u0432\u0435\u0441. \u0412\u0437\u0432\u0435\u0448\u0435\u043d\u043d\u044b\u0439 \u0433\u0440\u0430\u0444, \u0438\u043b\u0438 \u0441\u0435\u0442\u044c \u2014 \u0433\u0440\u0430\u0444, \u0443 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u0441\u0432\u044f\u0437\u0438 \u0443\u043a\u0430\u0437\u0430\u043d \u0432\u0435\u0441 (\u00ab\u0446\u0435\u043d\u0430\u00bb \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0430 \u0438\u0437 \u0443\u0437\u043b\u0430 A \u0432 \u0443\u0437\u0435\u043b B). \u0422\u0430\u043a\u0438\u0435 \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u0438 \u0448\u0438\u0440\u043e\u043a\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0434\u043b\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u0443\u0442\u0438, \u0438\u043b\u0438 \u0436\u0435 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u00ab\u0434\u0435\u0448\u0435\u0432\u043e\u0433\u043e\u00bb \u043f\u0443\u0442\u0438 \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u0442\u043e\u0447\u043a\u0430\u043c\u0438. \u041f\u0440\u043e\u043a\u043b\u0430\u0434\u043a\u0430 \u043f\u0443\u0442\u0438 \u0432 GoogleMap \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0438\u043c\u0435\u043d\u043d\u043e \u0432\u0437\u0432\u0435\u0448\u0435\u043d\u043d\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430. <\/p>\n<h5>\u041c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043e\u043a (\u043f\u0440\u044b\u0436\u043a\u043e\u0432)<\/h5>\n<p>  \u041e\u0431\u0449\u0435\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435 \u0442\u0435\u043e\u0440\u0438\u0438 \u0433\u0440\u0430\u0444\u043e\u0432 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u043f\u0440\u0438 \u043f\u043e\u0438\u0441\u043a\u0435 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043e\u043a \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u0443\u0437\u043b\u0430\u043c\u0438. \u0427\u0442\u043e \u043a\u0430\u0441\u0430\u0435\u0442\u0441\u044f \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432, \u0442\u043e \u0437\u0434\u0435\u0441\u044c \u0433\u0440\u0430\u0444\u044b \u043f\u043e\u043c\u043e\u0433\u0430\u044e\u0442 \u0432 \u043e\u0431\u0445\u043e\u0434\u0435 \u0434\u0435\u0440\u0435\u0432\u0430 \u0432 \u043e\u0434\u043d\u043e\u043c \u0438\u0437 \u0434\u0432\u0443\u0445 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0439 \u2014 \u0432 \u0433\u043b\u0443\u0431\u0438\u043d\u0443 \u0438\u043b\u0438 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443. \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0432 \u043f\u0440\u043e\u0448\u043b\u044b\u0439 \u0440\u0430\u0437 \u043c\u044b \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u043b\u0438 \u043f\u043e\u0438\u0441\u043a \u0432 \u0433\u043b\u0443\u0431\u0438\u043d\u0443, \u0442\u043e \u0441\u0435\u0439\u0447\u0430\u0441 \u0432\u0437\u0433\u043b\u044f\u043d\u0435\u043c \u043d\u0430 \u0434\u0440\u0443\u0433\u043e\u0439 \u043c\u0435\u0442\u043e\u0434.<\/p>\n<p>  \u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0433\u0440\u0430\u0444:<\/p>\n<p>  <img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/622\/6f0\/1ce\/6226f01ce17bb719f81589b1df422560.png\" alt=\"image\"\/><\/p>\n<p>  \u0414\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b \u0443\u0441\u043b\u043e\u0432\u0438\u043c\u0441\u044f, \u0447\u0442\u043e \u0434\u0430\u043d\u043d\u044b\u0439 \u0433\u0440\u0430\u0444 \u043d\u0435\u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0439. \u0417\u0430\u0434\u0430\u0447\u0430 \u2014 \u043d\u0430\u0439\u0442\u0438 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043e\u043a \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u043b\u044e\u0431\u044b\u043c\u0438 \u0443\u0437\u043b\u0430\u043c\u0438. \u041f\u0440\u0438 \u043f\u043e\u0438\u0441\u043a\u0435 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 \u043c\u044b \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u0441 \u043a\u043e\u0440\u043d\u044f (\u043d\u0443 \u0438\u043b\u0438 \u0441 \u0434\u0440\u0443\u0433\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u044b \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043b\u0438 \u043a\u0430\u043a \u043a\u043e\u0440\u0435\u043d\u044c) \u0438 \u0441\u043f\u0443\u0441\u043a\u0430\u0435\u043c\u0441\u044f \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443 \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u0437\u0430 \u0443\u0440\u043e\u0432\u043d\u0435\u043c. \u0427\u0442\u043e\u0431\u044b \u044d\u0442\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u0430 \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0434\u043b\u044f \u043e\u0440\u0433\u0430\u043d\u0438\u0437\u0430\u0446\u0438\u0438 \u0441\u043f\u0438\u0441\u043a\u0430 \u0443\u0437\u043b\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u044b \u0435\u0449\u0435 \u043d\u0435 \u043e\u0431\u043e\u0448\u043b\u0438, \u0447\u0442\u043e\u0431\u044b \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0442\u044c\u0441\u044f \u043a \u043d\u0435\u043c\u0443 \u0438 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c \u0435\u0433\u043e \u043a\u0430\u0436\u0434\u044b\u0439 \u0443\u0440\u043e\u0432\u0435\u043d\u044c. \u041e\u0431\u0449\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0442\u0430\u043a\u043e\u0439:<\/p>\n<ul>\n<li>1. \u0421\u043e\u0437\u0434\u0430\u0442\u044c \u043e\u0447\u0435\u0440\u0435\u0434\u044c<\/li>\n<li>2. \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0442\u0443\u0434\u0430 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0438 \u043f\u043e\u043c\u0435\u0447\u0430\u0435\u043c \u0435\u0433\u043e \u043a\u0430\u043a \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0439<\/li>\n<li>3. \u0414\u043e \u0442\u0435\u0445 \u043f\u043e\u0440 \u043f\u043e\u043a\u0430 \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u043d\u0435 \u043f\u0443\u0441\u0442\u0430:<\/li>\n<li>\n<ul>\n<li> 3a. \u0438\u0437\u0432\u043b\u0435\u043a\u0430\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0443\u0437\u0435\u043b<\/li>\n<li> 3b. \u0435\u0441\u043b\u0438 \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0443\u0437\u0435\u043b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0438\u0441\u043a\u043e\u043c\u044b\u043c \u2014 \u043e\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c\u0441\u044f<\/li>\n<li> 3c. \u0438\u043d\u0430\u0447\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u0435\u043c \u0432 \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u043a\u0430\u0436\u0434\u044b\u0439 \u043d\u0435\u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0439 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0439 \u0443\u0437\u0435\u043b \u0438 \u043f\u043e\u043c\u0435\u0447\u0430\u0435\u043c \u0435\u0433\u043e \u043a\u0430\u043a \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0439<\/li>\n<\/ul>\n<p>  <\/li>\n<\/ul>\n<p>  \u041d\u043e \u043a\u0430\u043a \u043c\u044b \u0443\u0437\u043d\u0430\u0435\u043c \u043a\u0430\u043a\u0438\u0435 \u0443\u0437\u043b\u044b \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u0438\u043b\u0438 \u043d\u0435\u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0435 \u043d\u0435 \u043f\u0440\u0438\u0431\u0435\u0433\u0430\u044f \u043a \u043e\u0431\u0445\u043e\u0434\u0443 \u0433\u0440\u0430\u0444\u0430? \u042d\u0442\u043e \u043f\u043e\u0434\u0432\u043e\u0434\u0438\u0442 \u043d\u0430\u0441 \u043a \u0432\u043e\u043f\u0440\u043e\u0441\u0443 \u043e \u0442\u043e\u043c, \u043a\u0430\u043a \u0433\u0440\u0430\u0444\u044b \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0441\u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u044b.<\/p>\n<h5>\u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0433\u0440\u0430\u0444\u0430<\/h5>\n<p>  \u041e\u0431\u044b\u0447\u043d\u043e, \u0433\u0440\u0430\u0444\u044b \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0434\u0432\u0443\u043c\u044f \u0441\u043f\u043e\u0441\u043e\u0431\u0430\u043c\u0438 \u2014 \u0442\u0430\u0431\u043b\u0438\u0446\u0430 \u0438\u043b\u0438 \u043c\u0430\u0442\u0440\u0438\u0446\u0430, \u0433\u0434\u0435 \u043e\u043f\u0438\u0441\u0430\u043d\u044b \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u0443\u0437\u043b\u044b. <br \/>  \u0412\u043e\u0442 \u043a\u0430\u043a \u044d\u0442\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0434\u043b\u044f \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u0440\u0430:<\/p>\n<p>  <img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/795\/094\/f63\/795094f6383974072090ac9b6f5b6ab1.png\" alt=\"image\"\/> <img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/67b\/a5d\/a12\/67ba5da126ad9801db231e107b9decd1.png\" alt=\"image\"\/><\/p>\n<p>  \u0412 \u043c\u0430\u0442\u0440\u0438\u0446\u0435, \u043d\u0430 \u043f\u0435\u0440\u0435\u0441\u0435\u0447\u0435\u043d\u0438\u0438 \u0443\u0437\u043b\u043e\u0432 \u0441\u0442\u0430\u0432\u0438\u0442\u0441\u044f \u00ab1\u00bb, \u0435\u0441\u043b\u0438 \u0443\u0437\u043b\u044b \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0441\u043e\u0441\u0435\u0434\u044f\u043c\u0438.<\/p>\n<p>  \u0421\u043f\u0438\u0441\u043e\u043a \u0443\u0434\u043e\u0431\u0435\u043d \u0432 \u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u0435\u0441\u043b\u0438 \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u0432\u0435\u0440\u0448\u0438\u043d \u043d\u0435 \u0438\u043c\u0435\u044e\u0442 \u0441\u0432\u044f\u0437\u0435\u0439 \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0431\u043e\u0439, \u043c\u0430\u0442\u0440\u0438\u0446\u0430 \u0436\u0435 \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0430\u0435\u0442 \u0431\u043e\u043b\u0435\u0435 \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u043f\u043e\u0438\u0441\u043a. \u0412 \u043a\u043e\u043d\u0446\u0435 \u043a\u043e\u043d\u0446\u043e\u0432 \u0432\u0438\u0434 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0433\u0440\u0430\u0444\u0430 \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0442\u043e\u0433\u043e, \u043a\u0430\u043a\u0438\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0441 \u0433\u0440\u0430\u0444\u043e\u043c \u0431\u0443\u0434\u0443\u0442 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u044c\u0441\u044f. \u041c\u044b \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u0441\u043f\u0438\u0441\u043a\u043e\u043c.<\/p>\n<pre><code class=\"php\">&lt;?php $graph = array(   'A' =&gt; array('B', 'F'),   'B' =&gt; array('A', 'D', 'E'),   'C' =&gt; array('F'),   'D' =&gt; array('B', 'E'),   'E' =&gt; array('B', 'D', 'F'),   'F' =&gt; array('A', 'E', 'C'), ); <\/code><\/pre>\n<p>  \u0418 \u043d\u0430\u043f\u0438\u0448\u0435\u043c \u043d\u0430\u0448 \u043f\u043e\u0438\u0441\u043a \u0432 \u0448\u0438\u0440\u0438\u043d\u0443:<\/p>\n<pre><code class=\"php\">&lt;?php class Graph {   protected $graph;   protected $visited = array();     public function __construct($graph) {     $this-&gt;graph = $graph;   }     \/\/ \u043d\u0430\u0439\u0434\u0435\u043c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u043f\u0440\u044b\u0436\u043a\u043e\u0432 (\u0441\u0432\u044f\u0437\u0435\u0439) \u043c\u0435\u0436\u0434\u0443 2 \u0443\u0437\u043b\u0430\u043c\u0438    public function breadthFirstSearch($origin, $destination) {     \/\/ \u043f\u043e\u043c\u0435\u0442\u0438\u043c \u0432\u0441\u0435 \u0443\u0437\u043b\u044b \u043a\u0430\u043a \u043d\u0435\u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0435     foreach ($this-&gt;graph as $vertex =&gt; $adj) {       $this-&gt;visited[$vertex] = false;     }       \/\/ \u043f\u0443\u0441\u0442\u0430\u044f \u043e\u0447\u0435\u0440\u0435\u0434\u044c     $q = new SplQueue();       \/\/ \u0434\u043e\u0431\u0430\u0432\u0438\u043c \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u0443\u044e \u0432\u0435\u0440\u0448\u0438\u043d\u0443 \u0432 \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0438 \u043f\u043e\u043c\u0435\u0442\u0438\u043c \u0435\u0435 \u043a\u0430\u043a \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u0443\u044e     $q-&gt;enqueue($origin);     $this-&gt;visited[$origin] = true;       \/\/ \u044d\u0442\u043e \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u0437\u0430\u043f\u0438\u0441\u0438 \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u0433\u043e \u043f\u0443\u0442\u0438 \u043e\u0442 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0437\u043b\u0430     $path = array();     $path[$origin] = new SplDoublyLinkedList();     $path[$origin]-&gt;setIteratorMode(       SplDoublyLinkedList::IT_MODE_FIFO|SplDoublyLinkedList::IT_MODE_KEEP     );       $path[$origin]-&gt;push($origin);       $found = false;     \/\/ \u043f\u043e\u043a\u0430 \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u043d\u0435 \u043f\u0443\u0441\u0442\u0430 \u0438 \u043f\u0443\u0442\u044c \u043d\u0435 \u043d\u0430\u0439\u0434\u0435\u043d     while (!$q-&gt;isEmpty() && $q-&gt;bottom() != $destination) {       $t = $q-&gt;dequeue();         if (!empty($this-&gt;graph[$t])) {         \/\/ \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0441\u043e\u0441\u0435\u0434\u043d\u0435\u0433\u043e \u0443\u0437\u043b\u0430         foreach ($this-&gt;graph[$t] as $vertex) {           if (!$this-&gt;visited[$vertex]) {             \/\/ \u0435\u0441\u043b\u0438 \u0432\u0441\u0435 \u0435\u0449\u0435 \u043d\u0435 \u043f\u043e\u0441\u0435\u0449\u0435\u043d, \u0442\u043e \u0434\u043e\u0431\u0430\u0432\u0438\u043c \u0432 \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0438 \u043e\u0442\u043c\u0435\u0442\u0438\u043c             $q-&gt;enqueue($vertex);             $this-&gt;visited[$vertex] = true;             \/\/ \u0434\u043e\u0431\u0430\u0432\u0438\u043c \u0443\u0437\u0435\u043b \u043a \u0442\u0435\u043a\u0443\u0449\u0435\u043c\u0443 \u043f\u0443\u0442\u0438             $path[$vertex] = clone $path[$t];             $path[$vertex]-&gt;push($vertex);           }         }       }     }       if (isset($path[$destination])) {       echo &quot;\u0438\u0437 $origin \u0432 $destination \u0437\u0430 &quot;,          count($path[$destination]) - 1,         &quot; \u043f\u0440\u044b\u0436\u043a\u043e\u0432&quot;;       $sep = '';       foreach ($path[$destination] as $vertex) {         echo $sep, $vertex;         $sep = '-&gt;';       }       echo &quot;n&quot;;     }     else {       echo &quot;\u041d\u0435\u0442 \u043f\u0443\u0442\u0438 \u0438\u0437 $origin \u0432 $destinationn&quot;;     }   } } <\/code><\/pre>\n<p>  \u0417\u0430\u043f\u0443\u0441\u0442\u0438\u0432 \u044d\u0442\u043e\u0442 \u043f\u0440\u0438\u043c\u0435\u0440 \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435:<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0412\u0437\u0433\u043b\u044f\u043d\u0443\u0442\u044c \u043d\u0430 \u0433\u0440\u0430\u0444 \u0435\u0449\u0435 \u0440\u0430\u0437<\/b><\/p>\n<div class=\"spoiler_text\"><img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/622\/6f0\/1ce\/6226f01ce17bb719f81589b1df422560.png\" alt=\"image\"\/><\/div>\n<\/div>\n<pre><code class=\"php\">&lt;?php $g = new Graph($graph);   \/\/ \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0448\u0430\u0433\u043e\u0432 \u0438\u0437 D \u0432 C $g-&gt;breadthFirstSearch('D', 'C'); \/\/ \u0432\u044b\u0432\u043e\u0434: \/\/ \u0438\u0437 D \u0432 C \u0437\u0430 3 \u0448\u0430\u0433\u0430 \/\/ D-&gt;E-&gt;F-&gt;C   \/\/ \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0448\u0430\u0433\u043e\u0432 \u0438\u0437 B \u0432 F $g-&gt;breadthFirstSearch('B', 'F'); \/\/ \u0432\u044b\u0432\u043e\u0434: \/\/ \u0438\u0437 B \u0432 F \u0437\u0430 2 \u0448\u0430\u0433\u0430 \/\/ B-&gt;A-&gt;F   \/\/ \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0448\u0430\u0433\u043e\u0432 \u0438\u0437 A \u0432 C $g-&gt;breadthFirstSearch('A', 'C'); \/\/ \u0432\u044b\u0432\u043e\u0434: \/\/ \u0438\u0437 A \u0432 C \u0437\u0430 2 \u0448\u0430\u0433\u0430 \/\/ A-&gt;F-&gt;C   \/\/ \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0448\u0430\u0433\u043e\u0432 \u0438\u0437 A \u0432 G $g-&gt;breadthFirstSearch('A', 'G'); \/\/ \u0432\u044b\u0432\u043e\u0434: \/\/ \u041f\u0443\u0442\u0438 \u0438\u0437 A \u0432 G \u043d\u0435\u0442 <\/code><\/pre>\n<p>  \u0415\u0441\u043b\u0438 \u0431\u044b \u043c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b\u0438 \u0441\u0442\u0435\u043a \u0432\u043c\u0435\u0441\u0442\u043e \u043e\u0447\u0435\u0440\u0435\u0434\u0438, \u0442\u043e \u043e\u0431\u0445\u043e\u0434 \u0441\u0442\u0430\u043b \u0431\u044b \u0432 \u0433\u043b\u0443\u0431\u0438\u043d\u0443.<\/p>\n<h5>\u041f\u043e\u0438\u0441\u043a \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u0443\u0442\u0438<\/h5>\n<p>  \u0414\u0440\u0443\u0433\u0430\u044f \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u043d\u0430\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u044d\u0442\u043e \u043f\u043e\u0438\u0441\u043a \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u0443\u0442\u0438 \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u043b\u044e\u0431\u044b\u043c\u0438 \u0443\u0437\u043b\u0430\u043c\u0438. \u0427\u0443\u0442\u044c \u0440\u0430\u043d\u044c\u0448\u0435 \u044f \u0443\u0436\u0435 \u0433\u043e\u0432\u043e\u0440\u0438\u043b \u043f\u0440\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u0432 GoogleMaps \u043a\u0430\u043a \u043f\u0440\u0438\u043c\u0435\u0440 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438. \u041a\u0430\u043a \u0432\u0430\u0440\u0438\u0430\u043d\u0442, \u0434\u0430\u043d\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u043a \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0438\u0437\u0430\u0446\u0438\u0438, \u0443\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044e \u0434\u043e\u0440\u043e\u0436\u043d\u044b\u043c \u0442\u0440\u0430\u0444\u0438\u043a\u043e\u043c \u0438 \u0442\u0430\u043a \u0434\u0430\u043b\u0435\u0435.<\/p>\n<p>  \u041e\u0434\u0438\u043d \u0438\u0437 \u0437\u043d\u0430\u043c\u0435\u043d\u0438\u0442\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432, \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0445 \u043d\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0434\u0430\u043d\u043d\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u0431\u044b\u043b \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043d \u0432 1959 \u0433\u043e\u0434\u0443 29-\u043b\u0435\u0442\u043d\u0438\u043c \u0443\u0447\u0435\u043d\u044b\u043c \u043f\u043e \u0438\u043c\u0435\u043d\u0438 <a href=\"http:\/\/ru.wikipedia.org\/wiki\/\u0414\u0435\u0439\u043a\u0441\u0442\u0440\u0430,_\u042d\u0434\u0441\u0433\u0435\u0440_\u0412\u0438\u0431\u0435\">\u042d\u0434\u0441\u0433\u0435\u0440 \u0412\u0438\u0431\u0435 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u0430<\/a>. \u0423\u0437\u043d\u0430\u0442\u044c \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u0435\u0435 \u043f\u0440\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043c\u043e\u0436\u043d\u043e \u0432 <a href=\"http:\/\/ru.wikipedia.org\/wiki\/\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c_\u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b\">\u0432\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u0438<\/a> \u0438\u043b\u0438 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u043d\u0430 \u043d\u0435\u0433\u043e \u0432 <a href=\"http:\/\/habrahabr.ru\/post\/111361\/\">\u0445\u0430\u0431\u0440\u0430\u043f\u043e\u0441\u0442\u0435<\/a> \u043e\u0442 <a href=\"http:\/\/habrahabr.ru\/users\/splitface\/\" class=\"user_link\">splitface<\/a>. \u0412 \u043e\u0431\u0449\u0438\u0445 \u0436\u0435 \u0447\u0435\u0440\u0442\u0430\u0445, \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b \u0441\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u043a \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0435 \u043a\u0430\u0436\u0434\u043e\u0439 \u0441\u0432\u044f\u0437\u0438 \u043c\u0435\u0436\u0434\u0443 \u0432\u0441\u0435\u043c\u0438 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u043c\u0438 \u043f\u0430\u0440\u0430\u043c\u0438 \u0443\u0437\u043b\u043e\u0432, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u043e\u0442 \u0441\u0442\u0430\u0440\u0442\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u0438 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u044f \u043e\u0431\u043d\u043e\u0432\u043b\u0435\u043d\u043d\u044b\u043c \u043d\u0430\u0431\u043e\u0440 \u0443\u0437\u043b\u043e\u0432 \u0441 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0439 \u0434\u0438\u0441\u0442\u0430\u043d\u0446\u0438\u0435\u0439, \u043f\u043e\u043a\u0430 \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0443\u0437\u0435\u043b \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u0434\u043e\u0441\u0442\u0438\u0433\u043d\u0443\u0442, \u0435\u0441\u043b\u0438 \u044d\u0442\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e.<\/p>\n<p>  \u0415\u0441\u0442\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u0432 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f, \u0430 \u0442\u0430\u043a\u0436\u0435 \u0438\u0445 \u0434\u043e\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f. \u041d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0438\u0437 \u043d\u0438\u0445 \u0443\u043b\u0443\u0447\u0448\u0430\u043b\u0438 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c, \u0430 \u0434\u0440\u0443\u0433\u0438\u0435 \u043b\u0438\u0448\u044c \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u043b\u0438 \u043d\u0430 \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043a\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043e\u043d\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0441 \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0432\u0437\u0432\u0435\u0448\u0435\u043d\u043d\u044b\u043c\u0438 \u0433\u0440\u0430\u0444\u0430\u043c\u0438 \u2014 \u0442\u0430\u043a\u0438\u043c\u0438, \u0433\u0434\u0435 \u043d\u0435\u0442 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0432\u0435\u0441\u043e\u0432 \u0443 \u0441\u0432\u044f\u0437\u0435\u0439.<\/p>\n<p>  \u0414\u043b\u044f \u043f\u0440\u0438\u043c\u0435\u0440\u0430 \u0432\u043e\u0437\u044c\u043c\u0435\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u0433\u0440\u0430\u0444 \u0438 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u043c \u0435\u0433\u043e \u0447\u0435\u0440\u0435\u0437 \u0441\u043f\u0438\u0441\u043e\u043a, \u0433\u0434\u0435 \u0443\u043a\u0430\u0436\u0435\u043c \u0441\u0432\u044f\u0437\u0438 \u0443\u0437\u043b\u043e\u0432 \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0431\u043e\u0439:<\/p>\n<p>  <img decoding=\"async\" src=\"http:\/\/habr.habrastorage.org\/post_images\/740\/6b2\/a52\/7406b2a5243a27028e5db2cf8f2a9fe1.png\" alt=\"image\"\/><\/p>\n<pre><code class=\"php\">&lt;?php $graph = array(   'A' =&gt; array('B' =&gt; 3, 'D' =&gt; 3, 'F' =&gt; 6),   'B' =&gt; array('A' =&gt; 3, 'D' =&gt; 1, 'E' =&gt; 3),   'C' =&gt; array('E' =&gt; 2, 'F' =&gt; 3),   'D' =&gt; array('A' =&gt; 3, 'B' =&gt; 1, 'E' =&gt; 1, 'F' =&gt; 2),   'E' =&gt; array('B' =&gt; 3, 'C' =&gt; 2, 'D' =&gt; 1, 'F' =&gt; 5),   'F' =&gt; array('A' =&gt; 6, 'C' =&gt; 3, 'D' =&gt; 2, 'E' =&gt; 5), ); <\/code><\/pre>\n<p>  \u0420\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u043d\u043e\u0439 \u043e\u0447\u0435\u0440\u0435\u0434\u0438 \u0434\u043b\u044f \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u0441\u043f\u0438\u0441\u043a\u0430 \u0432\u0441\u0435\u0445 \u00ab\u043d\u0435\u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445\u00bb \u0443\u0437\u043b\u043e\u0432:<\/p>\n<pre><code class=\"php\">&lt;?php class Dijkstra {   protected $graph;     public function __construct($graph) {     $this-&gt;graph = $graph;   }     public function shortestPath($source, $target) {     \/\/ \u043c\u0430\u0441\u0441\u0438\u0432 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0445 \u043f\u0443\u0442\u0435\u0439 \u043a \u043a\u0430\u0436\u0434\u043e\u043c\u0443 \u0443\u0437\u043b\u0443     $d = array();     \/\/ \u043c\u0430\u0441\u0441\u0438\u0432 &quot;\u043f\u0440\u0435\u0434\u0448\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u0438\u043a\u043e\u0432&quot; \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0437\u043b\u0430     $pi = array();     \/\/ \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0432\u0441\u0435\u0445 \u043d\u0435\u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432     $Q = new SplPriorityQueue();       foreach ($this-&gt;graph as $v =&gt; $adj) {       $d[$v] = INF; \/\/ \u0443\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043a\u0430\u043a \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0441\u0442\u044c       $pi[$v] = null; \/\/ \u043d\u0438\u043a\u0430\u043a\u0438\u0445 \u0443\u0437\u043b\u043e\u0432 \u043f\u043e\u0437\u0430\u0434\u0438 \u043d\u0435\u0442       foreach ($adj as $w =&gt; $cost) {         \/\/ \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u0446\u0435\u043d\u043e\u0439 \u0441\u0432\u044f\u0437\u0438 \u043a\u0430\u043a \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u043e\u043c         $Q-&gt;insert($w, $cost);       }     }       \/\/ \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u0430\u044f \u0434\u0438\u0441\u0442\u0430\u043d\u0446\u0438\u044f \u043d\u0430 \u0441\u0442\u0430\u0440\u0442\u043e\u0432\u043e\u043c \u0443\u0437\u043b\u0435 - 0     $d[$source] = 0;       while (!$Q-&gt;isEmpty()) {       \/\/ \u0438\u0437\u0432\u043b\u0435\u0447\u0435\u043c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u0443\u044e \u0446\u0435\u043d\u0443       $u = $Q-&gt;extract();       if (!empty($this-&gt;graph[$u])) {         \/\/ \u043f\u0440\u043e\u0439\u0434\u0435\u043c\u0441\u044f \u043f\u043e \u0432\u0441\u0435\u043c \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u043c \u0443\u0437\u043b\u0430\u043c         foreach ($this-&gt;graph[$u] as $v =&gt; $cost) {           \/\/ \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u043c \u043d\u043e\u0432\u0443\u044e \u0434\u043b\u0438\u043d\u0443 \u043f\u0443\u0442\u0438 \u0434\u043b\u044f \u0441\u043e\u0441\u0435\u0434\u043d\u0435\u0433\u043e \u0443\u0437\u043b\u0430           $alt = $d[$u] + $cost;           \/\/ \u0435\u0441\u043b\u0438 \u043e\u043d \u043e\u043a\u0430\u0437\u0430\u043b\u0441\u044f \u043a\u043e\u0440\u043e\u0447\u0435           if ($alt &lt; $d[$v]) {             $d[$v] = $alt; \/\/ update minimum length to vertex \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u043c \u043a\u0430\u043a \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0434\u043e \u044d\u0442\u043e\u0433\u043e \u0443\u0437\u043b\u0430             $pi[$v] = $u;  \/\/ \u0434\u043e\u0431\u0430\u0432\u0438\u043c \u0441\u043e\u0441\u0435\u0434\u0430 \u043a\u0430\u043a \u043f\u0440\u0435\u0434\u0448\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u044d\u0442\u043e\u043c\u0443 \u0443\u0437\u043b\u0430           }         }       }     }       \/\/ \u0442\u0435\u043f\u0435\u0440\u044c \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043d\u0430\u0439\u0442\u0438 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0443\u0442\u044c     \/\/ \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043e\u0431\u0440\u0430\u0442\u043d\u044b\u0439 \u043f\u0440\u043e\u0445\u043e\u0434     $S = new SplStack(); \/\/ \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u043a\u0430\u043a \u0441\u0442\u0435\u043a     $u = $target;     $dist = 0;     \/\/ \u043f\u0440\u043e\u0445\u043e\u0434 \u043e\u0442 \u0446\u0435\u043b\u0435\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0434\u043e \u0441\u0442\u0430\u0440\u0442\u043e\u0432\u043e\u0433\u043e     while (isset($pi[$u]) && $pi[$u]) {       $S-&gt;push($u);       $dist += $this-&gt;graph[$u][$pi[$u]]; \/\/ \u0434\u043e\u0431\u0430\u0432\u0438\u043c \u0434\u0438\u0441\u0442\u0430\u043d\u0446\u0438\u044e \u0434\u043b\u044f \u043f\u0440\u0435\u0434\u0448\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445       $u = $pi[$u];     }       \/\/ \u0441\u0442\u0435\u043a \u0431\u0443\u0434\u0435\u0442 \u043f\u0443\u0441\u0442\u043e\u0439, \u0435\u0441\u043b\u0438 \u043d\u0435\u0442 \u043f\u0443\u0442\u0438 \u043d\u0430\u0437\u0430\u0434     if ($S-&gt;isEmpty()) {       echo &quot;\u041d\u0435\u0442 \u043f\u0443\u0442\u0438 \u0438\u0437 $source \u0432 $targetn&quot;;     }     else {       \/\/ \u0434\u043e\u0431\u0430\u0432\u0438\u043c \u0441\u0442\u0430\u0440\u0442\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u0438 \u043f\u043e\u043a\u0430\u0436\u0435\u043c \u0432\u0435\u0441\u044c \u043f\u0443\u0442\u044c        \/\/ \u0432 \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u043c (LIFO) \u043f\u043e\u0440\u044f\u0434\u043a\u0435       $S-&gt;push($source);       echo &quot;$dist:&quot;;       $sep = '';       foreach ($S as $v) {         echo $sep, $v;         $sep = '-&gt;';       }       echo &quot;n&quot;;     }   } } <\/code><\/pre>\n<p>  \u041c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b \u2014 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443. \u0412\u0435\u0440\u043d\u0435\u043c\u0441\u044f \u043a \u043f\u0440\u0438\u043c\u0435\u0440\u0443 \u0438 \u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u0435\u0433\u043e:<\/p>\n<pre><code class=\"php\">&lt;?php $g = new Dijkstra($graph);   $g-&gt;shortestPath('D', 'C');  \/\/ 3:D-&gt;E-&gt;C $g-&gt;shortestPath('C', 'A');  \/\/ 6:C-&gt;E-&gt;D-&gt;A $g-&gt;shortestPath('B', 'F');  \/\/ 3:B-&gt;D-&gt;F $g-&gt;shortestPath('F', 'A');  \/\/ 5:F-&gt;D-&gt;A  $g-&gt;shortestPath('A', 'G');  \/\/ \u041d\u0435\u0442 \u043f\u0443\u0442\u0438 \u0438\u0437 A \u0432 G <\/code><\/pre>\n<p>  \u0412\u0441\u0435. \u041d\u0430 \u044d\u0442\u043e\u043c, \u0441\u0443\u0434\u044f \u043f\u043e \u0432\u0441\u0435\u043c\u0443, \u0441\u0442\u0430\u0442\u044c\u0438 \u043e\u0442 Ignatius Teo \u043f\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430\u043c \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u043b\u0438\u0441\u044c. \u0411\u043b\u0430\u0433\u043e\u0434\u0430\u0440\u044e \u0432\u0441\u0435\u0445 \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u0432\u0448\u0438\u0445, \u043d\u0435 \u043e\u0436\u0438\u0434\u0430\u043b, \u0447\u0442\u043e \u043f\u0435\u0440\u0432\u0443\u044e \u0447\u0430\u0441\u0442\u044c \u0442\u0430\u043a \u043c\u043d\u043e\u0433\u043e \u0447\u0435\u043b\u043e\u0432\u0435\u043a \u043f\u043e\u043c\u0435\u0441\u0442\u0438\u0442 \u0432 \u0438\u0437\u0431\u0440\u0430\u043d\u043d\u043e\u0435, \u0445\u043e\u0442\u044f \u0432\u0441\u0435 \u043c\u044b \u0437\u043d\u0430\u0435\u043c \u0447\u0442\u043e \u0438\u0437\u0431\u0440\u0430\u043d\u043d\u043e\u0435 \u0440\u0435\u0434\u043a\u043e \u043a\u043e\u0433\u0434\u0430 \u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f \u0438 \u0432\u0441\u0435 \u043f\u043e\u0441\u0442\u044b \u043e\u0441\u0442\u0430\u044e\u0442\u0441\u044f \u0442\u0430\u043c \u043d\u0430\u0432\u0441\u0435\u0433\u0434\u0430 \ud83d\ude42<\/p>\n<p>  \u041a\u0430\u043a \u043e\u0431\u044b\u0447\u043d\u043e, \u0432 \u043b\u0438\u0447\u043a\u0443 \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u044e\u0442\u0441\u044f \u043c\u043e\u0438 \u043e\u0448\u0438\u0431\u043a\u0438 \u0432 \u0442\u0435\u043a\u0441\u0442\u0435, \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0435, \u043f\u0440\u043e\u0442\u0438\u0432\u043e\u0440\u0435\u0447\u0438\u0432\u0430\u044f \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044f, \u0430 \u0442\u0430\u043a\u0436\u0435 \u043d\u0430\u0433\u043b\u043e\u0435 \u0432\u0440\u0430\u043d\u044c\u0435.<br \/>  \u0412 \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u044f\u0445 \u043f\u0440\u0438\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0442\u0441\u044f \u043e\u0431\u0441\u0443\u0436\u0434\u0435\u043d\u0438\u0435 \u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u0434\u043e\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f, \u0447\u0442\u043e\u0431\u044b \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0432 \u0441\u0442\u0430\u0442\u044c\u044e.   \t<\/p>\n<div class=\"clear\"><\/div>\n<\/p><\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"http:\/\/habrahabr.ru\/post\/190474\/\"> http:\/\/habrahabr.ru\/post\/190474\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div class=\"content html_format\">       \u041f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u044e \u0441\u043e\u0432\u043c\u0435\u0449\u0430\u0442\u044c \u043f\u0440\u0438\u044f\u0442\u043d\u043e\u0435 \u0441 \u043f\u043e\u043b\u0435\u0437\u043d\u044b\u043c \u0438 \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0438\u0442\u044c. \u0421\u0435\u0433\u043e\u0434\u043d\u044f \u0440\u0435\u0447\u044c \u0437\u0430\u0439\u0434\u0435\u0442 \u043e \u043a\u0443\u0447\u0430\u0445 (heaps) \u0438 \u0433\u0440\u0430\u0444\u0430\u0445. \u041a\u0430\u043a \u043e\u0431\u044b\u0447\u043d\u043e, \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b \u0441\u043a\u043e\u0440\u0435\u0435 \u043f\u043e\u0434\u043e\u0439\u0434\u0435\u0442 \u043d\u043e\u0432\u0438\u0447\u043a\u0430\u043c \u2014 \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438, \u0435\u0441\u043b\u0438 \u043d\u0435 \u0432\u0441\u044f, \u0443\u0436\u0435 \u0433\u0434\u0435-\u0442\u043e \u0442\u0430\u043a \u0438\u043b\u0438 \u0438\u043d\u0430\u0447\u0435 \u043e\u0441\u0432\u0435\u0449\u0430\u043b\u0430\u0441\u044c.<\/p>\n<p>  \u0412 \u043a\u043e\u043d\u0446\u0435 <a href=\"http:\/\/habrahabr.ru\/post\/190176\/\">\u043f\u0440\u043e\u0448\u043b\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0438<\/a> \u0437\u0430\u0442\u0440\u0430\u0433\u0438\u0432\u0430\u043b\u0438\u0441\u044c \u0434\u0435\u0440\u0435\u0432\u044c\u044f, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043d\u0430\u0447\u043d\u0435\u043c \u0441 \u043a\u0443\u0447\u0438, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043c\u0435\u0436\u0434\u0443 \u043a\u0443\u0447\u0435\u0439 \u0438 \u0434\u0435\u0440\u0435\u0432\u044c\u044f\u043c\u0438 \u0435\u0441\u0442\u044c \u043e\u0431\u0449\u0438\u0435 \u043a\u043e\u0440\u043d\u0438. \u0417\u0430\u0442\u0435\u043c \u043f\u0435\u0440\u0435\u0439\u0434\u0435\u043c \u043a \u0433\u0440\u0430\u0444\u0430\u043c \u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-190474","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/190474","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=190474"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/190474\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=190474"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=190474"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=190474"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}