Does anyone know how to implement a Priority queue using a heap data structure?

i did tried to do it. but i couldn't get to do the whole part. i am not even sure about the code i have. i would really appreciate the it if some one can help me out of this problem. thank you.

 

Could you post the code you've got, explain what it should do, and how it goes wrong? Does it compile? If not what errors do you get? If it runs and doesn't behave as you expect, could you give example input and what output you (a) got and (b) expected?

By "heap data structure" are you referring to this:
http://en.wikipedia.org/wiki/Heap_(computer_science)
Which variant are you using, if any?

 

Implement this Priority queue using heap data structure in c++ and should work in microsoft visual studio. This is the code i have. I have implemented some of the functions, but it will be confusing. so can you please help me out with this. i would really appreciate it if you can help me out with this. thank you.

Code:

#include <assert.h>    // Provides [URL=http://www.go4expert.com/articles/c-cpp-assert-function-t27488/]assert[/URL] function 
#include <iomanip>   // Provides setw 
#include <iostream>  // Provides cin, cout 
#include <math.h>      // Provides log2 
#include "pqueue2.h"  
using namespace std;  

PriorityQueue::PriorityQueue( ) 
{     // implement this. }  

void PriorityQueue::insert(const Item& entry, unsigned int priority) 
{     // implement this. }
 
PriorityQueue::Item PriorityQueue::get_front( )
 {     // implement this. }  

bool PriorityQueue::is_leaf(size_t i) const 
// Precondition: (i < many_items) 
// Postcondition: If heap[i] has no children in the heap, then the function
 // returns true. Otherwise the function returns false.
 {     // implement this. }  

size_t PriorityQueue::parent_index(size_t i) const 
// Precondition: (i > 0) && (i < many_items)
 // Postcondition: The return value is the index of the parent of heap[i]. 
{     // implement this. }  

unsigned int PriorityQueue::parent_priority(size_t i) const 
// Precondition: (i > 0) && (i < many_items) 
// Postcondition: The return value is the priority of the parent of heap[i]. 
{     // implement this. }  

size_t PriorityQueue::big_child_index(size_t i) const 
// Precondition: !is_leaf(i) 
// Postcondition: The return value is the index of one of heap[i]'s children. 
// This is the child with the larger priority. 
{     // implement this. }

 unsigned int PriorityQueue::big_child_priority(size_t i) const 
// Precondition: !is_leaf(i) 
// Postcondition: The return value heap[big_child_index(i)].priority 
{     // implement this. }  

void PriorityQueue::swap_with_parent(size_t i) 
// Precondition: (i > 0) && (i < many_items)
 // Postcondition: heap[i] has been swapped with heap[parent_index(i)] 
{     // implement this. }

When you implement this it should work on microsoft visual studio.

 

Please use code blocks when posting code.

Well, I'm happy to help, but I asked some questions and all you said in reply was "Please help". What form of help do you want, and why haven't you answered my questions?

> I have implemented some of the functions

No you haven't. They all say "{ // implement this. }".

 

Dear sir,
As i said, i did some work on this implementation. If you want i can send it to you. here it is:
Response Details:

Code:

#include <iostream.h>
#include <iomanip.h>
#include <fstream.h>
#include<conio.h>
struct node 
{
    int weight;
    unsigned char value;
    const node *child0;
    const node *child1;
    node( unsigned char c = 0, int i = -1 ) 
    {
        value = c;
        weight = i;
        child0 = 0;
        child1 = 0;
    }
    node( const node* c0, const node *c1 ) 
    {
        value = 0;
        weight = c0->weight + c1->weight;
        child0 = c0;
        child1 = c1;
    }
    bool operator<( const node &a ) const 
    {
        return weight < a.weight;
    }
    void traverse( string code = "" )  const;
};
 
void node::traverse( string code ) const
{
    if ( child0 ) {
        child0->traverse( code + "0" );
        child1->traverse( code + "1" );
    } else {
        cout << " " << value << "      ";
        cout << setw( 2 ) << weight;
        cout << "     " << code << endl;
    }
}
 
void count_chars( int *counts )
{
    for ( int i = 0 ; i < 256 ; i++ )
        counts[ i ] = 0;
    ifstream file( "input.dat" );
    if ( !file ) {
        cerr << "Couldn't open the input file!\n";
        throw "abort";
    }
    file.setf( ios::skipws );
    for ( ; ; ) {
        unsigned char c;
        file >> c;
        if ( file )
            counts[ c ]++;
        else
            break;
   }
}
main()
{
    clrscr();
    int counts[ 256 ];
    count_chars( counts );
    priority_queue< vector< node >, greater<node> > q;

    while ( q.size() > 1 ) {
        node *child0 = new node( q.top() );
        q.pop();
        node *child1 = new node( q.top() );
        q.pop();
        q.push( node( child0, child1 ) );
    }
    cout << "Char  Symbol   Code" << endl;
    q.top().traverse();
    return 0;
}

but this is not working in microsoft visual studio c++. i thought if i post this, people will be confused. so i asked them to write in c++. i have my own test file, header file. when i tried to debug it, its giving me errors.

 

"this is not working"
"its giving me errors"

Not much to go on. I've already asked the following questions:

explain what it should do, and how it goes wrong? Does it compile? If not what errors do you get? If it runs and doesn't behave as you expect, could you give example input and what output you (a) got and (b) expected?

Try answering them. Or if you don't want to/can't answer them, say so, and say what you expect instead. I can't help you if you simply refuse to answer my questions.

By the way, you should know that help from me doesn't comprise simply giving you the answer. You must work through this, as far as I'm concerned, because that's how you learn programming. I will help you understand what you must do, but I'm not going to do it for you.

 

Also, you didn't use a code block, so as you see all the formatting was lost. It's very easy to use a code block, type [ code ] before the code and [ /code ] after the code, except without spaces, and it comes out like this:

Code:

int main()
{
    printf("Hello world\n");
    return 0;
}