{"id":9920,"date":"2021-07-09T11:02:58","date_gmt":"2021-07-09T05:32:58","guid":{"rendered":"https:\/\/python-programs.com\/?p=9920"},"modified":"2021-11-22T18:50:10","modified_gmt":"2021-11-22T13:20:10","slug":"priority-queue-beginners-guide","status":"publish","type":"post","link":"https:\/\/python-programs.com\/priority-queue-beginners-guide\/","title":{"rendered":"Priority Queue: A Beginner\u2019s Guide"},"content":{"rendered":"

Prerequisites<\/strong><\/p>\n

To learn about Priority Queue, you must know:<\/p>\n

    \n
  1. Python 3<\/li>\n
  2. Linear Queue<\/li>\n
  3. Basic Python data structure concepts –\u00a0lists, tuples<\/li>\n<\/ol>\n

    What is a priority queue?<\/h2>\n

    Before you go ahead and read this tutorial, I highly recommend you to read the previous tutorial on\u00a0Queues\u00a0and\u00a0Circular Queues\u00a0as it will give you a better foundation and help you grasp the the content here.<\/p>\n

    What would you do if you wanted to track the least played songs in your playlist? The easiest solution would be to sort the list but that is time-consuming and wasteful. You only have to keep track of the song with the least hits. A min heap or priority queue helps you do this.<\/p>\n

    Priority Queues, also known as heap queues, are abstract data structures. Heaps are binary trees where every parent node has a value less than or equal to any of its children. In other words, this type of queue keeps track of the minimum value. Thus it helps retrieve the minimum value at all times. For this reason, it is also referred to as min heap. Thus, position 0 holds the smallest\/minimum value. There is also a max heap whose operation is quite similar.<\/p>\n

    Note:<\/b>\u00a0heap queues or priority queues don\u2019t sort lists in ascending order. It just keeps the smallest element in its 0th position. The rest of the elements may or may not be sorted.<\/p>\n

    How To Implement Priority Queue<\/b><\/h4>\n

    To use priority queue, you will have to import the\u00a0heapq\u00a0<\/i>library. This is done as follows:<\/p>\n

    import heapq<\/pre>\n
    The following heap commands can be performed once the\u00a0heapq\u00a0<\/i>module is imported:<\/p>\n
      \n
    1. heapify() – this operation enables you to convert a regular list to a heap. On performing this operation, the smallest element gets pushed to position 0.<\/li>\n<\/ol>\n
      h = [5,2,6,8,0,1,2,4]\r\nheapq.heapify(h) #returns [0, 2, 1, 4, 5, 6, 2, 8]<\/pre>\n
      Note:<\/strong>\u00a0Only the first element is in its correct sorted position.<\/p>\n
        \n
      1. heapq.heappush(heap, item) – this operation pushes an element into a heap.\u00a0Heap\u00a0<\/i>refers to the name of the heap and\u00a0item\u00a0<\/i>refers to the item to be added to the heap. For instance:<\/li>\n<\/ol>\n
        heapq.heappush(h,7)\r\nprint(h) #[0, 2, 1, 4, 5, 6, 2, 8, 7]<\/pre>\n
        Try adding a negative number and observe what happens.<\/p>\n
          \n
        1. heapq.heappop(heap) – this operation is used to return the smallest element in the heap.\u00a0Heap\u00a0<\/i>refers to the name of the heap.<\/li>\n<\/ol>\n
          heapq.heappop(h) #returns 0<\/pre>\n
            \n
          1. heapq.heappushpop(heap, item) – as the name suggests this command adds an item to the heap and returns the smallest number. This single command is much more efficient than a\u00a0heappush()\u00a0<\/i>command followed by\u00a0heappop()\u00a0<\/i>command.<\/li>\n<\/ol>\n
            heapq.heappushpop(h,3) #returns 0\r\nprint(h) #prints [1, 2, 2, 4, 5, 6, 3, 8, 7]<\/pre>\n
            If you try the above command with a number smaller than the min value of heap, you will notice that the same element gets popped. For instance:<\/p>\n
            heapq.heappushpop(h,0) #returns 0 print(h) #prints [1, 2, 2, 4, 5, 6, 3, 8, 7]<\/p>\n
              \n
            1. heapq.heapreplace(heap, item) -the above issue can be solved by executing this operation as it returns the smallest element and then adds the new element.<\/li>\n<\/ol>\n
              heapq.heapreplace(h,0) #returns 1\r\nprint(h) #prints [0, 2, 2, 4, 5, 6, 3, 8, 7]<\/pre>\n
              The above-mentioned commands are the main ones you will use when dealing with heaps but there are also other general commands like\u00a0merge(), nlargest()\u00a0<\/i>and\u00a0nsmallest().\u00a0<\/i>You can explore these on your own!<\/p>\n
              Applications<\/b><\/h3>\n
              Priority Queues are widely used in different fields such as Artificial Intelligence, Statistics, Operating systems and in graphs.<\/p>\n
              Conclusion<\/strong><\/p>\n
              Try solving the music player problem discussed in the introduction. You will need to\u00a0heapify<\/em>\u00a0a list of tuples where each tuple should look like\u00a0(number of hits, songid, name of the song)<\/i>. The\u00a0heapify<\/em>\u00a0command will track the min according to the first element of the tuple which is why the first element of the tuple is\u00a0the number of hits<\/em>. Post your answers below. That\u2019s it for this tutorial. Happy Pythoning!<\/p>\n","protected":false},"excerpt":{"rendered":"
              Prerequisites To learn about Priority Queue, you must know: Python 3 Linear Queue Basic Python data structure concepts –\u00a0lists, tuples What is a priority queue? Before you go ahead and read this tutorial, I highly recommend you to read the previous tutorial on\u00a0Queues\u00a0and\u00a0Circular Queues\u00a0as it will give you a better foundation and help you grasp …<\/p>\n
                Priority Queue: A Beginner\u2019s Guide<\/span> Read More »<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false,"jetpack_publicize_feature_enabled":true},"categories":[5],"tags":[],"yoast_head":"\nPriority Queue: A Beginner\u2019s Guide - Python Programs<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/python-programs.com\/priority-queue-beginners-guide\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Priority Queue: A Beginner\u2019s Guide - Python Programs\" \/>\n<meta property=\"og:description\" content=\"Prerequisites To learn about Priority Queue, you must know: Python 3 Linear Queue Basic Python data structure concepts –\u00a0lists, tuples What is a priority queue? Before you go ahead and read this tutorial, I highly recommend you to read the previous tutorial on\u00a0Queues\u00a0and\u00a0Circular Queues\u00a0as it will give you a better foundation and help you grasp … Priority Queue: A Beginner\u2019s Guide Read More »\" \/>\n<meta property=\"og:url\" content=\"https:\/\/python-programs.com\/priority-queue-beginners-guide\/\" \/>\n<meta property=\"og:site_name\" content=\"Python Programs\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/btechgeeks\" \/>\n<meta property=\"article:published_time\" content=\"2021-07-09T05:32:58+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2021-11-22T13:20:10+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@btech_geeks\" \/>\n<meta name=\"twitter:site\" content=\"@btech_geeks\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"veer\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Organization\",\"@id\":\"https:\/\/python-programs.com\/#organization\",\"name\":\"BTech Geeks\",\"url\":\"https:\/\/python-programs.com\/\",\"sameAs\":[\"https:\/\/www.instagram.com\/btechgeeks\/\",\"https:\/\/www.linkedin.com\/in\/btechgeeks\",\"https:\/\/in.pinterest.com\/btechgeek\/\",\"https:\/\/www.youtube.com\/channel\/UC9MlCqdJ3lKqz2p5114SDIg\",\"https:\/\/www.facebook.com\/btechgeeks\",\"https:\/\/twitter.com\/btech_geeks\"],\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/python-programs.com\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/python-programs.com\/wp-content\/uploads\/2020\/11\/BTechGeeks.png\",\"contentUrl\":\"https:\/\/python-programs.com\/wp-content\/uploads\/2020\/11\/BTechGeeks.png\",\"width\":350,\"height\":70,\"caption\":\"BTech Geeks\"},\"image\":{\"@id\":\"https:\/\/python-programs.com\/#\/schema\/logo\/image\/\"}},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/python-programs.com\/#website\",\"url\":\"https:\/\/python-programs.com\/\",\"name\":\"Python Programs\",\"description\":\"Python Programs with Examples, How To Guides on Python\",\"publisher\":{\"@id\":\"https:\/\/python-programs.com\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/python-programs.com\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/python-programs.com\/priority-queue-beginners-guide\/#webpage\",\"url\":\"https:\/\/python-programs.com\/priority-queue-beginners-guide\/\",\"name\":\"Priority Queue: A Beginner\u2019s Guide - Python Programs\",\"isPartOf\":{\"@id\":\"https:\/\/python-programs.com\/#website\"},\"datePublished\":\"2021-07-09T05:32:58+00:00\",\"dateModified\":\"2021-11-22T13:20:10+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/python-programs.com\/priority-queue-beginners-guide\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/python-programs.com\/priority-queue-beginners-guide\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/python-programs.com\/priority-queue-beginners-guide\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/python-programs.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Priority Queue: A Beginner\u2019s Guide\"}]},{\"@type\":\"Article\",\"@id\":\"https:\/\/python-programs.com\/priority-queue-beginners-guide\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/python-programs.com\/priority-queue-beginners-guide\/#webpage\"},\"author\":{\"@id\":\"https:\/\/python-programs.com\/#\/schema\/person\/9f9e30fd3f415217a11ac0d939213b7f\"},\"headline\":\"Priority Queue: A Beginner\u2019s Guide\",\"datePublished\":\"2021-07-09T05:32:58+00:00\",\"dateModified\":\"2021-11-22T13:20:10+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/python-programs.com\/priority-queue-beginners-guide\/#webpage\"},\"wordCount\":603,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/python-programs.com\/#organization\"},\"articleSection\":[\"Python\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/python-programs.com\/priority-queue-beginners-guide\/#respond\"]}]},{\"@type\":\"Person\",\"@id\":\"https:\/\/python-programs.com\/#\/schema\/person\/9f9e30fd3f415217a11ac0d939213b7f\",\"name\":\"veer\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/python-programs.com\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/f1f6915d5328abaea9a64249313d1c55?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/f1f6915d5328abaea9a64249313d1c55?s=96&d=mm&r=g\",\"caption\":\"veer\"},\"sameAs\":[\"https:\/\/python-programs.com\"],\"url\":\"https:\/\/python-programs.com\/author\/veer\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Priority Queue: A Beginner\u2019s Guide - Python Programs","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/python-programs.com\/priority-queue-beginners-guide\/","og_locale":"en_US","og_type":"article","og_title":"Priority Queue: A Beginner\u2019s Guide - Python Programs","og_description":"Prerequisites To learn about Priority Queue, you must know: Python 3 Linear Queue Basic Python data structure concepts –\u00a0lists, tuples What is a priority queue? Before you go ahead and read this tutorial, I highly recommend you to read the previous tutorial on\u00a0Queues\u00a0and\u00a0Circular Queues\u00a0as it will give you a better foundation and help you grasp … Priority Queue: A Beginner\u2019s Guide Read More »","og_url":"https:\/\/python-programs.com\/priority-queue-beginners-guide\/","og_site_name":"Python Programs","article_publisher":"https:\/\/www.facebook.com\/btechgeeks","article_published_time":"2021-07-09T05:32:58+00:00","article_modified_time":"2021-11-22T13:20:10+00:00","twitter_card":"summary_large_image","twitter_creator":"@btech_geeks","twitter_site":"@btech_geeks","twitter_misc":{"Written by":"veer","Est. reading time":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Organization","@id":"https:\/\/python-programs.com\/#organization","name":"BTech Geeks","url":"https:\/\/python-programs.com\/","sameAs":["https:\/\/www.instagram.com\/btechgeeks\/","https:\/\/www.linkedin.com\/in\/btechgeeks","https:\/\/in.pinterest.com\/btechgeek\/","https:\/\/www.youtube.com\/channel\/UC9MlCqdJ3lKqz2p5114SDIg","https:\/\/www.facebook.com\/btechgeeks","https:\/\/twitter.com\/btech_geeks"],"logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/python-programs.com\/#\/schema\/logo\/image\/","url":"https:\/\/python-programs.com\/wp-content\/uploads\/2020\/11\/BTechGeeks.png","contentUrl":"https:\/\/python-programs.com\/wp-content\/uploads\/2020\/11\/BTechGeeks.png","width":350,"height":70,"caption":"BTech Geeks"},"image":{"@id":"https:\/\/python-programs.com\/#\/schema\/logo\/image\/"}},{"@type":"WebSite","@id":"https:\/\/python-programs.com\/#website","url":"https:\/\/python-programs.com\/","name":"Python Programs","description":"Python Programs with Examples, How To Guides on Python","publisher":{"@id":"https:\/\/python-programs.com\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/python-programs.com\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/python-programs.com\/priority-queue-beginners-guide\/#webpage","url":"https:\/\/python-programs.com\/priority-queue-beginners-guide\/","name":"Priority Queue: A Beginner\u2019s Guide - Python Programs","isPartOf":{"@id":"https:\/\/python-programs.com\/#website"},"datePublished":"2021-07-09T05:32:58+00:00","dateModified":"2021-11-22T13:20:10+00:00","breadcrumb":{"@id":"https:\/\/python-programs.com\/priority-queue-beginners-guide\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/python-programs.com\/priority-queue-beginners-guide\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/python-programs.com\/priority-queue-beginners-guide\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/python-programs.com\/"},{"@type":"ListItem","position":2,"name":"Priority Queue: A Beginner\u2019s Guide"}]},{"@type":"Article","@id":"https:\/\/python-programs.com\/priority-queue-beginners-guide\/#article","isPartOf":{"@id":"https:\/\/python-programs.com\/priority-queue-beginners-guide\/#webpage"},"author":{"@id":"https:\/\/python-programs.com\/#\/schema\/person\/9f9e30fd3f415217a11ac0d939213b7f"},"headline":"Priority Queue: A Beginner\u2019s Guide","datePublished":"2021-07-09T05:32:58+00:00","dateModified":"2021-11-22T13:20:10+00:00","mainEntityOfPage":{"@id":"https:\/\/python-programs.com\/priority-queue-beginners-guide\/#webpage"},"wordCount":603,"commentCount":0,"publisher":{"@id":"https:\/\/python-programs.com\/#organization"},"articleSection":["Python"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/python-programs.com\/priority-queue-beginners-guide\/#respond"]}]},{"@type":"Person","@id":"https:\/\/python-programs.com\/#\/schema\/person\/9f9e30fd3f415217a11ac0d939213b7f","name":"veer","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/python-programs.com\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/f1f6915d5328abaea9a64249313d1c55?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/f1f6915d5328abaea9a64249313d1c55?s=96&d=mm&r=g","caption":"veer"},"sameAs":["https:\/\/python-programs.com"],"url":"https:\/\/python-programs.com\/author\/veer\/"}]}},"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/posts\/9920"}],"collection":[{"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/comments?post=9920"}],"version-history":[{"count":3,"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/posts\/9920\/revisions"}],"predecessor-version":[{"id":12175,"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/posts\/9920\/revisions\/12175"}],"wp:attachment":[{"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/media?parent=9920"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/categories?post=9920"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/tags?post=9920"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}