CS301 Quiz 2 Set 3

Data Structures · Lecture No. 3633 · Reading Material

Data Structures and Algorithm Analysis in C++ Chapter. 6, 8 6.3, 8.1

Summary

Priority Queue Using Heap

Heap Sort

Equivalence Relations

Priority Queue Using Heap

InAs discussed in the previous lecture, we discussed a lot about buildHeap.generally prefer to employ the buildHeap to construct If we have all the data available thenheap instead of using insert we can use buildHeap to construct heap. buildHeap is optimized as compared to insert method because it takes lesserthan Nlog2N time. We also proved a theorem that if the number of linkes in the tree are counted then the sum of heights of the nodes is N-h-1. We have been iteratinglot of times that the best use of heap is implementing priority queues. Lets try to develop a class of priority queue using heap. You might be remembering, when we did bank simulation, weused a priority queue but that was implementedusing an array. Now, we will implement the same queue using a heap. We will modify the same code to use heap instead of any array. The interface (.h file) will remain the same but the implementation (.cpp file) will be changed. As .cpp file will change, so let’s see the .cpp code below:

simulation. We are including .cpp files here as we have used templates of C++. At the second line, we have included heap.cpp. In the third line, we are defining a constant PQMAX, declaring the maximum size of the priority queue to be 30. In line 4, class PriorityQueue is declared. public keyword is given at line 6 indicating that all class members below will be of public scope. Line 7 is starting the class constructor’s Next isthe remove method that was sometimes, named as dequeue in our previous

We see the insert method now line by line. It is accepting a pointer type parameter of type Event. As the heap may become full if we keep on inserting elements into it, therefore, the first line inside the insert function is checking if the heap has gone full. If the heap is not full then the if-block is entered. At line 33 inside the if-block, an element that is passed as a parameter to insert method of heap is inserted into the queue by calling the insert method of heap. This insert call will internally perform percolate up and down operations to place the new element at its correct position. The returned value 1 indicates the successful insertion in the queue. If the heap has gone full then a message is displayed that ‘insert queue is full’. Note that we have used the word queue not heap in that message. It has to that way otherwise the users of the PriorityQueue class are unaware of

array). Next line is returning 0indicating that the insert operation was not successful. Below to insert, we have full() method. This method returns an int value. Internally, it is calling isFull() method of heap. The full() method returns whatever is returned by the isFull() method of heap. Next is length() method, as the size of heap is also the size of the queue, therefore, length() is internally calling the getSize() method of heap.

implementation with array. You must be remembering when we implemented the PriorityQueue with an array, at each insertion in the if we have all the required data. buildHeap is optimized as compared to insert method as it takes lesser time than Nlog2N . In the previous discussion, we had proved a theorem that if the number of links in the tree are counted, the sum of all is N-h-1. We have been iterating a lot of times that the best use of heap is priority queue’s implementation. Let’s try to develop a class of priority queue with the help of a heap. You are very familiar with the concept of bank simulation. While explaining the bank simulation, we had used a priority queue that was implemented by using an array. Now, we will implement the same queue with the help of a heap. For this purpose, the code will be modified so that heap is used in place of array. The interface (.h file) will remain the same. However, the implementation (.cpp file) will be changed. Let’s see the following cpp code, which also shows the change in the .cpp file:

1. #include “Event.cpp” 2. #include “Heap.cpp” 3. #define PQMAX 30 4. class PriorityQueue 5. 6. public: 7. PriorityQueue() 8. 9. heap = new Heap < Event> ( PQMAX ); 10. 11. 12. ~PriorityQueue() 13. 14. delete heap; 15. 16. 17. Event * remove() 18. 19. if( !heap->isEmpty() ) 20. 21. Event * e; 22. heap->deleteMin( e ); 23. return e; 24. 25. cout << "remove - queue is empty." << endl; 26. return (Event *) NULL; 27. 28. 29. int insert(Event * e) 30. 31. if( !heap->isFull() ) 1. 33. heap->insert( e ); 34. return 1; 35. 36. cout << "insert queue is full." << endl; 37. return 0; 38.