C++プライオリティキュー

Question

が進展しているが、私の無限ループがどこにあるか、まだ把握することはできません...

ヘッダファイル：

#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ファイル：

/** 
* 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 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(); 
} 

Answer 1

[OK]を、最終的にそれを得ました。 ..ありがとう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(); 
} 

Answer 2

問題が発生している最小の問題を抽出してください。質問の内容を正確に絞り込むことができれば、助けが簡単になります。

トラブル多分、次の（自己完結型）小さな例が役立つ配列コンテキストであなたの例からpairクラスの使用方法を理解した場合：

#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! 
}