–ü—Ä–∏–æ—Ä–∏—Ç–µ—Ç–Ω–∞—è –æ—á–µ—Ä–µ–¥—å Python: —Ä—É–∫–æ–≤–æ–¥—Å—Ç–≤–æ
–ü—Ä–∏–æ—Ä–∏—Ç–µ—Ç–Ω–∞—è –æ—á–µ—Ä–µ–¥—å Python —Ö—Ä–∞–Ω–∏—Ç –¥–∞–Ω–Ω—ã–µ –≤ –æ–ø—Ä–µ–¥–µ–ª–µ–Ω–Ω–æ–º –ø–æ—Ä—è–¥–∫–µ. –ï—Å—Ç—å –¥–≤–∞ —Å–ø–æ—Å–æ–±–∞ —Ä–µ–∞–ª–∏–∑–æ–≤–∞—Ç—å –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç–Ω—É—é –æ—á–µ—Ä–µ–¥—å –≤ Python: –∏—Å–ø–æ–ª—å–∑—É—è –∫–ª–∞—Å—Å –æ—á–µ—Ä–µ–¥–∏ –∏ –∏—Å–ø–æ–ª—å–∑—É—è –º–æ–¥—É–ª—å heapq.
–í—ã –º–æ–∂–µ—Ç–µ –∑–∞—Ö–æ—Ç–µ—Ç—å —É–ø–æ—Ä—è–¥–æ—á–∏—Ç—å –¥–∞–Ω–Ω—ã–µ –Ω–∞ –æ—Å–Ω–æ–≤–µ –∑–Ω–∞—á–µ–Ω–∏–π –∫–∞–∂–¥–æ–≥–æ —ç–ª–µ–º–µ–Ω—Ç–∞ –≤ —Å–ø–∏—Å–∫–µ. –ù–∞–ø—Ä–∏–º–µ—Ä, –≤—ã –º–æ–∂–µ—Ç–µ –∑–∞—Ö–æ—Ç–µ—Ç—å, —á—Ç–æ–±—ã –Ω–∞–∏–≤—ã—Å—à–µ–µ –∑–Ω–∞—á–µ–Ω–∏–µ –æ—Ç–æ–±—Ä–∞–∂–∞–ª–æ—Å—å –ø–µ—Ä–≤—ã–º –≤ —Å–ø–∏—Å–∫–µ, –∞ –Ω–∞–∏–º–µ–Ω—å—à–µ–µ - –ø–æ—Å–ª–µ–¥–Ω–∏–º –≤ —Å–ø–∏—Å–∫–µ.
–ò–º–µ–Ω–Ω–æ –∑–¥–µ—Å—å –∏ –ø–æ—è–≤–ª—è—é—Ç—Å—è –æ—á–µ—Ä–µ–¥–∏ —Å –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç–æ–º. –û—á–µ—Ä–µ–¥—å —Å –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç–æ–º - —ç—Ç–æ —Å—Ç—Ä—É–∫—Ç—É—Ä–∞ –¥–∞–Ω–Ω—ã—Ö. –∫–æ—Ç–æ—Ä—ã–π —Ö—Ä–∞–Ω–∏—Ç –¥–∞–Ω–Ω—ã–µ –Ω–∞ –æ—Å–Ω–æ–≤–µ –∑–Ω–∞—á–µ–Ω–∏–π –µ–≥–æ –∫–ª—é—á–µ–π –≤ –≤–æ–∑—Ä–∞—Å—Ç–∞—é—â–µ–º –ø–æ—Ä—è–¥–∫–µ. –≠—Ç–æ –ø–æ–∑–≤–æ–ª—è–µ—Ç –ª–µ–≥–∫–æ –ø–æ–ª—É—á–∏—Ç—å –¥–æ—Å—Ç—É–ø –∫ –Ω–∞–∏–º–µ–Ω—å—à–µ–º—É –∏ –Ω–∞–∏–±–æ–ª—å—à–µ–º—É –∑–Ω–∞—á–µ–Ω–∏—é –≤ –æ—á–µ—Ä–µ–¥–∏.
–í —ç—Ç–æ–º —Ä—É–∫–æ–≤–æ–¥—Å—Ç–≤–µ –±—É–¥–µ—Ç –æ–±—Å—É–∂–¥–∞—Ç—å—Å—è, –ø–æ—á–µ–º—É –≤–∞–º –Ω–µ —Å–ª–µ–¥—É–µ—Ç –∏—Å–ø–æ–ª—å–∑–æ–≤–∞—Ç—å —Å–ø–∏—Å–æ–∫ –¥–ª—è —Å–æ–∑–¥–∞–Ω–∏—è –æ—á–µ—Ä–µ–¥–µ–π —Å –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç–æ–º. –ú—ã –ø–æ–∫–∞–∂–µ–º –≤–∞–º –¥–≤–∞ –±–æ–ª–µ–µ —ç—Ñ—Ñ–µ–∫—Ç–∏–≤–Ω—ã—Ö –ø–æ–¥—Ö–æ–¥–∞, –∫–æ—Ç–æ—Ä—ã–µ –≤—ã –º–æ–∂–µ—Ç–µ –∏—Å–ø–æ–ª—å–∑–æ–≤–∞—Ç—å –¥–ª—è —Å–æ–∑–¥–∞–Ω–∏—è –æ—á–µ—Ä–µ–¥–∏ –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç–æ–≤ Python.
–ß—Ç–æ —Ç–∞–∫–æ–µ –æ—á–µ—Ä–µ–¥—å –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç–æ–≤ Python?
–û—á–µ—Ä–µ–¥–∏ –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç–æ–≤ - —ç—Ç–æ –º–æ–¥–∏—Ñ–∏—Ü–∏—Ä–æ–≤–∞–Ω–Ω–∞—è –≤–µ—Ä—Å–∏—è –æ—á–µ—Ä–µ–¥–∏, –≤ –∫–æ—Ç–æ—Ä–æ–π —Ö—Ä–∞–Ω—è—Ç—Å—è –¥–∞–Ω–Ω—ã–µ –≤ –ø–æ—Ä—è–¥–∫–µ —Ç–æ–≥–æ, –∫–∞–∫–æ–π —ç–ª–µ–º–µ–Ω—Ç –∏–º–µ–µ—Ç –Ω–∞–∏–≤—ã—Å—à–∏–π –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç. –ü—Ä–∏–æ—Ä–∏—Ç–µ—Ç –∫–∞–∂–¥–æ–≥–æ —ç–ª–µ–º–µ–Ω—Ç–∞ –≤ –æ—á–µ—Ä–µ–¥–∏ —Å –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç–æ–º –æ–ø—Ä–µ–¥–µ–ª—è–µ—Ç—Å—è –≤ –∑–∞–≤–∏—Å–∏–º–æ—Å—Ç–∏ –æ—Ç –∑–Ω–∞—á–µ–Ω–∏—è —ç–ª–µ–º–µ–Ω—Ç–∞.
–í –∏–Ω—Ñ–æ—Ä–º–∞—Ç–∏–∫–µ –æ—á–µ—Ä–µ–¥–∏ - —ç—Ç–æ —Å—Ç—Ä—É–∫—Ç—É—Ä—ã –¥–∞–Ω–Ω—ã—Ö, –≤ –∫–æ—Ç–æ—Ä—ã—Ö —ç–ª–µ–º–µ–Ω—Ç—ã —Ö—Ä–∞–Ω—è—Ç—Å—è –≤ –ø–æ—Ä—è–¥–∫–µ "–ø–µ—Ä–≤—ã–º –ø—Ä–∏—à–µ–ª - –ø–µ—Ä–≤—ã–º —É—à–µ–ª" (FIFO). . –ï—Å—Ç—å –Ω–µ—Å–∫–æ–ª—å–∫–æ —Å—Ü–µ–Ω–∞—Ä–∏–µ–≤, –≤ –∫–æ—Ç–æ—Ä—ã—Ö –∏—Å–ø–æ–ª—å–∑–æ–≤–∞–Ω–∏–µ —ç—Ç–æ–π —Å—Ç—Ä—É–∫—Ç—É—Ä—ã –º–æ–∂–µ—Ç –±—ã—Ç—å –ø–æ–ª–µ–∑–Ω—ã–º.
–ù–∞–ø—Ä–∏–º–µ—Ä, –ø—Ä–µ–¥–ø–æ–ª–æ–∂–∏–º, —á—Ç–æ –≤—ã —Å–æ–∑–¥–∞–µ—Ç–µ –ø—Ä–∏–ª–æ–∂–µ–Ω–∏–µ –¥–ª—è –æ—Ç—Å–ª–µ–∂–∏–≤–∞–Ω–∏—è –∑–∞–∫–∞–∑–æ–≤ –¥–ª—è —Ä–µ—Å—Ç–æ—Ä–∞–Ω–∞. –ß–µ–ª–æ–≤–µ–∫, —Ä–∞–∑–º–µ—Å—Ç–∏–≤—à–∏–π –∑–∞–∫–∞–∑ –ø–µ—Ä–≤—ã–º, –¥–æ–ª–∂–µ–Ω –æ–±—Å–ª—É–∂–∏–≤–∞—Ç—å—Å—è —Ä–∞–Ω—å—à–µ, —á–µ–º –ª—é–¥–∏, –∫–æ—Ç–æ—Ä—ã–µ —Ä–∞–∑–º–µ—Å—Ç—è—Ç —Å–≤–æ–π –∑–∞–∫–∞–∑ —Å–ª–µ–¥—É—é—â–∏–º. –ß—Ç–æ–±—ã –æ—Ç—Å–ª–µ–∂–∏–≤–∞—Ç—å –∑–∞–∫–∞–∑—ã, –≤—ã –º–æ–∂–µ—Ç–µ –∏—Å–ø–æ–ª—å–∑–æ–≤–∞—Ç—å –æ—á–µ—Ä–µ–¥—å.
–ï—Å—Ç—å –¥–≤–∞ —Å–ø–æ—Å–æ–±–∞ –æ–ø—Ä–µ–¥–µ–ª–∏—Ç—å –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç–Ω—É—é –æ—á–µ—Ä–µ–¥—å –≤ Python:
81% —É—á–∞—Å—Ç–Ω–∏–∫–æ–≤ –∑–∞—è–≤–∏–ª–∏, —á—Ç–æ –æ–Ω–∏ –±–æ–ª–µ–µ —É–≤–µ—Ä–µ–Ω—ã –≤ –∏—Ö –ø–µ—Ä—Å–ø–µ–∫—Ç–∏–≤—ã —Ç—Ä—É–¥–æ—É—Å—Ç—Ä–æ–π—Å—Ç–≤–∞ –≤ —Å—Ñ–µ—Ä–µ –≤—ã—Å–æ–∫–∏—Ö —Ç–µ—Ö–Ω–æ–ª–æ–≥–∏–π –ø–æ—Å–ª–µ —É—á–∞—Å—Ç–∏—è –≤ –±—É—Ç–∫–µ–º–ø–µ. –ü—Ä–æ–π–¥–∏—Ç–µ –∫—É—Ä—Å –æ–±—É—á–µ–Ω–∏—è —Å–µ–≥–æ–¥–Ω—è.
–°—Ä–µ–¥–Ω–∏–π –≤—ã–ø—É—Å–∫–Ω–∏–∫ —É—á–µ–±–Ω–æ–≥–æ –ª–∞–≥–µ—Ä—è –ø–æ—Ç—Ä–∞—Ç–∏–ª –º–µ–Ω–µ–µ —à–µ—Å—Ç–∏ –º–µ—Å—è—Ü–µ–≤ –Ω–∞ –ø–µ—Ä–µ—Ö–æ–¥–Ω—É—é –∫–∞—Ä—å–µ—Ä—É, –æ—Ç –Ω–∞—á–∞–ª–∞ —É—á–µ–±–Ω–æ–≥–æ –ª–∞–≥–µ—Ä—è –¥–æ –ø–æ–∏—Å–∫–∞ —Å–≤–æ–µ–π –ø–µ—Ä–≤–æ–π —Ä–∞–±–æ—Ç—ã.
–í—ã –º–æ–∂–µ—Ç–µ –æ–ø—Ä–µ–¥–µ–ª–∏—Ç—å –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç–Ω—É—é –æ—á–µ—Ä–µ–¥—å. –∏—Å–ø–æ–ª—å–∑—É—è —Å—Ç—Ä—É–∫—Ç—É—Ä—É —Å–ø–∏—Å–∫–∞. –ù–æ —ç—Ç–∞ —Å—Ç—Ä–∞—Ç–µ–≥–∏—è –º–µ–Ω–µ–µ —ç—Ñ—Ñ–µ–∫—Ç–∏–≤–Ω–∞, —á–µ–º –∏—Å–ø–æ–ª—å–∑–æ–≤–∞–Ω–∏–µ –∫–ª–∞—Å—Å–∞ –æ—á–µ—Ä–µ–¥–∏ PriorityQueue –∏–ª–∏ –º–æ–¥—É–ª—è heapq.
Priority Queue Python: queue.PriorityQueue
queue.PriorityQueue class —Å–æ–∑–¥–∞–µ—Ç –æ—á–µ—Ä–µ–¥—å –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç–æ–≤ Python. –≠—Ç–æ—Ç –∫–ª–∞—Å—Å —è–≤–ª—è–µ—Ç—Å—è —á–∞—Å—Ç—å—é –±–∏–±–ª–∏–æ—Ç–µ–∫–∏ –æ—á–µ—Ä–µ–¥–µ–π Python. –ß—Ç–æ–±—ã –∏—Å–ø–æ–ª—å–∑–æ–≤–∞—Ç—å —ç—Ç–æ—Ç –∫–ª–∞—Å—Å, –≤–∞–º –Ω–µ–æ–±—Ö–æ–¥–∏–º–æ –∏–º–ø–æ—Ä—Ç–∏—Ä–æ–≤–∞—Ç—å –±–∏–±–ª–∏–æ—Ç–µ–∫—É –æ—á–µ—Ä–µ–¥–∏. –ß—Ç–æ–±—ã –ø–æ–ª—É—á–∏—Ç—å —ç–ª–µ–º–µ–Ω—Ç –∏–∑ PriorityQueue, –≤—ã –º–æ–∂–µ—Ç–µ –∏—Å–ø–æ–ª—å–∑–æ–≤–∞—Ç—å –º–µ—Ç–æ–¥ get ().
–ß—Ç–æ–±—ã –ø–æ–ª—É—á–∏—Ç—å –¥–æ—Å—Ç—É–ø –∫ –∫–ª–∞—Å—Å—É PriorityQueue, –Ω–∞–º –Ω—É–∂–Ω–æ –∏–º–ø–æ—Ä—Ç–∏—Ä–æ–≤–∞—Ç—å –µ–≥–æ –≤ –Ω–∞—à –∫–æ–¥, —á—Ç–æ –º—ã –º–æ–∂–µ–º —Å–¥–µ–ª–∞—Ç—å —Å –ø–æ–º–æ—â—å—é —ç—Ç–æ–≥–æ –∏–Ω—Å—Ç—Ä—É–∫—Ü–∏—è –∏–º–ø–æ—Ä—Ç–∞ Python :
–ü—Ä–µ–¥–ø–æ–ª–æ–∂–∏–º, –º—ã —Ö–æ—Ç–∏–º —Å–æ–∑–¥–∞—Ç—å –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç–Ω—É—é –æ—á–µ—Ä–µ–¥—å –¥–ª—è –≤–ª–∞–¥–µ–ª—å—Ü–µ–≤ –±–∏–ª–µ—Ç–æ–≤ –Ω–∞ –º–µ—Å—Ç–Ω—ã–π –∫–æ–Ω—Ü–µ—Ä—Ç. –ú—ã –º–æ–≥–ª–∏ –±—ã —Å–¥–µ–ª–∞—Ç—å —ç—Ç–æ —Å –ø–æ–º–æ—â—å—é —Å–ª–µ–¥—É—é—â–µ–≥–æ –∫–æ–¥–∞:
–ù–∞—à –∫–æ–¥ –≤–æ–∑–≤—Ä–∞—â–∞–µ—Ç:
–í –Ω–∞—à–µ–º –∫–æ–¥–µ –º—ã —Å–Ω–∞—á–∞–ª–∞ –∏–º–ø–æ—Ä—Ç–∏—Ä—É–µ–º –∫–ª–∞—Å—Å PriorityQueue –∏–∑ –±–∏–±–ª–∏–æ—Ç–µ–∫–∏ queue, –∞ –∑–∞—Ç–µ–º –∏–Ω–∏—Ü–∏–∞–ª–∏–∑–∏—Ä—É–µ–º –æ—á–µ—Ä–µ–¥—å —Å –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç–æ–º –ø–æ–¥ –Ω–∞–∑–≤–∞–Ω–∏–µ–º ticket_holder. –ó–∞—Ç–µ–º –º—ã –≤—Å—Ç–∞–≤–ª—è–µ–º —Ç—Ä–∏ –∫–æ—Ä—Ç–µ–∂–∞ –≤ –Ω–∞—à—É –æ—á–µ—Ä–µ–¥—å –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç–æ–≤, –≤ –∫–æ—Ç–æ—Ä—ã—Ö —Ö—Ä–∞–Ω—è—Ç—Å—è –Ω–æ–º–µ—Ä–∞ –∏ –∏–º–µ–Ω–∞ –±–∏–ª–µ—Ç–æ–≤, —Å–≤—è–∑–∞–Ω–Ω—ã–µ —Å –±–∏–ª–µ—Ç–æ–º.
–ú—ã –∏—Å–ø–æ–ª—å–∑—É–µ–º —Ü–∏–∫–ª while Python –¥–ª—è –ø—Ä–æ—Ö–æ–∂–¥–µ–Ω–∏—è –∫–∞–∂–¥–æ–≥–æ —ç–ª–µ–º–µ–Ω—Ç–∞ –≤ –æ—á–µ—Ä–µ–¥–∏ –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç–æ–≤ ticket_holder. –ó–∞—Ç–µ–º –º—ã –ø–æ–ª—É—á–∞–µ–º —ç—Ç–æ—Ç —ç–ª–µ–º–µ–Ω—Ç —Å –ø–æ–º–æ—â—å—é get ().
–ú–µ—Ç–æ–¥ queue.PriorityQueue —ç—Ñ—Ñ–µ–∫—Ç–∏–≤–µ–Ω –∏ –ø—Ä–æ—Å—Ç –≤ –∏—Å–ø–æ–ª—å–∑–æ–≤–∞–Ω–∏–∏, —á—Ç–æ –¥–µ–ª–∞–µ—Ç –µ–≥–æ –æ—Ç–ª–∏—á–Ω—ã–º –≤—ã–±–æ—Ä–æ–º. –∫–æ–≥–¥–∞ –≤–∞–º –Ω—É–∂–Ω–æ —Å–æ–∑–¥–∞—Ç—å –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç–Ω—É—é –æ—á–µ—Ä–µ–¥—å.
Priority Queue Python heapq Module
–ú–æ–¥—É–ª—å heapq –ø–æ–∑–≤–æ–ª—è–µ—Ç –≤–∞–º –æ–ø—Ä–µ–¥–µ–ª—è—Ç—å –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç–Ω—É—é –æ—á–µ—Ä–µ–¥—å Python. –°—Ç—Ä—É–∫—Ç—É—Ä–∞ –¥–∞–Ω–Ω—ã—Ö heapq —É–¥–∞–ª—è–µ—Ç —ç–ª–µ–º–µ–Ω—Ç—ã –≤ –ø–æ—Ä—è–¥–∫–µ –∏—Ö –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç–∞. –°–∞–º–æ–µ –Ω–∏–∑–∫–æ–µ –∑–Ω–∞—á–µ–Ω–∏–µ –∏–º–µ–µ—Ç —Å–∞–º—ã–π –Ω–∏–∑–∫–∏–π –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç, –∞ —Å–∞–º–æ–µ –≤—ã—Å–æ–∫–æ–µ –∑–Ω–∞—á–µ–Ω–∏–µ –∏–º–µ–µ—Ç —Å–∞–º—ã–π –≤—ã—Å–æ–∫–∏–π –ø—Ä–∏–æ—Ä–∏—Ç–µ—Ç –≤ —Å—Ç—Ä—É–∫—Ç—É—Ä–µ heapq.