Priority Queue (Binary Search Tree) Implementation

Question

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:

#ifndef PQ_H
#define PQ_H
#include <iostream>
struct Node
{
 int value;
 Node * left;
 Node * right;
 Node(int value)
 : value(value), left(NULL), right(NULL)
 {
 }
};
class PQ
{
 private:
 Node * root;
 void Push(int value, Node * node);
 int Pop(Node * node, Node * parent);
 void DeletePQ(Node * node);
 public:
 PQ();
 ~PQ();
 void Push(int value);
 int Pop();
 void DeletePQ();
 bool IsEmpty();
};
#endif

PQ.C:

#include "PQ.h"
PQ::PQ()
{
 root = NULL;
}
PQ::~PQ()
{
 DeletePQ();
}
void PQ::DeletePQ()
{
 DeletePQ(root);
}
void PQ::DeletePQ(Node * node)
{
 if(node != NULL)
 {
 DeletePQ(node->left);
 DeletePQ(node->right);
 delete node;
 }
}
void PQ::Push(int value)
{
 if(root != NULL)
 {
 Push(value, root);
 }
 else
 {
 root = new Node(value);
 }
}
void PQ::Push(int value, Node * node)
{
 if(value < node->value)
 {
 if(node->left != NULL)
 {
 Push(value, node->left);
 }
 else
 {
 node->left = new Node(value);
 }
 }
 else
 {
 if(node->right != NULL)
 {
 Push(value, node->right);
 }
 else
 {
 node->right = new Node(value);
 }
 }
}
int PQ::Pop()
{
 int value;
 if(root != NULL)
 {
 if(root->right != NULL)
 {
 value = Pop(root->right, root);
 }
 else
 {
 value = root->value;
 if(root->left != NULL)
 {
 Node * temp = root;
 root = root->left;
 delete temp;
 }
 else
 {
 delete root;
 root = NULL;
 }
 }
 }
 else
 {
 value = -1;
 }
 return value;
}
int PQ::Pop(Node * node, Node * parent)
{
 int value;
 if(node->right != NULL)
 {
 value = Pop(node->right, node);
 }
 else
 {
 value = node->value;
 if(node->left != NULL)
 {
 parent->right = node->left;
 }
 else
 {
 parent->right = NULL;
 }
 delete node;
 }
 return value;
}
bool PQ::IsEmpty()
{
 bool isEmpty;
 if(root == NULL)
 {
 isEmpty = true;
 }
 else
 {
 isEmpty = false;
 }
 return isEmpty;
}

• fernando.reyes: You need to add a constructor for Node, so you can initialize left, right and value in one line, and make your code shorter and clearer
• Michael Brandon Morris: @fernando.reyes Updated to include Node constructor.
• Sebastian Redl: If you just want a priority queue, a heap is more efficient than a binary tree.

Answer 1

• Handling booleans

  Computation of isEmpty is anti-idiomatic. Consider

   isEmpty = (root == NULL);
  

  Now it is easy to see that isEmpty is not needed at all. The whole method can be shortened to

  bool PQ::IsEmpty()
  {
   return root == NULL;
  }
  

• Pop return on failure

  Returning -1 on failure means that the tree cannot have nodes with -1 as a value (a caller cannot tell such node from a failure). Consider throwing an exception instead.

• Recursive Push

  Push doesn't need to be recursive:

  void PQ::Push(int value, Node * node)
  {
   while (1) {
   if (value < node->value) {
   if (node->left) {
   node = node->left;
   } else {
   node->left = new Node(value);
   return;
   }
   } else {
   if (node->right) {
   node = node->right;
   } else {
   node->right = new Node(value);
   return;
   }
   }
   }
  }
  

• Recursive Pop

  Pop needs not to be recursive either:

  int PQ::Pop(Node * node, Node * parent)
  {
   while (node->right) {
   parent = node;
   node = node->right;
   }
   do_actual_deletion
  }
  

Edit: as requested, no multiple returns, no infinite loops. I am not sure it is cleaner than the original.

 void PQ::Push(int value, Node * node)
 {
 Node ** insertionPoint = 0;
 while (insertionPoint == 0) {
 if (value < node->value) {
 if (node->left) {
 node = node->left;
 } else {
 insertionPoint = &node->left;
 }
 } else {
 if (node->right) {
 node = node->right;
 } else {
 insertionPoint = &node->right;
 }
 }
 }
 *insertionPoint = new Node(value);
 }

• Michael Brandon Morris: Should multiple return statements as in your Push function not be avoided?
• vnp: @michaelbmorris Yes, unless unifying them complicates the code. In fact my first draft had a single return (and a Node ** variable) but I decided that the posted version is cleaner.
• vnp: @michaelbmorris It is a very dogmatic point of view. Language features are meant to be used, as long as they make code cleaner. See the edit.
• Loki Astari: @michaelbmorris: Forcing a single return per function is a C habit so that resource allocation is done correctly. Because of RAII this is not required in C++ and thus this rule is superfolus. Thus code clarity should always trump this.
• vnp: @LokiAstari As a primarily C programmer I may assure that it is not a C habit. It is more a Pascal habit (though I prefer to say dogma).

Answer 2

First Observation

