Chapter 6 Answers

powered by FreeFind

Modified: 

Heaps

Question - Which of these trees satisfy the heap definition? Only the first.

Why not? 2nd is missing left child; 3rd has value 5 node parent of value 6.

Question Do the arithmetic to determine the array index number of:

  1. parent of A[9] = A[ ë9/2û ] = A[ 4 ]
  2. left child of A[2] = A[2*2] = A[ 4 ]
  3. right child of A[2] = A[2*2+1] = A[ 5 ]

Question What array index holds the largest element in a max-heap? A[ 1 ]

               The smallest? We don't know.

                The max-heap below has height 3. What size array would be required if the max-heap below were full? 15

                How many for a full max-heap of height h? 2h+1-1

Heapify

Question - Give an algorithm to determine if an array is a heap.

static boolean isaHeap(int A[], int i) {
   if( right(i) > A.length-1) return true;    // last child
   if( !heapProperty(A, i)) return false;
   return isaHeap(A, left(i)) && isaHeap(A, right(i));
}
// true when i has no children (a leaf) or i > left and right children of i

static boolean heapProperty(int A[], int i) {
     return right(i) >= A.length-1 || (A[i] > A[ left(i) ] && A[i] > A[ right(i) ]);
}
static int parent(int i) { return i/2; }
static int left( int i )    { return 2*i; }
static int right( int i )  { return 2*i+1; }

What is the recurrence equation?

All algorithms except isaHeap() run in constant time, there is no combine time. 

T(1) = c

T(n) = 2T(n/2) + c

Determine the run time.

For full tree.

Master Theorem

a=2 b=2 f(n)=c= O(1)  

nlog22 = n1 = n

f(n) = O(nlog22-1 ) = O(n0) = O(1)

By Case 2: T(n) Î Q(nlog22) = Q(n1) = Q(n)

Does this make sense?

Consider there are n nodes in the heap and all are examined.

Build-Max-Heap

Question - What does O(n lg n) assume in terms of the Max_Heapify tree height? lg n examined but not true in upper-level nodes.
 

Question

We started with

T(n) = O(n lg n)

and tightened the bounds to

T(n) = O(n)

Think about what happens to the depth with each application of Max-Heapify.

What simplifying assumption did we make to come up with T(n) = O(n lg n)?

We assumed that Max_Heapify reaches the bottom level of the tree, lg n, for each of the ën/2û iterations of Build-Max-Heap. In fact, after a parent has been visited once to arrange so the max-heap property holds, it is never visited as a parent again.
 

Analysis of Heapsort

Question - Remember our initial mistake on thinking Build_Max_Heap was O(n lg n) by assuming a tree of height lg n for each of the n applications of Max_Heapify - are we making the same mistake again? No. Max-Heapify starts at node number 1 each time with possibly the smallest value in the heap. May require traversing lg n levels.

 

Priority Queue

Question

Suggest an algorithm for deleting the value at the head of the queue, the value at array location 1.

A[1] « A[heapsize]

heapsize --

Max-Heapify(A, 1)

Is the max heap property maintained? Yes.

What is the estimated O run time? O(lg n) of Max-Heapify

Question

Trace the effect of Heap_Increase_Key (A, i=2, key=6). Why is this result necessary? Prints error because replacing 14 with 6 would violate max-heap property.

What is the estimated worst case run time order? O(lg n) when new key is largest value in heap and i is a leaf on left side. The best? W(1) when new key is less than or equal the parent.

Question

What is the array before and after insertion?

1 2 3 4 5 6 7 8 9 10
9 6 8 2 5 7        
1 2 3 4 5 6 7 8 9 10
10 6 9 2 5 7 8      

What is the worst case run time order? O(lg n)

Is the Line 2, A[heapsize[A]] ¬ -¥, necessary? Yes. For Heap_Increase_Key error test.

 

Heap_Extract_Max

Question

Question

Question

Question