patterncppModerate
Implementation of binary min-heap data structure
Viewed 0 times
heapminbinarystructureimplementationdata
Problem
What do you think is wrong with this code, and how can it be improved? What corner case have I overlooked, if any?
Note: I do not want to use any STL features here, but I'm okay with anything else from C++11.
Note: I do not want to use any STL features here, but I'm okay with anything else from C++11.
class min_heap{
int pvt,P;
int arr[10000];
public:
min_heap(){
P=1;
}
void add(int x){
pvt=P;
arr[P]=x;
while(pvt>1){
if(arr[pvt]arr[x*2+1]&&(elm>arr[x*2]||elm>arr[x*2+1])){
arr[x]=arr[x*2+1];
arr[x*2+1]=temp;
x=x*2+1;
continue;
}
if(arr[x*2]arr[x*2]||elm>arr[x*2+1])){
arr[x]=arr[x*2];
arr[x*2]=temp;
x=x*2;
continue;
}
break;
}
if(P-1>=x*2&&arr[x*2]>x1;
min1.add(x1);
}
std::cout<<std::endl;
for(int i=1;i<=50;i++){
int x1=min1.extract();
std::cout<<x1<<std::endl;
}
}Solution
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 appears to be too long, it either needs to be shortened (preferred) or wrapped onto separate lines.
Either way, you should especially have some whitespace between operators and operands so that it won't take others unneeded time to read and understand it. This will also benefit you whenever you're maintaining the code (fixing bugs, adding things, and changing things around).
For instance, this line:
should look like this:
Isn't that easier to read? There's no need to cram everything together; just let the code breathe. You could still space out the operators within the
-
Your variable names are very generic. Many of them are only single letters, and your array data member is just named
-
Although it's entirely optional, you can add the
-
The constructor:
can be an initializer list:
If it ever gets lengthy, you can list the members on separate lines:
If
-
You don't need
Instead, just output
This is also mentioned here.
Overall, I'd highly recommend making this more readable first, so that it's easier to understand and improve for yourself and others. Implementing all the algorithms yourself will especially require the code to be clean and self-documenting, otherwise you're really just writing C code instead.
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 appears to be too long, it either needs to be shortened (preferred) or wrapped onto separate lines.
Either way, you should especially have some whitespace between operators and operands so that it won't take others unneeded time to read and understand it. This will also benefit you whenever you're maintaining the code (fixing bugs, adding things, and changing things around).
For instance, this line:
if(arr[x*2]>arr[x*2+1]&&(elm>arr[x*2]||elm>arr[x*2+1])){should look like this:
if (arr[x*2] > arr[x*2+1] && (elm > arr[x*2] || elm > arr[x*2+1])) {Isn't that easier to read? There's no need to cram everything together; just let the code breathe. You could still space out the operators within the
[], but it's not quite as common.-
Your variable names are very generic. Many of them are only single letters, and your array data member is just named
arr. Without good naming, you'll just leave others guessing at what each variable does. Plus, if you look at this code years from now, you may have no idea what it all means, and so you may be tempted to throw it away and start all over.-
Although it's entirely optional, you can add the
private keyword anyway, even though classes are private by default. It may add a little more readability, especially if there is a lot of code.-
The constructor:
min_heap(){
P=1;
}can be an initializer list:
min_heap() : P(1) {}If it ever gets lengthy, you can list the members on separate lines:
min_heap()
: P(1)
, // additional ones
, // separated by commas
{}If
pvt and arr need to be initialized, then it should be done here as well. I'm not sure why you just initialize one data member.-
You don't need
std::endl here. In most cases, a flush isn't necessary along with a newline, which is what's being done by that.Instead, just output
"\n" for a newline:std::cout << "\n";This is also mentioned here.
Overall, I'd highly recommend making this more readable first, so that it's easier to understand and improve for yourself and others. Implementing all the algorithms yourself will especially require the code to be clean and self-documenting, otherwise you're really just writing C code instead.
Code Snippets
if(arr[x*2]>arr[x*2+1]&&(elm>arr[x*2]||elm>arr[x*2+1])){if (arr[x*2] > arr[x*2+1] && (elm > arr[x*2] || elm > arr[x*2+1])) {min_heap(){
P=1;
}min_heap() : P(1) {}min_heap()
: P(1)
, // additional ones
, // separated by commas
{}Context
StackExchange Code Review Q#57387, answer score: 15
Revisions (0)
No revisions yet.