Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
MinPQ I refered this Java sourse ftp://ftp.cs.princeton.edu/pub/cs226/bins/MinPQ.java
/*
* 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;
}
/*
* 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_ */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment