-
-
Save iwatakeshi/1aed40f56f100931582d53d5f0dbeb43 to your computer and use it in GitHub Desktop.
MinPQ
I refered this Java sourse ftp://ftp.cs.princeton.edu/pub/cs226/bins/MinPQ.java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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