c++ - 优先队列排序 [C++]

Question

我有一个任务到期，它要求我将排序方法添加到我为上一个任务所做的优先级队列中。

好吧，我确实添加了排序功能，但我不确定如何用它完成我的 main，因为 main 似乎已经对队列进行了排序。我确实有一个 main 可能是什么样子的例子，但我相信教授希望我们使用我们之前提交的内容，所以我坚持要做什么。请帮忙。

哦，我的最后一个作业确实被扣了一分，他留下的评论只是“调用 enqueue() 时出现段错误”。我给他发了一封电子邮件，这是什么意思，他没有回复(昨天给出了成绩)。我认为错误来自于未在第 90 行调用 malloc。

#include <stdlib.h> //NEEDED TO RUN calloc
#include <cstdio> // NEEDED TO RUN perror
#include <iostream>

using namespace std;

// c-style struct
// node used to implement linked list
typedef struct _node
{
    int value;
    struct _node *next;
}
node;

/* Standard Stack LIFO ADT */
class Priority_Queue
{

    /* tracks number of nodes in Priority_Queue */
    int nNodes;
    /* keeps track of first node in Priority_Queue */
    node *head;
    void     sort( void ); //Sort linked list using selection sorting algorithm

    //anything above public is private
    public:

        Priority_Queue( void ); //find a constructor everytime the user             extanjiates Priority_Queue object.

        void    enqueue( int );  //insert node/ enqueue on an integer.
        void    dequeue( void );  //remove node/ dequeue off node from the top.
        bool    empty( void );  //test whether Priority_Queue is empty
        int     size( void );  //return size
        int     top( void );  // access top of the Priority_Queue/ next node.
        int     back( void );
};

/* init head and nNodes */
Priority_Queue::Priority_Queue( void )
{
    head = NULL; //everytime a user enstantiates one of the Priority_Queues
    nNodes = 0; // so we know how many nodes are sitting on our Priority_Queue.
}

/* place new node at top of Priority_Queue */
void Priority_Queue::enqueue( int value ) //enqueue on a value/ user wants     to place a Priority_Queue
{

    if( head == NULL )
    {
        if(( head = (node*)calloc(1, sizeof(node))) == NULL )
        {
            perror( "Could not calloc memory" );
        }
        else
        {
            head->value = value;
            nNodes++; // increase the number of nodes in link list
        }
    }
    else
    {
        node *temp;

        if( ( temp = (node*)malloc( sizeof( node ) ) ) == NULL ) //malloc     because both values for stut will be set immediatly
        {
            perror( "Could not malloc memory" );
        }
        else
        {
            temp->value = value;  //
            node* p = head;

            if ( value<head->value )
            {
                temp -> next = head;
                head = temp;
                temp = NULL;
            }
            while (p->next != NULL && p->next->value<value )
            {
                p = p-> next; // p is pointintint to the next node
            }
            temp->next = p->next;
            p->next = temp;
            temp = NULL;
            nNodes++; // increase the number of nodes in link list
        }
        //malloc( sizeof (node));
    }

}

/* remove the first node from top of Priority_Queue */
void Priority_Queue::dequeue( void )
{
    node *temp;

    if( head != NULL ) // allow users to keep calling dequeue even if it is empty
    {
        temp = head;
        head = head->next; // head is now pointing to 3

        free( temp );
        temp = NULL;

        nNodes--; //decrease node count for the Priority_Queue
    }

}

/* return true if Priority_Queue is empty */
bool Priority_Queue::empty( void )
{
    return ( head == NULL ); //valuated as true or false.
}

/* return number of nodes in Priority_Queue */
int Priority_Queue::size( void )
{
    return nNodes; //PLACING RESPONSIBILITY ON USER TO REMEMBER 28:00 part1
}

/* return value of node at top of Priority_Queue */
int Priority_Queue::top( void )
{
    return head->value; // PLACING RESPONSIBILITY ON USER TO REMEMBER 28:00 part1
}

int Priority_Queue::back( void )
{
    node *p = head;
    while (p->next != NULL)
    {
        p = p->next;
    }
    return p->value; //
}

void Priority_Queue::sort( void )
{
        node *temp;
    bool onward = true; //while loop set to true
    //compare each pair of adjacent elements
    //switches elements if in wrong order
    //Continues operations until elements are sorted.
    while( onward )
    {
        // onward set to false so just in case it is sorted, it will loop through the elements.
        for( temp = head, onward = false; temp->next != NULL; temp = temp->next )
        {
            //Check to see if current element is greater than the next
            if( temp->value > temp->next->value )
            {
                //swapping current elements value
                int a = temp->value;
                temp->value = temp->next->value;
                temp->next->value = a;
                onward = true; //
            }
        }
    }
}

int main( void )
{
    /* instantiate new Priority_Queue */
    Priority_Queue my_Priority_Queue = Priority_Queue();
    int i = 0;
    /* enqueue some values onto Priority_Queue */
    for( i = 0; i < 10; i++ )
        my_Priority_Queue.enqueue( i );
    /* print values stored in Priority_Queue until Priority_Queue is empty */
    while( !my_Priority_Queue.empty() )
    {
        cout << "Value: " << my_Priority_Queue.top() << endl; // Give access to the top of the Priority_Queue.
        my_Priority_Queue.dequeue();    // dequeue the top off so to see a different node at the top in the next line.
        cout << "Node Count: " << my_Priority_Queue.size() << endl << endl;
    }
    my_Priority_Queue.dequeue();

    return 0;
}

Answer 1

优先级队列通常具有获取最高优先级元素的功能。

要对所有元素进行排序，您需要做的就是将元素一个一个弹出，它们将按排序顺序排列。

通常情况下，优先级队列是用堆来实现的，将堆作为优先级队列的排序算法称为heapsort。

由于您没有给出优先级队列代码，因此以 std::priority_queue 为例，以下是您如何获得排序的元素列表:

template<class T, class Container, class Compare>
std::vector<T> get_sorted(std::priority_queue<T, Container, Compare> pq)
{
  std::vector<T> sorted;
  sorted.reserve(pq.size());
  while (!pq.empty())
  {
    sorted.push_back(pq.top());
    pq.pop();
  }
  return sorted;
}