C++ priority queue as binary heap

have been making progress, but still can't figure out where my infinite loop is...

header file:

#include <string>

class priority_queue_overflow{};    //if insert tries to exceed the size of A then throw priority_queue_overflow() 
class priority_queue_underflow{};   //if extract_min tries is called on an empty heap then throw priority_queue_overflow() 

class priority_queue {
private:

  class pair {
  public:
    std::string object;
    double key;
  };

  pair* A;  //the array used to store the heap
  int heapsize; //the current heap size
  int size; //the current size of the array: does not change

  void heapify(int k);  //as described in Cormen et al

public:

  priority_queue(int n); //don't forget to allocate the array of size n+1 as we don't use slot zero
  ~priority_queue();    //delete the array

  bool empty(); //true/false depending upon whether the heap is empty
  void insert(std::string s, double priority); //add s to the heap with the given priority as its key
  std::string extract_min();    //remove the string of lowest key and return that string

  operator std::string();
};

cpp file:

/**
 * implementing the priority queue as a binary heap
 *
 */

#include <iostream>
#include <istream>
#include <ostream>
#include <sstream>
#include <map>
#include <algorithm>

#include "binary_heap.hpp"

/***********************
 *** inline functions
 ***********************/
inline开发者_StackOverflow中文版 int left(int i) { return  2*1; } // ( i << 1 )

inline int right(int i) { return 2*i+1; } // (i << 1 | 1)

inline int parent(int i) { return i/2; } // ( i >> 1 )


/*********************
 *** constructor
 *********************/
priority_queue::priority_queue(int n)  //don't forget to allocate the array of size n+1 as we don't use slot zero 
  :heapsize(0), size(n)
{
  A = new pair[n+1];
}


/*********************
 *** destructor
 *********************/
priority_queue::~priority_queue()  //delete the array
{
  delete[] A; // iterrate through delete each elem
}


/*******************************************
 *** heapify * finds max of three things
 *******************************************/
void priority_queue::heapify(int k)
{
  std::cout<<"HERE HEAP"<<'\n';
  pair smallest = A[k];
  int pos = k;        

  //only treat child as object if it's inside heap
  if (left(k) <= heapsize and A[left(k)].key < A[pos].key) {

    // update variables
    smallest = A[left(k)];
    pos = left(k);
  }

  // identical for right
  if (right(k) <= heapsize and A[right(k)].key < A[pos].key) {

    // update variables
    smallest = A[right(k)];
    pos = right(k);
  }

  // after both if's exectued: smallest and pos contain smallest key

  // only need to do something if pos is !=i
  std::cout<< pos <<" == "<< k<<'\n';

  if (pos != k) {

    // swap items
    std::swap(A[k], A[pos]);

    // go recursive   
    heapify(pos);
  }
}


/****************
 *** empty
 ****************/
bool priority_queue::empty()
{
  return (heapsize == 0);
}


/****************
 *** insert
 ****************/
void priority_queue::insert(std::string s, double priority)  //add s to the heap with the given priority as its key
{
  if (heapsize == size) {
    throw priority_queue_overflow();
  }

  ++heapsize;  
  A[heapsize].object = s;
  A[heapsize].key = priority;

  int i(heapsize);
  while (i > 1 and A[parent(i)].key > A[i].key) {
    std::swap(A[parent(i)], A[i]);
    i = parent(i);  
  }
}


/*******************
 *** extract_min
 *******************/
std::string priority_queue::extract_min()  //remove the string of lowest key and return that string
{
  if (heapsize == 0) {
    throw priority_queue_underflow();
  }

  std::string ans = A[1].object;
  A[1] = A[heapsize];
  --heapsize;
  heapify(1);
  return ans;        
}


/**********************************
 *** function operator overload
 **********************************/
priority_queue::operator std::string()
{
  std::stringstream text; 
  int i(1);  

  while (i <= size) { 
    text << A[i].object << std::endl;
    ++i;
  } 
  return text.str(); 
}

You should try to extract the smallest problem you're having trouble with. It would be easier to help if you could narrow down exactly what your question is.

