Instantly share code, notes, and snippets.

# tsu-nera/MinPQ.cpp Created Nov 4, 2013

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 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_ */