14

This code looks a lot like C with classes, rather than modern C++. You make no use of the standard library except for std::cout. You #include <cmath>, but I don't see where you used its functionality. I'll try to point out a few places where the standard library would simplify the code. But first: Bug: Your copy constructor copies items over from ...


12

General design Encapsulation Some of the member functions provided by PQueue<T> are helper functions which should not be publicly available (e.g. why should an external caller use PQueue<T>::increment?). Helper functions should usually be private, or in some exceptional cases protected. Return types/out parameters Some methods take an int& to ...


11

First up, let's both simplify your low level Stack class, and correct the Generics at the same time. Stack The issues with the generics are "obvious" by the numerous times you cast values that should be generically correct anyway. You also have overly complicated logic in your push method: public void push(T item){ Node p = new Node((Comparable) item)...


10

Not a Stack A Stack is a data structure where items are removed Last-In-First-Out (LIFO). This data structure does not do that. Therefore, it is not a Stack. Calling it a SortedStack is confusing as you've removed everything about it that is like a Stack and not any other type of Collection. This has the interface behavior of a PriorityQueue, why not ...


10

I opted to make a constructor that allows the option of min or max order, since it runs on the pathfinder the performance of this is quite crucial as well. So hopefully some one has some suggestions on ways to improve it. Sure: take an IComparer (defaulting to Comparer<T>.Default if you have a simpler constructor which doesn't take one) and use ...


8

You're off to a great start. +1 for providing comments. Here are some tips: 1) Define variables before modifying them. So the constants MAX_HEAP and MIN_HEAP should be defined after PriorityQueue. Old Code: PriorityQueue.MAX_HEAP = 0; PriorityQueue.MIN_HEAP = 1; function PriorityQueue(criteria, heapType) { //... } New Code: function PriorityQueue(...


8

new and delete... Manual use of new and delete very often leads to leaks. In this case you have a destructor but not any other of the rule of 5 requirements so every List and Node will get double deleted once the queue has been copied once. If instead if you had m_priority_map and m_element_map hold their values by value there wouldn't be any leak ...


7

The following is used multiple times and it could be extracted out: if (!sorted) { Collections.sort(list, comparator); sorted = true; } to a helper method: private void sortIfNeccessary() { if (sorted) { return; } Collections.sort(list, comparator); sorted = true; } Note the guard clause. List.remove returns the removed ...


7

const int maxsize = 5; A couple of things here. First you should prefer constexpr. But furthermore I am curious why you have a maxsize of 5. You may have a good reason, but if you do it would probably be good to document the decision because it isn't implicitly obvious. Is it completely arbitrary? You could document that if it is the case. int front, rear,n;...


6

I'm asking for rather hard, destructive critics and review. Sure. Interface. I don't see the interface (ie class definition). So it becomes harder to review. Things I don't see I don't see any move semantics for your class. Normally (since C++11) I would expect containers to implement move semantics. i.e. I would expect to see the following methods: ...


6

1. Review The code in the post does not work: >>> q = PriorityQueue(()) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "cr152757.py", line 8, in __init__ self._counter = itertools.count() # unique sequence count NameError: name 'itertools' is not defined The problem is that itertools was ...


5

In regards to your questions: I see no real benefit of suffixing struct types with _t - it just adds clutter. As well prefixing every pointer with p_ introduces a lot of clutter and makes the code harder to read since now all identifiers start with the same prefix - this typically means your brain has to do a lot more work and read a lot more characters ...


5

1. Bug You can't pop an item from the queue if it's the only item: >>> q = PriorityQueueUpdateable() >>> q[1] = 1 >>> q.pop() Traceback (most recent call last): File "<stdin>", line 1, in <module> File "cr163560.py", line 41, in pop self._clear_heap() File "cr163560.py", line 25, in _clear_heap value, ...


5

When you declare a class, initialize all member variables char data = '\0'; size_t freq = 0; ... (depending on your compiler you may need to do that in the constructor instead) especially pointers, since a delete on an uninitialized pointer is undefined behavior but a delete on a nullptr is OK (NOP). void GenerateCode(std::vector<char>& data, ...


5

A definite memory leak: void priority_queue_free(struct priority_queue_t* pq) { free(pq); } doesn't free(pq->array). A possible memory leak: a realloc in array_resizemay fail, and after pq->array = array_resize(....) the array is lost. The pq->array[0] is never used. I am not sure that it makes the code simpler. Idiomatically n should ...


5

"The user of the priority queue is expected to define their data type in the data.h header. This is to make the code flexible and not use void*." Code limits the types available to pointers to some struct. The definition mechanism requires a data.h file - this is awkward. Strongly recommend a simpler direct approach and reconsider using void *. &...


4

Reject nodes already visited Your main loop looks like this: while(!pq.isEmpty()){ min_node=pq.remove().node; visited[min_node]=true; updateDistance(min_node); } Since your code is capable of adding the same node multiple times to the priority queue (with updated costs), you should reject any node that you've already visited, like this: while(!...


4

Doesn't work if mt == 0 If looks like the code is supposed to support both multithreaded and non-multithreaded cases. However, in add_pqueue(), there is this code: } else { if (!pqueue->mt) return 1; The effect of this is to always abort if multithreading is off. I think you meant to do this instead: } else if (pqueue->mt) { Mutexes and ...


4

I am aware that there are other ways of implementing a priority queue e.g. using a sorted array/list. ok, for the sake of the review I'll pretend I know only the List<>. Queue or Stack? This should be a PriorityQueue so I suggest renaming TKey to TPriority and the Key property to Priority as this is what the key is, right? If you look a the .NET ...


4

About performance As a forewords, I'm not sure you should be obsessed with performance as a beginner (actually I'm pretty sure you should not but surely others will disagree). Consider reading : https://softwareengineering.stackexchange.com/questions/80084/is-premature-optimization-really-the-root-of-all-evil With that said... In the Employee class : As ...


4

Until for (i in 0..n - 1) { can be replaced with for (i in (0 until n)) Lift return from when when { left <= n && greater(k, left) -> return false right <= n && greater(k, right) -> return false else -> { return isMinHeap(left) && isMinHeap(right) } } can be replaced with return when { ...


4

The other answers make some good points (especially @vnp who caught the two memory leaks — that's a huge deal!). I'll try not to repeat too much. int compare(const struct element* element1, const struct element* element2) { return element1->weight - element2->weight; } You should be aware that this comparator can have undefined behavior if ...


4

This is a very nice and clean implementation and looks like there's not much to complain about but I have a few thoughts. One thing I'm undecided on is restricting T to be ICompareable<T>. While this sends a strong signal about the requirements of T when using the default comparer, it's unnecessarily restrictive in the case where the user wants to ...


4

Please review the code as if this was 45 minute interview. I don't know what you expect from answerers with this statement. The evaluation of some code produced within 45 minutes is subjective, highly dependent on the company and position, and dozens of other factors. Whether a reviewer says "good job in 45 minutes" or "poor job in 45 minutes", I think it's ...


4

Naming The name Heap is confusing, since this is a priority queue, not a heap. The heap is merely an internal private implementation detail that should not be exposed to the outside world. Just call it what it is: a PriorityQueue. The same applies to heap. This one is a local variable with limited scope and obvious semantics, so I would be fine with pq as a ...


4

Avoid double pointers. They are absolutely unwarranted in all the functions (except init, but see below). Prefer returning a value to a side effect. In the client code, which I presume is along the lines of struct priority_queue * pq; init_queue(&pq, capacity); I have to read the source of init_queue to see that there is a side effect of modifying ...


3

Allocation one too big In pq_create(), this allocation: priority_queue *pq = malloc(sizeof(priority_queue) + sizeof(item) * (size + 1)); could be smaller by one item: priority_queue *pq = malloc(sizeof(priority_queue) + sizeof(item) * size); The priority_queue structure already contains space for one item, so you only need size more items. Dead code ...


3

Use of linked list I wrote a Priority Queue that is stored using a doubly linked list. I'm tempted to start and stop with this single point. A priority queue stored as a linked list is just a bad idea. There's virtually nothing you can do from that point onward to even have a hope of repairing that. If you're set on putting a linked list to use, I'd at ...


3

First of all, it's probably best to realize that a heap isn't particularly useful for this problem as it's specified. It can be used, but it doesn't really contribute much (if anything at all). If you do use a heap, you want to take the specific properties of a max heap into account. In particular, a heap is arranged so each node is at least as large as any ...


3

Mmmmm // A trick because top() returns a const T& Interval i1 = std::move(const_cast<Interval&>(queue.top())); A trick that is illegal. Also I am not convinced this does not break the underlying priority queue. As the top value when popped is unwound out of a heap using the compare operation that inspects the internal members ...


Only top voted, non community-wiki answers of a minimum length are eligible