Notes

6-1 Percolate Up and Down Write the routines to do a “percolate up” and a “percolate down” in a binary min-heap. Format of functions: void PercolateUp( int p, PriorityQueue H ); void PercolateDown( int p, PriorityQueue H ); where int p is the position of the element, and PriorityQueue is defined as the following: typedef struct HeapStruct *PriorityQueue; struct HeapStruct { ElementType *Elements; int Capacity; int Size; }; Sample program of judge: #include <stdio.h> #include <stdlib.h> typedef int ElementType; #define MinData -1 typedef struct HeapStruct *PriorityQueue; struct HeapStruct { ElementType *Elements; int Capacity; int Size; }; PriorityQueue Initialize( int MaxElements ); /* details omitted */ void PercolateUp( int p, PriorityQueue H ); void PercolateDown( int p, PriorityQueue H ); void Insert( ElementType X, PriorityQueue H ) { int p = ++H->Size; H->Elements[p] = X; PercolateUp( p, H ); } ElementType DeleteMin( PriorityQueue H ) { ElementType MinElement; MinElement = H->Elements[1]; H->Elements[1] = H->Elements[H->Size--]; PercolateDown( 1, H ); return MinElement; } int main() { int n, i, op, X; PriorityQueue H; scanf("%d", &n); H = Initialize(n); for ( i=0; i<n; i++ ) { scanf("%d", &op); switch( op ) { case 1: scanf("%d", &X); Insert(X, H); break; case 0: printf("%d ", DeleteMin(H)); break; } } printf("\nInside H:"); for ( i=1; i<=H->Size; i++ ) printf(" %d", H->Elements[i]); return 0; } /* Your function will be put here */ Sample Input: 9 1 10 1 5 1 2 0 1 9 1 1 1 4 0 0 Sample Output: 2 1 4 Inside H: 5 10 9 Code #include <stdio.h> #include <stdlib.h> typedef int ElementType; #define MinData -1 typedef struct HeapStruct *PriorityQueue; struct HeapStruct { ElementType *Elements; int Capacity; int Size; }; PriorityQueue Initialize( int MaxElements ); /* details omitted */ void PercolateUp( int p, PriorityQueue H ); void PercolateDown( int p, PriorityQueue H ); void Insert( ElementType X, PriorityQueue H ) { int p = ++H->Size; H->Elements[p] = X; PercolateUp( p, H ); } ElementType DeleteMin( PriorityQueue H ) { ElementType MinElement; MinElement = H->Elements[1]; H->Elements[1] = H->Elements[H->Size--]; PercolateDown( 1, H ); return MinElement; } int main() { int n, i, op, X; PriorityQueue H; scanf("%d", &n); H = Initialize(n); for ( i=0; i<n; i++ ) { scanf("%d", &op); switch( op ) { case 1: scanf("%d", &X); Insert(X, H); break; case 0: printf("%d ", DeleteMin(H)); break; } } printf("\nInside H:"); for ( i=1; i<=H->Size; i++ ) printf(" %d", H->Elements[i]); return 0; } /* Your function will be put here */ void swap(int pos1, int pos2, PriorityQueue H){ ElementType tmp = H->Elements[pos1]; H->Elements[pos1] = H->Elements[pos2]; H->Elements[pos2] = tmp; } int min_idx(int idx1, int idx2, PriorityQueue H){ if(H->Elements[idx1] < H->Elements[idx2]) return idx1; return idx2; } void PercolateUp( int p, PriorityQueue H ){ int pos = p; while(pos>1){ int parent_idx = 1; int val = H->Elements[pos]; if(pos%2==0) parent_idx = pos/2; else parent_idx = (pos-1)/2; if(H->Elements[parent_idx]>val) swap(pos, parent_idx, H); else break; pos = parent_idx; } } void PercolateDown( int p, PriorityQueue H ){ int pos = p; while(pos*2 <= H->Size){ int val = H->Elements[pos]; int child_idx = H->Size; if(pos*2+1 <= H->Size) child_idx = min_idx(pos*2, pos*2+1, H); else child_idx = pos*2; if(H->Elements[child_idx] < val) swap(pos, child_idx, H); else break; pos = child_idx; } }

7-1 ZigZagging on a Tree Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences. And it is a simple standard routine to print the numbers in level-order. However, if you think the problem is too simple, then you are too naive. This time you are supposed to print the numbers in “zigzagging order” – that is, starting from the root, print the numbers level-by-level, alternating between left to right and right to left. For example, for the following tree you must output: 1 11 5 8 17 12 20 15. ...

6-1 Isomorphic Two trees, T1 and T2, are isomorphic if T1 can be transformed into T2 by swapping left and right children of (some of the) nodes in T1. For instance, the two trees in Figure 1 are isomorphic because they are the same if the children of A, B, and G, but not the other nodes, are swapped. Give a polynomial time algorithm to decide if two trees are isomorphic. ...

7-1 Pop Sequence Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4. ...