This is not a priority queue.
It is simply a binary tree. To have a priority queue you need to have both an data object and a way to define the order. Here your object is your order (there is a sub class of the problem were this holds true) but in the general case it does not.

Usually this is done by passing a functor that understands the priority (where operator< is the simplest version).

Code Review

I don't seem any stream types being used in the header file.

#include <iostream>

Don't include header files you don't need in header files.

Hide Internal Types

You should not define types that are public that you don't want people to use directly.

struct Node
{
 int value;
 Node * left;
 Node * right;
 Node(int value)
 : value(value), left(NULL), right(NULL)
 {
 }
};

This should be a private type defined inside PQ.

Naming conventions

In C++ naming conventions are a bit fluid. But generally the standard is to use identifiers with an initial uppercase letter as user defined types. While identifiers with an initial lowercase letter are objects and function names.

 void Push(int value);
 int Pop();
 void DeletePQ();
 bool IsEmpty();

I would have lowercased the first letter on all these.

The reason is that types are extremely important in C++. So you need to be able to distinguish types from objects.

Use the Initializer list

PQ::PQ()
{
 root = NULL;
}

In this case it's not going to matter. But this is habit that is good to get into and it makes your code look consistent.

PQ::PQ()
 : root(nullptr)
{}

Also C++11 introduced nullptr as a replacement to the more error prone NULL.

Pre-Conditions

Its normal to check pre-conditions and return early if these are not met. This makes the rest of the code flow more normally (I don;t need to check the end of the function for an else part).

void PQ::DeletePQ(Node * node)
{
 if(node != NULL)
 {
 DeletePQ(node->left);
 DeletePQ(node->right);
 delete node;
 }
}

I would write this as:

void PQ::DeletePQ(Node * node)
{
 if(node == NULL) {
 return;
 }
 DeletePQ(node->left);
 DeletePQ(node->right);
 delete node;
}

Change in style.

Unlike @vnp I am not worried about recursion when using binary trees. The whole point is that its not going to get that deep anyway (that's why you are using a tree). But even in the worst case and it goes linear you are unlikely to break the stack unless you are solving some big data solution and then you already know that and take precautions.

Sure this works. But I prefer a more functional style.

void PQ::Push(int value)
{
 if(root != NULL)
 {
 Push(value, root);
 }
 else
 {
 root = new Node(value);
 }
}

I would have written this as:

void PQ::Push(int value)
{
 root = Push(value, root);
}
Node* PQ::Push(int value, Node* node)
{
 if (node == nullptr) {
 return new Node(value);
 }
 Node*& next = (node.value < value)
 ? node->left
 : node->right;
 next = Push(next, value);
 return node;
}

Also by using this style re-balancing dynamically does not get that much harder.

This again I would use a more functional style:

int PQ::Pop()
{
 int value;
 if(root != NULL)
 {
 if(root->right != NULL)
 {
 value = Pop(root->right, root);
 }
 else
 {
 value = root->value;
 if(root->left != NULL)
 {
 Node * temp = root;
 root = root->left;
 delete temp;
 }
 else
 {
 delete root;
 root = NULL;
 }
 }
 }
 else
 {
 value = -1;
 }
 return value;
}

Like this:

int Pop()
{
 if (root == nullptr) {
 throw int(5); // Find a real object to throw
 }
 int result;
 root = Pop(root, result);
 return result;
}
Node* Pop(Node* node, int& result)
{
 if (result->right) {
 result->right = Pop(node->right, result);
 }
 else if (result->left) {
 result->left = Pop(node->left, result);
 }
 else {
 result = node.value;
 delete node;
 node = nullptr;
 }
 return node;
}

Const correctness.

Its important to get your functions const correct. There are a lot of situations where pass an object by const reference. When this happens you can only call const functions. So it is important to get this correct.

Dont test for a boolean result

bool PQ::IsEmpty()
{
 bool isEmpty;
 if(root == NULL)
 {
 isEmpty = true;
 }
 else
 {
 isEmpty = false;
 }
 return isEmpty;
}

Easyier to just do:

bool PQ::IsEmpty() const // NOTE: the const. State of object not changed.
{
 return root == nullptr;
}

Answer 3

My 5 cents

Consider return something here:

void PQ::Push(int value, Node * node)

DeletePQ()

Consider doing this inline:

inline void PQ::DeletePQ()
{
 DeletePQ(root);
}

Consider NULL check here and not the level down:

inline void PQ::DeletePQ()
{
 if (root)
 DeletePQ(root);
}
void PQ::DeletePQ(Node * node)
{
 if(node->left)
 DeletePQ(node->left);
 if(node->left)
 DeletePQ(node->right);
 delete node;
}

Consider using smart pointers

C++11 introduce std::unique_ptr.

If you can use C++11, check it and use it.

It will save you delete also you will not need to write your own destructor.

Go wild with recursion!

Currently I do not see anything that differentiate the Node and PQ.

Why not move all methods from PQ to Node?

Only one thing would stop me to do this and it is removing the root Node.

Templetize everything

Currently your data is int. Consider using template or at least use typedef or using.

using PG_value_type = int;
struct Node
{
 PG_value_type value;
 Node * left;
 Node * right;
 Node(int value)
 : value(value), left(NULL), right(NULL)
 {
 }
};
void PQ::Push(int PG_value_type, Node * node);
void PQ::Push(int PG_value_type);