If you're having trouble understanding how to use the pair class from your example in an array context maybe the following small (self-contained) example will help:

#include <iostream>
#include <string>

class pair {
public:
    std::string object;
    double key;
};

void print_pair(const pair& p) {
    std::cout << p.object << " = " << p.key << std::endl;
}

int main() {

    // allocated on the stack, dies at the end of the function
    pair p;

    p.object = "question";
    p.key = 42;
    print_pair(p);

    pair* pp = new pair();
    (*pp).object = "6 * 10";  // We need to dereference the pointer, kinda clumsy syntax
    pp->key = 60; // Luckily there's a short hand! pp[0].key = 60; is the same thing
    print_pair(*pp);
    delete pp; // remember to clean up!

    pair* ap = new pair[10]; // allocate 10 pairs
    ap[0].object = "zero"; 
    (*(ap + 0)).key = 0; // same thing, ap[N] is the same as *(ap + N)
    print_pair(ap[0]);
    delete []ap; // remember to use the [] syntax when you new'ed like that!
}

ok, finally got it... thanks errbody :-)

/**
* implementing the priority queue as a binary heap
*
*/

#include <iostream>
#include <istream>
#include <ostream>
#include <sstream>
#include <map>
#include <algorithm>

#include "binary_heap.hpp"

/***********************
 *** inline functions
 ***********************/
inline int left(int i) { return i << 1; }

inline int right(int i) { return i << 1 | 1; }

inline int parent(int i) { return i >> 1; }


/*********************
 *** constructor
 *********************/
priority_queue::priority_queue(int n)  
{
  heapsize = 0;
  size = n;

  // don't forget to allocate the array of size n+1 as we don't use slot zero 
  A = new pair[n+1];
}


/*********************
 *** destructor
 *********************/
priority_queue::~priority_queue()  //delete the array
{
  delete[] A;
}


/*******************************************
 *** heapify * finds max of three things
 *******************************************/
void priority_queue::heapify(int k)
{
  pair smallest = A[k];
  int pos = k;        

  //only treat child as object if it's inside heap
  if (left(k) <= heapsize and A[left(k)].key < A[pos].key) {

    // update variables
    smallest = A[left(k)];
    pos = left(k);
  }

  // identical for right
  if (right(k) <= heapsize and A[right(k)].key < A[pos].key) {

    // update variables
    smallest = A[right(k)];
    pos = right(k);
  }

  // after both if's exectued: smallest is pair with smallest key and
  // pos is index of that pair in A[]

  // only need to do something if pos is NOT the same position
  // that we were passed in originally
  if (pos != k) {

    // swap items
    std::swap(A[k], A[pos]);

    // go recursive to trickle down...
    heapify(pos);
  }
}


/****************
 *** empty
 ****************/
bool priority_queue::empty()
{
  return (heapsize == 0);
}


/****************
 *** insert
 ****************/
void priority_queue::insert(std::string s, double priority)  //add s to the heap with the given priority as its key
{
  if (heapsize == size) {
    throw priority_queue_overflow();
  }

  // make room for insert
  ++heapsize;  
  // assign string arg to object member
  A[heapsize].object = s;
  // assign priority arg to key member
  A[heapsize].key = priority;

  // loop through and trickle up as needed
  int i(heapsize);
  while (i > 1 and A[parent(i)].key > A[i].key) {
    std::swap(A[parent(i)], A[i]);
    i = parent(i);  
  }
}


/*******************
 *** extract_min
 *******************/
std::string priority_queue::extract_min()  //remove the string of lowest key and return that string
{
  if (heapsize == 0) {
    throw priority_queue_underflow();
  }

  std::string ans = A[1].object;
  A[1] = A[heapsize];
  --heapsize;
  // trickle down as needed
  heapify(1);
  return ans;        
}


/**********************************
 *** function operator overload
 **********************************/
priority_queue::operator std::string()
{
  std::stringstream text; 
  int i(1);    

  while (i <= size) { 
    text << A[i].object << std::endl;
    ++i;
  } 
  return text.str(); 
}