Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- PQ er CPP
- #ifndef PRIORITYQUEUE_CPP
- #define PRIORITYQUEUE_CPP
- #include"priorityQueue.h"
- template<class ItemType>
- PQType<ItemType>::PQType(int max)
- {
- maxItems = max;
- heap.elements = new ItemType[max];
- numItems = 0;
- }
- template<class ItemType>
- PQType<ItemType>::~PQType()
- {
- delete []heap.elements;
- }
- template<class ItemType>
- bool PQType<ItemType>::isFull()const
- {
- return (numItems==maxItems);
- }
- template<class ItemType>
- bool PQType<ItemType>::isEmpty()const
- {
- return (numItems==0);
- }
- template<class ItemType>
- void PQType<ItemType>::MakeEmpty()
- {
- numItems = 0;
- }
- template<class ItemType>
- void PQType<ItemType>::Dequeue(ItemType &item)
- {
- item = heap.elements[0];
- heap.elements[0] = heap.elements[numItems-1];
- numItems--;
- heap.ReheapDown(0,numItems-1);
- }
- template<class ItemType>
- void PQType<ItemType>::Enqueue(ItemType newItem)
- {
- numItems++;
- heap.elements[numItems-1] = newItem;
- heap.ReheapUp(0,numItems-1);
- }
- #endif
- heap er CPP
- #ifndef HEAP_CPP
- #define HEAP_CPP
- #include"heap.h"
- template<class ItemType>
- void HeapType<ItemType>::ReheapDown(int root,int bottom)
- {
- int maxChild,rightChild,leftChild;
- leftChild = 2*root + 1;
- rightChild = 2*root +2;
- if(leftChild<=bottom){
- if(leftChild==bottom)
- maxChild = leftChild;
- else{
- if(elements[leftChild]<=elements[rightChild])
- maxChild = rightChild;
- else
- maxChild = leftChild;
- }
- if(elements[root]<elements[maxChild])
- {
- Swap(elements,root,maxChild);
- ReheapDown(maxChild,bottom);
- }
- }
- }
- template<class ItemType>
- void HeapType<ItemType>::ReheapUp(int root,int bottom)
- {
- int parent;
- if(bottom>root){
- parent = (bottom-1)/2;
- if(elements[parent]<elements[bottom])
- {
- Swap(elements,parent,bottom);
- ReheapUp(root,parent);
- }
- }
- }
- template<class ItemType>
- void Swap(ItemType *elements,int root,int bottom)
- {
- int temp = elements[root];
- elements[root] = elements[bottom];
- elements[bottom] = temp;
- }
- #endif
- main er cpp
- #include <iostream>
- #include"priorityQueue.h"
- using namespace std;
- int main()
- {
- PQType<int> pq(6);
- pq.Enqueue(8);
- pq.Enqueue(2);
- pq.Enqueue(9);
- pq.Enqueue(10);
- int i;
- pq.Dequeue(i);
- cout<<i<<endl;
- pq.Dequeue(i);
- cout<<i<<endl;
- pq.Dequeue(i);
- cout<<i<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement