6.2-2

Starting with the procedure MAX-HEAPIFY, write pseudocode for the procedure MIN-HEAPIFYA(i), which performs the corresponding manipulation on a minheap. How does the running time of MIN-HEAPIFY compare to that of MAXHEAPIFY? MIN-HEAPIFY A(i)
l = left(i)
r = right(i)
if l<=A.length and A[l] < A[i] then smallest = l else smallest = i; if r<=A.length and A[r] < A[smallest] then smallest = r if smallest != i then swap a[i] and a[smallest] MIN-HEAPIFY(A,smallest) The running time is same as MAX-HEAPIFY because the max size of substree 2n/3 and $\theta(1)$ to swap A[i] and A[left(i)] and A[right(i)].

Heap sort 2n/3 sub tree size

In a tree where each node has exactly either 0 or 2 children, the number of nodes with 0 children is one more than the number of nodes with 2 children.{Explanation: number of nodes at height h is 2^h, which by the summation formula of a geometric series equals (sum of nodes from height 0 to h-1) + 1; and all the nodes from height 0 to h-1 are the nodes with exactly 2 children}

    ROOT
  L      R
 / \    / \
/   \  /   \
-----  -----
*****

Let k be the number of nodes in R. The number of nodes in L is k + (k + 1) = 2k + 1. The total number of nodes is n = 1 + (2k + 1) + k = 3k + 2 (root plus L plus R). The ratio is (2k + 1)/(3k + 2), which is bounded above by 2/3. No constant less than 2/3 works, because the limit as k goes to infinity is 2/3.
Refrence : http://stackoverflow.com/questions/9099110/worst-case-in-max-heapify-how-do-you-get-2n-3

6.1-7

Show that, with the array representation for storing an n-element heap, the leaves are the nodes indexed by $$\lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2. . . . .n.$$ since 2i and 2i+1 are the children for i th node. for the leaf this will not exist. The no of non leaf nodes are at most $$\lfloor n/2 \rfloor $$ since if i = n/2 if we calculate right child $$2i+1 = 2*(n/2)+1 = n +1 $$ It would outside of the boundary of heap (since we assumed we have n elements). hence the no of non leaf nodes should be at most $$\lfloor n/2 \rfloor $$ Since we index array from 1 to n and we have at most $\lfloor n/2 \rfloor $ non leaf nodes. The leaf nodes are $n/2+1,n/2+2.....n$

6.1-6

Is the array with values {23, 17, 14, 6, 13, 10, 1, 5, 7, 12} a max-heap? False. Because if you form a tree for 6 which is the 4 the element the children are 8{2i} and 9{2i+1}. But a[9] > a[4]. For max heap you need $a{[}parent(i){]} > a{[}i{]} $ but the array doesn't satisfy the above condition.

6.1-5

Is an array that is in sorted order a min-heap? True

6.1-4

Where in a max-heap might the smallest element reside, assuming that all elements are distinct? The smallest element resides at the leaf(last leaf from left to right).

6.1-3

6.1-3 Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree. Since for max-heap the parent is always greater than or equal to the child. The child is also greater than equal its childs. This relation continues till we reach end of the tree.