The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [priority-queue]

Priority queues are dynamic sets that always remove highest priority elements first.

Filter by
Sorted by
Tagged with
11
votes
3answers
5k views

Priority Queues - Array based implementation

I am learning about stacks, queues, lists & hash tables from the book Data Structures using C and C++ by Tanenbaum. I am also spending time to take in OOPs essentials, to ensure they sink in well, ...
11
votes
1answer
93 views

Longest lines using priority queue

Inspired by a comment on this question, I thought I'd exercise my C skills by implementing something like it using a priority queue. The idea is to be able to invoke the program like this: ./...
10
votes
2answers
197 views

SortedStack implementation in Java

This is a data structure that supports the push(), pop() and isEmpty() operations and ...
10
votes
1answer
249 views

Yet Another MinHeap

So, this has been done quite a few times on here, but each of the linked implementations has some significant issues. Since I needed a MinHeap anyway, I figured I would throw my version into the ring. ...
10
votes
2answers
408 views

Java queue with dynamic priority flag

I need to build a queue where the elements will be added and removed in chronological order by default. But if the client sets the priority flag for the queue I need to be able to pull the elements ...
7
votes
1answer
6k views

Priority Queue with update-able values

Here is my attempt to implement a minimum priority queue class in Python using the heapq module. I plan to use it in graph search algorithms so the values ...
6
votes
2answers
1k views

My implementation of FixedSizedPriorityQueue

I implemented a fixed sized priority queue. How can I improve my code? ...
6
votes
2answers
1k views

A stable priority queue in C++

I have this priority queue in C++ that is stable. Stability here means that if the queue contains different elements with equal priority, they will be popped in the insertion order. ...
6
votes
1answer
2k views

C++ Heap implementation

I'm on my way of understanding basic data structures and sorting algorithms through implementing them in c++. Post is followed of my implementation of Vector. I decided to weld the heap behaviour ...
6
votes
1answer
259 views

Updatable priority queue

This is an updatable priority queue. In contains an index (implemented as std::unordered_map) which maps a value to its position in the queue itself. The queue is ...
5
votes
4answers
7k views

Priority queue implementation in C#

My application has a thread for handling database inserts and updates. Data is added by other threads to a generic queue in the DB thread. The contents of this queue is retrieved and is sequentially ...
5
votes
1answer
5k views

Javascript PriorityQueue based on object property

I wrote this class which is a priority queue based on a numeric property of any object. As far as I can tell, the following code is working as intended. Are there any stylistic tendencies that I am ...
5
votes
2answers
462 views

Select top 2 employees based on Grade and Alphabetical Order

Given a list of Employees ( name and grade). Output the names of the top 2 employees selected for a task(sorted based on grade and then alphabetically). I am using a maxHeap and override the ...
5
votes
3answers
2k views

Indexed Fibonacci heap implementation

I implemented two versions of a Fibonacci heap one using a unordered map (mapping keys to their nodes) so that the client can call decrease in \$O(1)\$ average and ...
5
votes
1answer
172 views

Comparing puzzle solvers in Java

I have this program that solves a \$(n^2 - 1)\$-puzzles for general \$n\$. I have three solvers: BidirectionalBFSPathFinder ...
5
votes
0answers
1k views

Fibonacci heap in Python

I have this implementation of the Fibonacci heap in Python: ...
4
votes
4answers
2k views

Priority queue implementation in C based on heap ordered (resizable) array

I am practicing writing C library code and wrote a priority queue for some graph work. I am fairly new to writing C libraries so would appreciate any feedback on this implementation. Some items to ...
4
votes
3answers
240 views

C Threadsafe Priority Queue O(log n) push, O(1) pop

I wrote this for an A* implementation: (pqueue.c) ...
4
votes
4answers
167 views

Subdividing intervals that contain the largest error values

I'm trying to accomplish the following: Start out with 1 interval on the real line. This interval is processed in some function and out comes an array of errors (size < 10 usually). The maximum ...
4
votes
2answers
790 views

Basic generic priority queue using an unsorted list

I am aware that there are other ways of implementing a priority queue e.g. using a sorted array/list. Would appreciate some comments on my implementation of a basic priority queue supporting three ...
4
votes
1answer
1k views

Python priority queue class wrapper

I'm trying to incorporate the advice found in https://docs.python.org/3.5/library/heapq.html in order to make a priority queue implementation (see corresponding section) in a class ...
4
votes
1answer
2k views

Fibonacci heap in C

(See the next iteration.) I have rewritten a Fibonacci heap implementation from Java to C. fibonacci_heap.h: ...
4
votes
2answers
3k views

Maximum Priority Queue using Heap

I have written this program for Maximim Priority Queue after studying from Introduction to Algorithm . I want to improve my code. Is there any other method to implement Priority Queue instead of Heap? ...
4
votes
1answer
65 views

Overriding List subscription to create IndexedHeap for Classical Dijkstra's Algorithm

Much of the academic exposition of Dijkstra's Algorithm (such as Wikipedia, or this class page from Darmouth) relies on your priority queue having the ability decrease the key of an entry: the ...
4
votes
2answers
520 views

ObservablePriorityQueue<T> Implementation

I have a requirement in my current project that will need a Prioritised Queue that supports the IObservable interface. Please notify me of any problems with the implementation that I currently have: ...
3
votes
1answer
338 views

C# binary heap priority queue

