i
of
the heap. Assume that functions Percolate_Down
and
Percolate_Up
exist, with prototypes
void Percolate_Down( ElementType * heap, int size, int i); void Percolate_Up( ElementType * heap, int size, int i);where
heap
is the array of elements, and size
is the
current number of elements. Assume that i
is correctly given
to you, i.e., assume 1 <= i <= size
.
Start from the following prototype
void Delete( ElementType * heap, int & size, int i);
Solution:
The trick here is that a percolate up operation may be required in
some instances! Otherwise, it is very similar to the delete min
operation.
{ heap[i] = heap[size--]; if ( i == 1 || heap[i] > heap[i/2] ) Percolate_Down( heap, size, i ); else Percolate_Up( heap, size, i ); }
Solution:
2 through 7. It could be one of the two children of the root or it
could be one of the grandchildren of the root.
Solution:
through n. This is any location that has
no children.
Solution:
, because each of the
locations
identified in the previous problem must be searched.
Build_Heap
function.) Then show the heap after the minimum
value is removed. You may show the heap as a tree rather
than as an array. The heap is ordered so that the minimum value is at
the root.
Solution:
Root
, to the root of a
leftist heap of floating point values. Suppose you are also given a
pointer, P
, to a particular node in the leftist heap. Assume
each Leftist
node has the structure
struct Leftist { float Value; Leftist *Parent, *Left, *Right; int Npl; // the null path length };You may assume the existence of a merge function with the following prototype:
Leftist* Merge( Leftist* t1_root, Leftist* t2_root )which merges two leftist heaps, updates the null path lengths as necessary, and returns a pointer to the root of the resulting leftist tree.
P
. The
function should be as efficient as possible.
Here is the prototype:
void LeftistRemove( Leftist* & Root, Leftist* & P )
Solution:
This was a challenging problem, and was intended as such! There are
two parts to the solution. First, is removing P
from the tree,
which involved both fixing pointers and a merge operation. The
second, it isn't nearly enough to merge
the left and right subtrees and merge the result with the root.
Anyway, here is the code.
void LeftistRemove( Leftist* & Root, Leftist* & P ) { // Do the merge and fix pointers. Leftist * q = Merge( P->Left, R->Right ); if ( P == Root ) { Root = q; return; } if ( P->Parent->Left == P ) P->Parent->Left = q; else P->Parent->Right = q; q->Parent = P->Parent; delete P;
// Go up the tree only until the NPL doesn't change! while ( q->Parent != NULL ) { Leftist * parent = q->Parent; if ( (parent->Right == q && parent->Npl == q->Npl+1) || (parent->Left == q && q->Npl >= parent->Right->Npl) ) break; else { parent->Npl = q->Npl+1; if (q->Npl < parent->Right->Npl) swap( q, parent->Right ); q = parent; } } }
Solution:
This one is subtle. Certainly, the merge is . Walking
back up the tree is also
, despite the fact that the
longest path back to the route is O(N). The reason is that
propagation back up to the route can only continue up the right path
or when the right path and left path are balanced. Since the right
path from the route is
, the result follows. Combining the
times additively yields
overall.