Advertisement
Guest User

Untitled

a guest
Apr 20th, 2018
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.50 KB | None | 0 0
  1. PQ er CPP
  2. #ifndef PRIORITYQUEUE_CPP
  3. #define PRIORITYQUEUE_CPP
  4.  
  5. #include"priorityQueue.h"
  6. template<class ItemType>
  7. PQType<ItemType>::PQType(int max)
  8. {
  9. maxItems = max;
  10. heap.elements = new ItemType[max];
  11. numItems = 0;
  12. }
  13. template<class ItemType>
  14. PQType<ItemType>::~PQType()
  15. {
  16. delete []heap.elements;
  17. }
  18. template<class ItemType>
  19. bool PQType<ItemType>::isFull()const
  20. {
  21. return (numItems==maxItems);
  22. }
  23. template<class ItemType>
  24. bool PQType<ItemType>::isEmpty()const
  25. {
  26. return (numItems==0);
  27. }
  28. template<class ItemType>
  29. void PQType<ItemType>::MakeEmpty()
  30. {
  31. numItems = 0;
  32. }
  33.  
  34. template<class ItemType>
  35. void PQType<ItemType>::Dequeue(ItemType &item)
  36. {
  37. item = heap.elements[0];
  38. heap.elements[0] = heap.elements[numItems-1];
  39. numItems--;
  40. heap.ReheapDown(0,numItems-1);
  41. }
  42. template<class ItemType>
  43. void PQType<ItemType>::Enqueue(ItemType newItem)
  44. {
  45. numItems++;
  46. heap.elements[numItems-1] = newItem;
  47. heap.ReheapUp(0,numItems-1);
  48. }
  49. #endif
  50.  
  51. heap er CPP
  52. #ifndef HEAP_CPP
  53. #define HEAP_CPP
  54. #include"heap.h"
  55. template<class ItemType>
  56. void HeapType<ItemType>::ReheapDown(int root,int bottom)
  57. {
  58. int maxChild,rightChild,leftChild;
  59.  
  60. leftChild = 2*root + 1;
  61. rightChild = 2*root +2;
  62.  
  63. if(leftChild<=bottom){
  64. if(leftChild==bottom)
  65. maxChild = leftChild;
  66. else{
  67. if(elements[leftChild]<=elements[rightChild])
  68. maxChild = rightChild;
  69. else
  70. maxChild = leftChild;
  71. }
  72. if(elements[root]<elements[maxChild])
  73. {
  74. Swap(elements,root,maxChild);
  75. ReheapDown(maxChild,bottom);
  76. }
  77. }
  78. }
  79. template<class ItemType>
  80. void HeapType<ItemType>::ReheapUp(int root,int bottom)
  81. {
  82. int parent;
  83. if(bottom>root){
  84. parent = (bottom-1)/2;
  85. if(elements[parent]<elements[bottom])
  86. {
  87. Swap(elements,parent,bottom);
  88. ReheapUp(root,parent);
  89. }
  90. }
  91. }
  92. template<class ItemType>
  93. void Swap(ItemType *elements,int root,int bottom)
  94. {
  95. int temp = elements[root];
  96. elements[root] = elements[bottom];
  97. elements[bottom] = temp;
  98. }
  99. #endif
  100.  
  101. main er cpp
  102. #include <iostream>
  103. #include"priorityQueue.h"
  104.  
  105. using namespace std;
  106.  
  107. int main()
  108. {
  109.  
  110. PQType<int> pq(6);
  111. pq.Enqueue(8);
  112. pq.Enqueue(2);
  113. pq.Enqueue(9);
  114. pq.Enqueue(10);
  115.  
  116. int i;
  117. pq.Dequeue(i);
  118. cout<<i<<endl;
  119. pq.Dequeue(i);
  120. cout<<i<<endl;
  121. pq.Dequeue(i);
  122. cout<<i<<endl;
  123.  
  124. return 0;
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement