MinPQ I refered this Java sourse ftp://ftp.cs.princeton.edu/pub/cs226/bins/MinPQ.java

MinPQ.cpp

/*
 * PriorityQueue.cpp
 *
 *  Created on: 2013/10/27
 *      Author: tsu-nera
 *
 */

#include "PriorityQueue.h"
#include <iostream>

PriorityQueue::PriorityQueue(int size)
{
  this->pq = new Node[size+1];
  this->N = 0;
}

PriorityQueue::~PriorityQueue()
{
  delete pq;
}

void PriorityQueue::push(Node node)
{
  pq[++N] = node;
  swim(N);
}

bool PriorityQueue::isEmpty()
{ return N == 0; }

Node PriorityQueue::delMin()
{
  Node min = pq[1];
  exch(1, N--);
  sink(1);
  pq[N+1].no = 0;
  pq[N+1].cost = 0;
  return min;
}

void PriorityQueue::swim(int k)
{
  while (k > 1 && less(k/2, k))
  {
    exch(k, k/2);
    k = k/2;
  }
}

void PriorityQueue::sink(int k)
{
  while(2*k <= N)
  {
    int j = 2*k;
    if (j < N && less(j, j+1)) j++;
    if (!less(k, j)) break;
    exch(k, j);
    k = j;
  }
}

void PriorityQueue::exch(int i, int j)
{
  Node t = pq[i];
  pq[i] = pq[j];
  pq[j] = t;
}

bool PriorityQueue::isContain(Node node)
{
  for(int i=0; i < N+1; i++) {
    if (pq[i].no == node.no) {
      return true;
    }
  }
  return false;
}

bool PriorityQueue::less(int i, int j)
{
  return (pq[i].cost > pq[j].cost);
}

void PriorityQueue::update(Node node)
{
  for(int i=0; i < N+1; i++) {
    if (pq[i].no == node.no) {

      if ( pq[i].cost > node.cost ) {
        pq[i].cost = node.cost;
        exch(i,N);
        swim(N);
      }
      return;
    }
  }
}

void PriorityQueue::show()
{
  for(int i=0; i < N+1; i++) {
    std::cout << "(" << pq[i].no << ", " << pq[i].cost << ") ";
  }
  std::cout << std::endl;
}

MinPQ.h

/*
 * PriorityQueue.h
 *
 *  Created on: 2013/10/27
 *      Author: tsu-nera
 */

#ifndef PRIORITYQUEUE_H_
#define PRIORITYQUEUE_H_

struct Node{
public:
  Node(int no=0, double cost=0) : no(no), cost(cost) {}
  int no;
  double cost;
};

class PriorityQueue
{
public:
  PriorityQueue(int size);
  ~PriorityQueue();
  void push(Node node);
  bool isEmpty();
  Node delMin();
  void swim(int k);
  bool isContain(Node node);
  void update(Node node);
  void show();

private:
  Node* pq; // Priority Queue
  int N;    // queue count

  void sink(int k);
  void exch(int i, int j);
  bool less(int i, int j);
};

#endif /* PRIORITYQUEUE_H_ */