Skip to content
XeveAbout code and problems

Indexed Priority Queue in C++

January 12, 2021 0 comments Article Uncategorized nspo

Basics

Priority queues are a useful data structure e.g. when you repeatedly need to access the largest or smallest element of a set of values but want more efficiency than keeping an array ordered. The C++ standard library contains std::priority_queue, which works well for basic use cases. It offers insertion of elements as well as access and removal of the minimum (or maximum). It does not, however, offer a method for changing the priority of a value, which is needed for some applications (like Dijkstra’s algorithm to find shortest paths in graphs). Often such a method is called decreaseKey or changeKey. This post offers an implementation using a binary heap which supports this operation in O(log(n)) time.

Code

The implementation makes it necessary to refer to specific elements with a numeric ID (or index) between 0 and maxSize-1. This maximum size of the priority queue must be specified when calling the constructor. The priority of IDs is specified with keys, which can be both simple numeric values (e.g. integers or floating point values) or custom classes for which operator< (for IndexedMaxPriorityQueue) or operator> (for IndexedMinPriorityQueue) is defined. The following main methods are available:

  • insert to add a new ID
  • peekFirst and removeFirst to view or remove the value with minimum/maximum priority
  • remove to delete a specific ID
  • changeKey to adapt the priority of an ID
  • empty and contains to check for emptiness and whether a specific ID is part of the priority queue

The code needs C++17 and is available here: https://github.com/nspo/graphs-cpp/blob/master/general/include/IndexedPriorityQueue.h

You can also check out the test folder for some exampes.

Tags: c++, changekey, decreasekey, dijkstra, indexed priority queue, priority queue

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Recent Posts

  • Spanish Juggling problem
  • Changing the maximum upload file size with Nextcloud in a docker-compose setup
  • Shrinking a QNAP Virtualization Station disk image
  • Indexed Priority Queue in C++
  • Efficient Union-Find in C++ – or: Disjoint-set forests with Path Compression and Ranks

Recent Comments

  • Andreas on Shrinking a QNAP Virtualization Station disk image
  • Arjun on Fix for Latex4CorelDraw with CorelDraw 2017
  • Nigel De Gillern on No wired (LAN) connection in Linux, although everything looks right
  • Harald H on Automatically reboot TP-Link router WDR4300 / N750 with bash script
  • Gene on Running multiple Django projects on one Apache instance with mod_wsgi

Archives

  • January 2023
  • December 2022
  • January 2021
  • May 2020
  • April 2020
  • July 2018
  • May 2018
  • April 2018
  • March 2018
  • September 2015
  • August 2015
  • June 2015
  • March 2015
  • February 2015
  • September 2014
  • March 2013

Categories

  • Uncategorized

Meta

  • Log in
  • Entries feed
  • Comments feed
  • WordPress.org

Copyright Xeve 2025 | Theme by ThemeinProgress | Proudly powered by WordPress