I made an A* pathfinder and it was too slow so i did some research into priority queues, i got it working but i am wondering if there is any improvements i can make for this class. I opted to make a ...
3
votes
2answers
13k views

Huffman Coding in C++

I have written this code after studying from Introduction to Algorithm and from GeeksForGeeks. I know there is a lot to improve because I don't know much C++11. Please help me to improve this code. <...
3
votes
1answer
103 views

LeetCode: Minimum cost to hire k workers

https://leetcode.com/problems/minimum-cost-to-hire-k-workers/ There are N workers. The i-th worker has a quality[i] and a minimum wage expectation wage[i]. Now we want to hire exactly K ...
3
votes
2answers
151 views

Time Limit Exceeded for build_max_heap

This problem is from HackerEarth: The Monk learned about priority queues recently and asked his teacher for an interesting problem. So his teacher came up with a simple problem. He now has an ...
3
votes
4answers
8k views

Most frequent word in an array of strings - Java

Input word array is ...
3
votes
1answer
207 views

d-ary heap in C

Now I have this d-ary heap data structure. Note that for d = 2 this is a binary heap. The client programmer specifies the value ...
3
votes
1answer
755 views

Priority queue implementation in C based on heap ordered (resizable) array - take 2

You think that your code is perfect ... until you put it up for code review. I put up my priority queue for review and received lots of really good feedback. Including a memory leak which was ...
2
votes
1answer
1k views

Minimum Priority Queue implementation in Kotlin

Below you can find a generic implementation and some unit tests of a minimum priority queue in Kotlin. What could be improved in this implementation, so that it complies to best coding practices in ...
2
votes
1answer
67 views

Updateable Priority Queue

I've implemented an updateable priority queue as a part of implementing some single-source-shortest-path algorithms (Dijkstra, BF). I'm relatively new to Python. ...
2
votes
1answer
2k views

Implementation of Prim's Algorithm to find minimum spanning tree

What is the time complexity of the following code? I'm implementing Prim's Algorithm with adjacency matrix representation of the graph and priority queue. ...
2
votes
1answer
1k views

Priority queue implementation using unsorted and sorted array

Below is the unsorted array and sorted array implementation of priority queue. Code directory structure: ...
2
votes
1answer
54 views

A simple priority queue in Java via linked list sorted by priority keys

Now I have this very simple priority queue. add and changePriority both run in \$\mathcal{O}(n)\$ and ...
2
votes
1answer
69 views

Prioritize objects using PriorityQueue and custom comparator in Java

I have a list of objects and a query. I need to rank the objects, based on how do they match the query. An object would match the query 100% if it contains all properties in the query. My program ...
2
votes
0answers
70 views

An ISeq implementing Priority Queue

This is a follow up to my last review request. I made three major changes: I had it fully implement ISeq and IPersistentStack, ...
2
votes
0answers
61 views

A Priority Queue implemented using a Linked List

I'm going to write a Huffman Coding implementation, and decided to write from scratch a priority queue to help out. I've never written a priority queue before, in any language, so this was interesting....
2
votes
0answers
499 views

Priority queue with updatable values

I'm writing a priority queue that stores a bunch of data with a value attached to the data, with \$O(1)\$ access to the data with the smallest value attached to it. I also need to be able to update ...
2
votes
0answers
435 views

Min-Heap based priority queue class written in ES6

I would appreciate any feedback on syntax, naming convention, possible shortcuts, clarity of code and any other constructive feedback. This code was based off of the Priority Queue chapter in The ...
1
vote
1answer
125 views

Dijkstra's Algorithm not optimized enough

I was attempting a question on HackerRank-Dijkstra's Shortest Reach 2 and upon submission my programs times out in 3/7 test cases. One of the test cases had 200 nodes and about 2000 connections. Here ...
1
vote
2answers
330 views

Generic Min Heap Implementation in Java

There is a Min-Heap implementation in Java. BubbleUp() and BubbleDown() could have been coded using recursion but I prefer without recursion. Would there be a major difference if had used recursion? ...
1
vote
1answer
3k views

Implement a generic Priority Queue in C++

I wrote a Priority Queue that is stored using a doubly linked list. The queue can return the head and tail of the list, and contains a print function that is only used for testing purposes. I'd like ...
1
vote
3answers
3k views

Priority Queue (Binary Search Tree) Implementation

I have made a Priority Queue implemented as a Binary Search Tree. I would appreciate comments related to optimization and proper functionality, but any comments/critiques are welcome. PQ.h: ...
1
vote
1answer
8k views

Priority in pair<int,int> inside priority_queue on basis of both elements [closed]

I want a priority queue such that first it should be done on basis of first element (increasing order)and when clash occurs then on basis of second element(decreasing order). I came up with the ...
1
vote
2answers
298 views

Fibonacci heap in C - follow-up

(See the previous iteration.) I have incorporated some points made by ChrisWue and refactored my Fibonacci heap implementation: fibonacci_heap.h ...
1
vote
2answers
95 views

A simple card game simulator

This is a homework question, and I have written the code but wasn't sure if I had picked the right data structure for this job and minimised time complexity. Can anyone give me some feedback, anything ...
1
vote
1answer
290 views

Binary heap (priority queue) implementation in JavaScript

I wrote this heap implementation because I need it to run Dijkstra's algorithm to find paths in a game (for which reason I'd like this implementation not to be unreasonably slow...) Sadly I don't ...