{"id":204004,"date":"2025-05-29T13:20:22","date_gmt":"2025-05-29T05:20:22","guid":{"rendered":"https:\/\/server.hk\/cnblog\/204004\/"},"modified":"2025-05-29T13:20:22","modified_gmt":"2025-05-29T05:20:22","slug":"%e4%ba%86%e8%a7%a3python%e7%9a%84heapq%e6%a8%a1%e5%9d%97","status":"publish","type":"post","link":"https:\/\/server.hk\/cnblog\/204004\/","title":{"rendered":"\u4e86\u89e3Python\u7684heapq\u6a21\u5757"},"content":{"rendered":"<p><b><\/b>     <\/p>\n<h1>\u4e86\u89e3Python\u7684heapq\u6a21\u5757<\/h1>\n<p><span style=\"font-size: 15px\">\u6709\u5fd7\u8005\uff0c\u4e8b\u7adf\u6210\uff01\u5982\u679c\u4f60\u5728\u5b66\u4e60<span style=\"color: #FF6600;, Helvetica, Arial, sans-serif;font-size: 14px;background-color: #FFFFFF\">\u6587\u7ae0<\/span>\uff0c\u90a3\u4e48\u672c\u6587<span style=\"color: #FF6600;, Helvetica, Arial, sans-serif;font-size: 14px;background-color: #FFFFFF\">\u300a\u4e86\u89e3Python\u7684heapq\u6a21\u5757\u300b<\/span>\uff0c\u5c31\u5f88\u9002\u5408\u4f60\uff01\u6587\u7ae0\u8bb2\u89e3\u7684\u77e5\u8bc6\u70b9\u4e3b\u8981\u5305\u62ec<span style=\"color: #FF6600;, Helvetica, Arial, sans-serif;font-size: 14px;background-color: #FFFFFF\"><\/span>\uff0c\u82e5\u662f\u4f60\u5bf9\u672c\u6587\u611f\u5174\u8da3\uff0c\u6216\u8005\u662f\u60f3\u641e\u61c2\u5176\u4e2d\u67d0\u4e2a\u77e5\u8bc6\u70b9\uff0c\u5c31\u8bf7\u4f60\u7ee7\u7eed\u5f80\u4e0b\u770b\u5427~<\/span><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/www.17golang.com\/uploads\/20241017\/1729139443671092f383c3d.jpg\" class=\"aligncenter\"><\/p>\n<p>\u5728python\u4e2d\uff0c\u5806\u662f\u4e00\u4e2a\u5f3a\u5927\u7684\u5de5\u5177\uff0c\u53ef\u4ee5\u6709\u6548\u5730\u7ba1\u7406\u5143\u7d20\u96c6\u5408\uff0c\u5728\u8fd9\u4e9b\u5143\u7d20\u96c6\u5408\u4e2d\uff0c\u60a8\u7ecf\u5e38\u9700\u8981\u5feb\u901f\u8bbf\u95ee\u6700\u5c0f\uff08\u6216\u6700\u5927\uff09\u7684\u9879\u76ee\u3002 <\/p>\n<p>python\u4e2d\u7684heapq\u6a21\u5757\u63d0\u4f9b\u4e86\u5806\u961f\u5217\u7b97\u6cd5\u7684\u5b9e\u73b0\uff0c\u4e5f\u79f0\u4e3a\u4f18\u5148\u7ea7\u961f\u5217\u7b97\u6cd5\u3002 <\/p>\n<p>\u672c\u6307\u5357\u5c06\u89e3\u91ca\u5806\u7684\u57fa\u7840\u77e5\u8bc6\u4ee5\u53ca\u5982\u4f55\u4f7f\u7528 heapq \u6a21\u5757\uff0c\u5e76\u63d0\u4f9b\u4e00\u4e9b\u5b9e\u9645\u793a\u4f8b\u3002<\/p>\n<hr>\n<p>\u5806\u662f\u4e00\u79cd\u7279\u6b8a\u7684\u57fa\u4e8e\u6811\u7684\u6570\u636e\u7ed3\u6784\uff0c\u6ee1\u8db3\u5806\u5c5e\u6027\uff1a<\/p>\n<ul>\n<li>\u5728\u6700\u5c0f\u5806\u4e2d\uff0c\u5bf9\u4e8e\u4efb\u4f55\u7ed9\u5b9a\u8282\u70b9 i\uff0ci \u7684\u503c\u5c0f\u4e8e\u6216\u7b49\u4e8e\u5176\u5b50\u8282\u70b9\u7684\u503c\u3002\u56e0\u6b64\uff0c\u6700\u5c0f\u7684\u5143\u7d20\u59cb\u7ec8\u4f4d\u4e8e\u6839\u3002<\/li>\n<li>\u5728\u6700\u5927\u5806\u4e2d\uff0ci \u7684\u503c\u5927\u4e8e\u6216\u7b49\u4e8e\u5176\u5b50\u5143\u7d20\u7684\u503c\uff0c\u4f7f\u6700\u5927\u5143\u7d20\u6210\u4e3a\u6839\u3002<\/li>\n<\/ul>\n<p>\u5728 python \u4e2d\uff0cheapq \u5b9e\u73b0\u4e86\u6700\u5c0f\u5806\uff0c\u8fd9\u610f\u5473\u7740\u6700\u5c0f\u7684\u5143\u7d20\u59cb\u7ec8\u4f4d\u4e8e\u5806\u7684\u6839\u90e8\u3002<\/p>\n<hr>\n<p>\u5f53\u60a8\u9700\u8981\u65f6\uff0c\u5806\u7279\u522b\u6709\u7528\uff1a<\/p>\n<ul>\n<li>\u5feb\u901f\u8bbf\u95ee\u6700\u5c0f\u6216\u6700\u5927\u5143\u7d20\uff1a\u8bbf\u95ee\u5806\u4e2d\u6700\u5c0f\u6216\u6700\u5927\u5143\u7d20\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a o(1)\uff0c\u8fd9\u610f\u5473\u7740\u5b83\u5728\u5e38\u6570\u65f6\u95f4\u5185\u5b8c\u6210\u3002<\/li>\n<li>\u9ad8\u6548\u7684\u63d2\u5165\u548c\u5220\u9664\uff1a\u5411\u5806\u4e2d\u63d2\u5165\u4e00\u4e2a\u5143\u7d20\u6216\u5220\u9664\u6700\u5c0f\u7684\u5143\u7d20\u9700\u8981 o(log n) \u65f6\u95f4\uff0c\u6bd4\u5bf9\u672a\u6392\u5e8f\u5217\u8868\u7684\u64cd\u4f5c\u6548\u7387\u66f4\u9ad8\u3002<\/li>\n<\/ul>\n<hr>\n<p>heapq \u6a21\u5757\u63d0\u4f9b\u4e86\u5bf9\u5e38\u89c4 python \u5217\u8868\u6267\u884c\u5806\u64cd\u4f5c\u7684\u51fd\u6570\u3002 <\/p>\n<p>\u4f7f\u7528\u65b9\u6cd5\u5982\u4e0b\uff1a<\/p>\n<p>\u8981\u521b\u5efa\u5806\uff0c\u8bf7\u4ece\u4e00\u4e2a\u7a7a\u5217\u8868\u5f00\u59cb\uff0c\u7136\u540e\u4f7f\u7528 heapq.heappush() \u51fd\u6570\u6dfb\u52a0\u5143\u7d20\uff1a<\/p>\n<pre>import heapq\n\nheap = []\nheapq.heappush(heap, 10)\nheapq.heappush(heap, 5)\nheapq.heappush(heap, 20)\n<\/pre>\n<p>\u7ecf\u8fc7\u8fd9\u4e9b\u64cd\u4f5c\uff0c\u5806\u5c06\u662f [5, 10, 20]\uff0c\u6700\u5c0f\u5143\u7d20\u4f4d\u4e8e\u7d22\u5f15 0\u3002<\/p>\n<p>\u53ea\u9700\u5f15\u7528heap[0]\u5373\u53ef\u8bbf\u95ee\u6700\u5c0f\u5143\u7d20\uff0c\u800c\u65e0\u9700\u5220\u9664\u5b83\uff1a<\/p>\n<pre>smallest = heap[0]\nprint(smallest)  # output: 5\n<\/pre>\n<p>\u8981\u5220\u9664\u5e76\u8fd4\u56de\u6700\u5c0f\u5143\u7d20\uff0c\u8bf7\u4f7f\u7528 heapq.heappop():<\/p>\n<pre>smallest = heapq.heappop(heap)\nprint(smallest)  # output: 5\nprint(heap)  # output: [10, 20]\n<\/pre>\n<p>\u6b64\u64cd\u4f5c\u540e\uff0c\u5806\u4f1a\u81ea\u52a8\u8c03\u6574\uff0c\u4e0b\u4e00\u4e2a\u6700\u5c0f\u7684\u5143\u7d20\u5360\u636e\u6839\u4f4d\u7f6e\u3002<\/p>\n<p>\u5982\u679c\u4f60\u5df2\u7ecf\u6709\u4e00\u4e2a\u5143\u7d20\u5217\u8868\uff0c\u53ef\u4ee5\u4f7f\u7528 heapq.heapify() \u5c06\u5176\u8f6c\u6362\u4e3a\u5806\uff1a<\/p>\n<pre>numbers = [20, 1, 5, 12, 9]\nheapq.heapify(numbers)\nprint(numbers)  # output: [1, 9, 5, 20, 12]\n<\/pre>\n<p>\u5806\u5316\u540e\uff0c\u6570\u5b57\u5c06\u4e3a[1, 9, 5, 12, 20]\uff0c\u4fdd\u6301\u5806\u5c5e\u6027\u3002<\/p>\n<p>heapq.merge() \u51fd\u6570\u5141\u8bb8\u60a8\u5c06\u591a\u4e2a\u6392\u5e8f\u8f93\u5165\u5408\u5e76\u4e3a\u4e00\u4e2a\u6392\u5e8f\u8f93\u51fa\uff1a<\/p>\n<pre>heap1 = [1, 3, 5]\nheap2 = [2, 4, 6]\nmerged = list(heapq.merge(heap1, heap2))\nprint(merged)  # output: [1, 2, 3, 4, 5, 6]\n<\/pre>\n<p>\u8fd9\u4f1a\u4ea7\u751f [1, 2, 3, 4, 5, 6]\u3002<\/p>\n<p>\u60a8\u8fd8\u53ef\u4ee5\u4f7f\u7528 heapq.nlargest() \u548c heapq.nsmallest() \u67e5\u627e\u6570\u636e\u96c6\u4e2d\u6700\u5927\u6216\u6700\u5c0f\u7684 n \u4e2a\u5143\u7d20\uff1a<\/p>\n<pre>numbers = [20, 1, 5, 12, 9]\nlargest_three = heapq.nlargest(3, numbers)\nsmallest_three = heapq.nsmallest(3, numbers)\nprint(largest_three)  # output: [20, 12, 9]\nprint(smallest_three)  # output: [1, 5, 9]\n<\/pre>\n<p>\u6700\u5927\u7684_\u4e09\u5c06\u662f[20,12,9]\uff0c\u6700\u5c0f\u7684_\u4e09\u5c06\u662f[1,5,9]\u3002<\/p>\n<hr>\n<p>\u5806\u7684\u4e00\u4e2a\u5e38\u89c1\u7528\u4f8b\u662f\u5b9e\u73b0\u4f18\u5148\u7ea7\u961f\u5217\uff0c\u5176\u4e2d\u6bcf\u4e2a\u5143\u7d20\u90fd\u6709\u4e00\u4e2a\u4f18\u5148\u7ea7\uff0c\u5e76\u4e14\u9996\u5148\u670d\u52a1\u5177\u6709\u6700\u9ad8\u4f18\u5148\u7ea7\uff08\u6700\u4f4e\u503c\uff09\u7684\u5143\u7d20\u3002<\/p>\n<pre>import heapq\n\n\nclass PriorityQueue:\n    def __init__(self):\n        self._queue = []\n        self._index = 0\n\n    def push(self, item, priority):\n        heapq.heappush(self._queue, (priority, self._index, item))\n        self._index += 1\n\n    def pop(self):\n        return heapq.heappop(self._queue)[-1]\n\n\n# Usage\npq = PriorityQueue()\npq.push('task1', 1)\npq.push('task2', 4)\npq.push('task3', 3)\n\nprint(pq.pop())  # Outputs 'task1'\nprint(pq.pop())  # Outputs 'task3'\n<\/pre>\n<p>\u5728\u6b64\u793a\u4f8b\u4e2d\uff0c\u4efb\u52a1\u4ee5\u5176\u5404\u81ea\u7684\u4f18\u5148\u7ea7\u5b58\u50a8\u5728\u4f18\u5148\u7ea7\u961f\u5217\u4e2d\u3002 <\/p>\n<p>\u4f18\u5148\u7ea7\u503c\u6700\u4f4e\u7684\u4efb\u52a1\u603b\u662f\u5148\u5f39\u51fa\u3002<\/p>\n<hr>\n<p>      \u7248\u672c\u58f0\u660e \u672c\u6587\u8f6c\u8f7d\u4e8e\uff1adev.to \u5982\u6709\u4fb5\u72af\uff0c\u8bf7\u8054\u7cfb\u5220\u9664<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u4e86\u89e3Python\u7684heapq\u6a21\u5757&#46;&#46;&#46;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4925],"tags":[],"class_list":["post-204004","post","type-post","status-publish","format-standard","hentry","category-4925"],"_links":{"self":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/posts\/204004","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/comments?post=204004"}],"version-history":[{"count":0,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/posts\/204004\/revisions"}],"wp:attachment":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/media?parent=204004"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/categories?post=204004"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/tags?post=204004"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}