{"id":6484,"date":"2020-06-24T13:27:53","date_gmt":"2020-06-24T13:27:53","guid":{"rendered":"https:\/\/www.askpython.com\/?p=6484"},"modified":"2020-06-24T13:27:54","modified_gmt":"2020-06-24T13:27:54","slug":"python-heapq-module","status":"publish","type":"post","link":"https:\/\/www.askpython.com\/python-modules\/python-heapq-module","title":{"rendered":"Python heapq Module: Using heapq to Build Priority Queues in Python"},"content":{"rendered":"\n<p>Hello everyone! In today&#8217;s article, we&#8217;ll be looking at using the Python heapq Module.<\/p>\n\n\n\n<p>This modules gives us a quick and easy way to build any type of priority queue for your application.<\/p>\n\n\n\n<p>To understand more about this module, let&#8217;s take a closer look.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Priority Queue as a Min-Heap<\/h2>\n\n\n\n<p>A Priority Queue is a queue where elements have another parameter called the priority. Based on the priority of the element, those elements are pushed \/ popped off the Queue first.<\/p>\n\n\n\n<p>This modules utilizes a binary min-heap for building the priority queue.<\/p>\n\n\n\n<p>The main property of this heap queue data structure is that the smallest element is always popped off first!<\/p>\n\n\n\n<p>In addition, once any element is pushed \/ popped, the same type of structure is maintained.<\/p>\n\n\n\n<p>This data structure has a large number of applications, including sorting.<\/p>\n\n\n\n<p>Let&#8217;s understand how we can now use this module.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Understanding the Python heapq Module<\/h2>\n\n\n\n<p>This module is a part of the standard library, so there&#8217;s no need to install it separately using <a href=\"https:\/\/www.askpython.com\/python-modules\/python-pip\" class=\"rank-math-link\">pip<\/a>.<\/p>\n\n\n\n<p>To import the heapq module, we can do the following:<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: plain; title: ; notranslate\" title=\"\">\nimport heapq\n<\/pre><\/div>\n\n\n<p>In the <code>heapq<\/code> module, we mainly require 3 methods which we need for building and manipulating our priority queue:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>heappush(heap, item)<\/code> -&gt; Push <code>item<\/code> onto the <code>heap<\/code>, and maintaining the min-heap property.<\/li><li><code>heappop(heap)<\/code> -&gt; Pops and returns the smallest item from the heap. If the heap is empty, we will get an <code>IndexError<\/code> <a href=\"https:\/\/www.askpython.com\/python\/python-exception-handling\" class=\"rank-math-link\">Exception<\/a>.<\/li><li><code>heapify(iterable)<\/code> -&gt; Converts the iterable (list, etc) into a min-heap. This modifies the iterable in-place<\/li><\/ul>\n\n\n\n<p>Let&#8217;s take a simple example of building the priority queue from a normal list of integers.<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nimport heapq\n\na = &#x5B;1, 4, 3, 5, 2]\n\nprint(&quot;List =&quot;, a)\n\n# Convert the iterable (list) into a min-heap in-place\nheapq.heapify(a)\n\nprint(&quot;Min Heap =&quot;, a)\n<\/pre><\/div>\n\n\n<p><strong>Output<\/strong><\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nList = &#x5B;1, 4, 3, 5, 2]\nMin Heap = &#x5B;1, 2, 3, 5, 4]\n<\/pre><\/div>\n\n\n<p>As you can see, the <code>heapify()<\/code> method modifies the list in-place, and converts it into a min-heap.<\/p>\n\n\n\n<p>To observe why it is a min-heap, simply draw the tree representation of both the lists.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"411\" height=\"291\" src=\"https:\/\/www.askpython.com\/wp-content\/uploads\/2020\/06\/old_list-1.png\" alt=\"Old List 1\" class=\"wp-image-6486\" srcset=\"https:\/\/www.askpython.com\/wp-content\/uploads\/2020\/06\/old_list-1.png 411w, https:\/\/www.askpython.com\/wp-content\/uploads\/2020\/06\/old_list-1-300x212.png 300w\" sizes=\"auto, (max-width: 411px) 100vw, 411px\" \/><figcaption>Old List &#8211; Tree Representation<\/figcaption><\/figure><\/div>\n\n\n\n<p>For a min-heap representation from a list, for a node with index <code>i<\/code>, its children have indices <code>2*i<\/code> and <code>2*i+1<\/code>.<\/p>\n\n\n\n<p>For a min-heap, the parent must be lesser than both it&#8217;s children!<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"423\" height=\"298\" src=\"https:\/\/www.askpython.com\/wp-content\/uploads\/2020\/06\/min-heap-flow.png\" alt=\"Min Heap Flow\" class=\"wp-image-6519\" srcset=\"https:\/\/www.askpython.com\/wp-content\/uploads\/2020\/06\/min-heap-flow.png 423w, https:\/\/www.askpython.com\/wp-content\/uploads\/2020\/06\/min-heap-flow-300x211.png 300w\" sizes=\"auto, (max-width: 423px) 100vw, 423px\" \/><figcaption>Min Heap Flow<\/figcaption><\/figure><\/div>\n\n\n\n<p>As you can see, the second list indeed follows our min-heap property! Thus, we have verified that the <code>heapify()<\/code> method gives us the correct min-heap.<\/p>\n\n\n\n<p>We will now push and pop to\/from our heap.<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nimport heapq\n\na = &#x5B;1, 4, 3, 5, 2]\n\nprint(&quot;List =&quot;, a)\n\n# Convert the iterable (list) into a min-heap in-place\nheapq.heapify(a)\n\nprint(&quot;Min Heap =&quot;, a)\n\n# Use heappush\nheapq.heappush(a, 10)\n\nprint(&quot;After heappush(), Min Heap =&quot;, a)\n\n# Use array indexing to get the smallest element\nprint(f&quot;Smallest element in the heap queue = {a&#x5B;0]}&quot;)\n\n# Use heappop() and return the popped element\npopped_element = heapq.heappop(a)\n\nprint(f&quot;Popped element = {popped_element}, Min Heap = {a}&quot;)\n<\/pre><\/div>\n\n\n<p><strong>Output<\/strong><\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nList = &#x5B;1, 4, 3, 5, 2]\nMin Heap = &#x5B;1, 2, 3, 5, 4]\nAfter heappush(), Min Heap = &#x5B;1, 2, 3, 5, 4, 10]\nSmallest element in the heap queue = 1\nPopped element = 1, Min Heap = &#x5B;2, 4, 3, 5, 10]\n<\/pre><\/div>\n\n\n<p>As you can see, we were easily able to perform our desired operations on this heap queue! Let&#8217;s now look at using this min-heap to sort our list using heapsort.<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nimport heapq\n\ndef heapsort(iterable):\n    h = &#x5B;]\n    for value in iterable:\n        # Push the elements onto the heap\n        heapq.heappush(h, value)\n    # Keep popping the smallest elements and appending them to our sorted list\n    return &#x5B;heapq.heappop(h) for i in range(len(h))]\n\nsorted_list = heapsort(&#x5B;1, 3, 5, 7, 9, 2, 4, 6, 8, 0])\nprint(sorted_list)\n<\/pre><\/div>\n\n\n<p><strong>Output<\/strong><\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: plain; title: ; notranslate\" title=\"\">\n&#x5B;0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n<\/pre><\/div>\n\n\n<p>Great! Indeed, we have used the heap queue property to sort our list!<\/p>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Conclusion<\/h2>\n\n\n\n<p>In this article, we learned about using the Python heapq module and saw how we could use the min-heap property to sort our unordered list.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">References<\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"https:\/\/docs.python.org\/3\/library\/heapq.html\" target=\"_blank\" rel=\"noopener\">Python Documentation<\/a> on the heapq module<\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n","protected":false},"excerpt":{"rendered":"<p>Hello everyone! In today&#8217;s article, we&#8217;ll be looking at using the Python heapq Module. This modules gives us a quick and easy way to build any type of priority queue for your application. To understand more about this module, let&#8217;s take a closer look. Priority Queue as a Min-Heap A Priority Queue is a queue [&hellip;]<\/p>\n","protected":false},"author":7,"featured_media":6489,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-6484","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-python-modules"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts\/6484","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/comments?post=6484"}],"version-history":[{"count":0,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts\/6484\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/media\/6489"}],"wp:attachment":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/media?parent=6484"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/categories?post=6484"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/tags?post=6484"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}