Hot answers tagged

16

Since you seem to be tryingy to mimic the style of STL containers (at least, that's what your comments say), there are several things you could improve: STL containers subtypes Most of the STL containers have subtypes. I am pretty sure that some parts of the standard library use these subtypes. Therefore, if you want your code to work with the generic ...


15

You've mentioned that you don't want to utilize the STL, so I'll honor that. Just be aware that neglecting to use it may lessen the quality of your code, especially if you start to experience bugs. I'll mainly address best-practices as I'm not so familiar with the algorithm myself. Your lack of whitespace just makes this painful to read. If a line ...


14

Your names. pvt is pretty poor and P is, frankly, quite dismal as names go. I'm still not sure what P is really supposed to mean. you've used a fixed-size array where it's not really suitable. If your heap contains fewer than 10000 items, it wastes space. If a user tries to add more than 10000 items, they overflow the space you've allocated, leading to ...


14

Memory management You never delete[] arr;, which leaks memory. Not a good thing! There are multiple ways to fix this: Adding correct calls to delete[] arr; in the right places (remember exceptions, assignments and so on!), which is rather bug-prone. Also, new T[size] default-constructs size objects of type T in the contiguous memory. This requires T to be ...


14

Looks pretty readable and I agree with most of your formatting however there are some things that stand out. using namespace std; Kick this habit before it kicks you. #define MAX_TREE_HEIGHT 1000 I'd prefer to put this into an anonymous namespace as implementation detail unsigned freq; Not everyone knows this defaults to int. Might be a good idea to add int ...


13

As everyone has immediately pointed out, please stick with the namingConventions for methods and parameter names. Your code is not object oriented, as Java code should be. One sign is that you are using static functions everywhere. Another hint is that the name of a class should always be a noun; if it's a verb then your objects are likely to be crappy. ...


12

Style Dead code should be removed. Naming single letter variables should be avoided if they are not temporary. variable names should be named using camelCase casing names should be meaningful to support the readability of the code. Comments Comments should be used to describe why something is done not what is done. **What is done should be ...


12

Performance bug private void BubbleUp(T element) { int elementIndex = _elements.IndexOf(element); ... This is \$O(n)\$, which completely oblitirates \$O(\log n)\$. (It takes over a second on 2,5 GHz CPU to insert 10 000 elements using your version.) Same applies to BubbleDown. Instead of passing the element to BubbleUp and BuggleDown, pass the ...


11

Priority queue There are warnings of unchecked calls, mostly since you declared MinPriorityQueue<Key extends Comparable, Value extends Comparable>. Comparable to what? That should be MinPriorityQueue<Key extends Comparable<? super Key>, Value extends Comparable<? super Value>>. One more warning happens at the array creation in ...


10

I note that you're restricting your types T to those that are IComparable, that is, those that implement CompareTo. A more general solution would allow the caller to specify their own IComparer which may be that type's CompareTo or may be something else entirely. Also see https://stackoverflow.com/questions/14336416/using-icomparer-for-sorting


10

It would be nice to be able to pass an IComparer<TKey> instead of having to make sure TKey implements IComparable<>. It could default to Comparer<TKey>.Default. This provides you with a lot more flexibility in terms of which types can be used as keys. Get can return null . So if you try to access a non-existing key you will get a ...


9

public HeapType MinOrMax { get; private set; } I'm wary of any name that has the words And or Or in it. It often indicates that something has too many responsibilities. Names like HeapType inside of a Heap class are also indicative that you should be considering some inheritance and an OOP approach. I'm not saying for sure that it's better, but you may ...


9

All in all it seems to work all right. Personally I don't like constructs like: if (0 < Count) {...} but: if (Count > 0) {...} And this: if (!(offset < Capacity)) is less readable than: if (offset >= Capacity) If I interpret Operations.NextPowerOf2 in the right way, I think it makes the heap capacity grow unnecessarily for larger ...


8

I see you have tested the case when there is no path to the destination, but I'm not convinced that returning seemingly valid data in that case is a good idea. You can easily catch such case by adding an else clause to the main while loop. You will land there if the loop ends without break. Disregarding the no path case you can simplify the second while loop ...


8

You added beginner, so I'm going to give you a few pointers to start with, to help you work from. First: C#6.0 (which I see you are using) allows void methods to be expressions as well as ones with a return type. public void Clear() { _elements.Clear(); } To: public void Clear() => _elements.Clear(); You may or may not want to do this, I don't like ...


8

You have a couple of PEP8 style problems: Functions should have an empty line above and below them. Function calls should have their bracket immediately after the name. So fn( not fn (. Assignment operators should have a space either side of them. Try to keep code less than 80 characters long. You also have a couple of naming problems: compar should be ...


8

Your method isEmpty is not needed at all. First, none of your code uses it. Second, if you were to keep it, you should turn it's logic around and rename it to __bool__, this way, if heap automatically works and is True if the heap is not empty. But third, if no __bool__ method exists, Python already calls len(obj) != 0 to determine an object's truthiness, so ...


8

public abstract class AbstractHeap { #region internal properties private int Capacity { get; set; } internal int Size { get; set; } internal int[] Nodes { get; set; } Capacity doesn't seem to serve any purpose at all. It just mirrors Nodes.Length and is a potential source of bugs. Why should subclasses be able to access the setters of Size ...


8

I don't like the Swap method. The two ref parameters suggest that the values passed are swapped. Instead, the values are taken as indexes in m_values whose values are swapped. It also has an unexpected side-effect as it changes the index x. Also, y is passed as ref, but it never changes. Either call it SwapValuesAt and take the input as indexes without ref, ...


8

NEVER use using namespace std. It can cause hard tracked bugs. Read here why: https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice The code has WAY to much comments. "Well commented" does not mean that it should have tons of comments. I have seen well commented code without comments. A problem with comments is that ...


7

1. Bug You don't properly synchronize the set and the heap in all cases. For example, when taking a union: >>> a = OpenList() >>> a |= set([1,2,3]) >>> a OpenList([1, 2, 3]) >>> a._heap [] If you insist on your class being a subclass of set, then you probably ought to intercept every method that modifies the set (and ...


7

I haven't checked the details of the algorithm, just some general feedback on the code, API, etc: It's usually a good practice to make a copy of mutable input parameters. (E[] heap in this case.) It prohibits malicious clients to modify the heap's internal structure or it could save you from a few hours of debugging. (Effective Java, 2nd Edition, Item 39: ...


7

You should always try to program against an interface instead of against an implementation. List<T> elements; should be IList<T> elements; Restrict the scope of fields and methods to the smallest possible. So public void Heapify() should be private instead. The swapping of elements inside the Heapify() method can be extracted to a ...


7

Style Dead code should be removed. maxSize is never used. Be consistent in your style. You should decide wether you use this. If a decision is made you should stick to it. Here i would suggest refactor the constructor to public MinHeap(int maxSize){ heap = new int[maxSize+1]; heap[0] = Integer.MIN_VALUE; size = 0; } Simplification ...


7

Initialize Set with values Your method of initializing the hashset with values takes quite a bit of space. I would create a static field: public static final String[] SEPARATORS = new String[] { " ", ",", ".", ";" }; And then use it like this: public static final Set<String> separatorsSet = new HashSet<String>(Arrays.asList(SEPARATORS)); ...


7

A few details. while len(h) > 0 can be rewritten while len(h) which can be rewritten while h. Comparisons to singletons like None should always be done with is or is not , never the equality operators. as per PEP8, the standard guide style. so prev[f] != None should be prev[f] is not None.


7

Drop the checks Right now, your pop() and top() both check for emptiness and throw. assert() would be better - you don't want these functions throwing. It's likely that your user will check for empty() first anyway - and if they don't, make sure they understand that they have to. With that, our top() becomes trivial: const T& top() const { return ...


7

public sealed class BinaryHeap<T> Well done. Using sealed if you don't intend to inherit from this class thats the way to go. private readonly List<T> _elements; private readonly Comparison<T> _compare; Marking fields which should not change with readonly is good. int elementIndex = _elements.IndexOf(element), minElementIndex = 0;...


7

You should separate your declarations into three parts: The public interface. malloc calloc realloc free The debug interface. print_freelist The implementation details, which should be kept out of headers. (the rest, consider static linkage) Avoid needless casts. Each and every cast is a possible trouble-spot. Use the standard library where allowed. No ...


7

Just the general C++ coding style treatment. Do not use using namespace std;. It can introduce subtle bugs, makes the code harder to read and writing out the std:: prefix generally is not going to be to time intensive. Keep your spacing consistent. Compare the following two lines bool operator< (const Node& other) vector<int> topKFrequent(...


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