Use only C programming language for the following questions. 1. Write in pseudo-
ID: 3809996 • Letter: U
Question
Use only C programming language for the following questions.
1. Write in pseudo-code the siftdown algorithm for a min-heap.
2. A ternary max-heap is similar to the binary max-heap that we have discussed in class, but now non-leaf nodes can have 3 children instead of 2.
(i) A ternary max-heap can be represented using an array. What are the indices of the parent and children of a node at index i ?
(ii) Write in pseudocode the siftdown algorithm for a ternary max-heap.
3. Show that the alogorihm in Question 2(ii) has worst-case complexity O(log n), where n is the length of the array.
Explanation / Answer
1.psudocode the siftdown algorithm for a min-heap
2.(i) Directed Edge - The link from the parent to the child.
- A node p is an ancestor of a node q if it exists on the path from q to the root. The node q is then termed a descendant of p.
- A size of a node is the number of descendants it has including itself.
2(ii)Algorithm
Extract-Max(A, d)
Input: An array A containing the d-ary heap
Output: Extracting the maximum element of the heap while preserving the heap structure 1: if length(A) < 1 then
2: Error
3: end if
4: max A[0]
5: A[0] A[length(A) 1]
6: length(A) length(A) 1
7: D-SiftDown(A, 0, d)
8: return max
3.Algorithm has worst case complexity O(log n), where n is the length of the array.
Number of nodes at -
Summation of all nodes from level 0 up to level n,
From geometric series summation rule we know that
Substituting x = 2, we get
As 2^(n+1) is the total nodes at level n+1, we can say that the number of nodes with 0 children is one more than the number of nodes with 2 children.
Now lets calculate number of nodes in left subtree, right tree and total ..
By the above reasoning, number of leaf nodes in the left subtree or root = k + 1. Number of non-leaf nodes in the right subtree of root = k as the tree is said to be exactly half full.
Total number of nodes in the left subtree of root = k + k + 1 = 2k +1
That's the reason of saying that the children’s subtrees each have size at most 2n/3.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.