Skip to Content

COMP225 : Algorithms and Data Structures

Week 8

Heaps and Priority Queues all self-test answers at back of book 
  1. heapsort
4 7 3 9 6
step 1
  using for i := n/2 down to 0 
     heaprebuild (a,2,5)   4 7 3 9 6
     heaprebuild (a,1,5)   4 9 3 7 6
     heaprebuild (a,0,5)   9 7 3 4 6
step 2 keep swapping a[0],a[last] and rebuild heap
           7 6 3 4  |  9
           6 4 3    | 7 9
           4 3     | 6 7 9
           3  | 4 6 7 9
           3 4 6 7 9

  2. int parent(int a[], int n, int k)
(
    if (k<=0 || k >=n )
      return INT_MIN;
    else return a[(k-1)/2]
}


  3. bool isHeap (int a[], int n)
{
    for (int i = n-1; i > 0; i--)
      if (a[(i-1)/2] < a[i])
         return false;
    
    return true;
}
    can go other way - probably more error prone 
    bool isHeap (int a[], int n)
{
   for (int i = n/2 ; i >= 0; i--)
   {
      if (i*2+1 < n && a[i*2+1] > a[i])
          return false;
      if (i *2+2  a[i])
          return false;
   }
   return true; 
}
    O(n) algo can we do better? no because have to examine each element 
  4. assuming  node defined as 
  struct node
  {
      int key;
      node *left;
      node *right;
  };

void mkheap(node *t,  int a[], int &i)
{
    if (t != NULL)
    {
        mkheap(t->right,a,i);
        a[++i] = t->key;
        mkheap(t->left,a,i);
    }
}