Tutorial Week 8
Objectives : to learn more about heaps and priority queue Reference Carrano chapter on ADT table.First try some of the self-test exercises at end of chapter eg ex 2,5,6,7.
- * Trace through heapsort on the following array 4,7,3,6,9. Show both
the actual array and the visualised complete tree exactly as Carrano does in
Figure "A trace of heapsort" (and as shown is short version of heapsort).
- * Write an algorithm in c++ which if passed an int array A and its size n
(representing a valid max-heap) and an integer k will return
the value of the parent of k (if it exists) else INT_MIN?
int getParent(int a{], int n, int k) // pre : A[0..n-1] is a max-heap // post : returns value of parent of k if it exists else INT_MIN - What is the output of the following program excerpt?
priority_queue
pq; pq.insert(5); pq.insert(9); pq.insert(2); pq.insert(3); pq.pop(); cout << pq.top(); pq.pop(); cout << pq.top(); cout << pq.size(); cout << pq.top(); pq.pop(); cout << pq.size(); cout << pq.top(); - Write an algorithm in C++ which if given an int array A and its
size n will return true if A is a max-heap and otherwise false.
bool isMaxheap(int A[], int n) // returns true if A is a max-heap and otherwise false.
- Would an array sorted in descendng order be a valid max-heap?
- Write an algorithm in c++ which if passed a binary search tree t
will create a valid max-heap in array A.
Hint : where is largest value in b.s.t. ? where is largest value in max-heap?? How would you display b.s.t. in descending order?