Skip to Content

COMP225 : Algorithms and Data Structures

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.

  1. * 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

  2. * What is the output of the following program excerpt? 
      priority_queue  pq;
  pq.push(5);  
  pq.push(9);  
  pq.push(2);  
  pq.push(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();

  3. * Trace through heapsort on the following array 4,7,3,6,9. Show just the actual array after each pass (easier to submit but may be helpful to draw complete tree as well on scrap paper for your own benefit). Use the more efficent way to create the heap (step 1).

    Submit above answers to Blackboard

  4. 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.

  5. Would an array sorted in descending order be a valid max-heap?

  6. Write a function 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?

  7. Consider the files provided for practical week 8 from Carrano. What is the purpose of HeapException.h? What are exceptions? Consider how the other files are used.
All enquiries to Ros Ballantyne